Donald Knuth es un científico de la computación que se preocupa tanto por la exactitud de sus libros que ofrece un dólar hexadecimal ($ 2.56, 0x $ 1.00) por cualquier "error" encontrado, donde todo lo que es "técnica, histórica y tipográficamente, se considera un error". o políticamente mal ". Tenía muchas ganas de recibir un cheque de Knut, así que decidí buscar errores en su excelente trabajo "El arte de la programación" (TAOCP). Me las arreglé para encontrar tres. Fiel a la palabra, Knut envió un cheque por 0x $ 3.00 .



Como puede ver, este no es un control real. Knut solía enviar cheques reales, pero se detuvo en 2008 debido a un fraude desenfrenado . Ahora envía "certificados de depósito personales" en el Banco de San Serriff (BoSS). Él dice que está listo para enviar dinero real si es necesario, pero parece ser demasiado problemático.

Encontré dos errores tipográficos y un error histórico. Los enumeraré en orden decreciente de trivialidad.

Error tipográfico 1

El primer error tipográfico está en la página 392 del tercer volumen "Ordenar y buscar", la octava línea desde abajo: "Después de una búsqueda fallida, a veces (en algún momento) es aconsejable ingresar un nuevo registro en la tabla que contiene K ; El método que hace esto se llama algoritmo de búsqueda e inserción. El error es que en lugar de alguna vez debería ser a veces .

Por supuesto, tal error no es sorprendente. Solo en este artículo seguramente habrá algunos errores tipográficos (no hay recompensas por encontrarlos). Lo que es realmente sorprendente es que no se ha notado por tanto tiempo. La página 392 no está enterrada en lo profundo de la sección de matemáticas, ¡esta es la primera página del sexto capítulo de "Búsqueda"! Quizás una de las secciones más leídas del libro. En teoría, debería haber menos errores tipográficos, pero no.

Por cierto, si alguna vez pensaste en leer TAOCP, pruébalo. Muchos dirán que esta es una guía no destinada a la lectura directa, pero esto no es cierto. El autor tiene un punto de vista claro y un estilo peculiar. Lo único que impide la legibilidad es la complejidad de las matemáticas. Sin embargo, hay una solución simple: lea hasta llegar a las matemáticas que no comprende, omítalas y abra la siguiente sección que pueda comprender. Al leer de esta manera, echo de menos al menos el 80% del libro, ¡pero el 20% restante es genial!

También dicen que TAOCP es irrelevante , obsoleto o de otra manera inaplicable a la "programación real". Esto tampoco es cierto. Por ejemplo, en la primera sección después de la introducción, se considera la búsqueda de un elemento en una matriz no ordenada. El algoritmo más simple es familiar para todos los programadores. Ejecute el puntero al comienzo de la matriz, luego haga lo siguiente en un bucle:

1. Compruebe si se desea el elemento actual. Si es así, devuélvelo; de lo contrario
   
2. Compruebe si el puntero está fuera de la matriz. Si es así, devuelve un error; de lo contrario
   
3. Aumenta el puntero y continúa.

Ahora considere: ¿cuántas verificaciones fronterizas requiere este algoritmo, en promedio? En el peor de los casos, cuando la matriz no contiene un elemento, para cada elemento de la lista se requiere una verificación, y en promedio será algo así como $$$N / 2$. Un algoritmo de búsqueda más inteligente puede funcionar con solo una verificación de borde. Adjunte el elemento deseado al final de la matriz, luego ejecute el puntero al comienzo de la matriz y siga estos pasos en un bucle:

1. Compruebe si se desea el elemento actual. Si es así, devolvemos la respuesta si el puntero está dentro de la matriz, o un error si no lo está. De lo contrario
   
2. Aumenta el puntero y continúa.

De una forma u otra, se garantiza que el elemento se encontrará, y la verificación de bordes se realiza solo una vez, cuando esto sucedió. Esta es una idea profunda, pero es lo suficientemente simple incluso para un programador novato. Probablemente, no puedo hablar sobre la relevancia del trabajo para otros, pero pude aplicar inmediatamente esta sabiduría tanto en código personal como profesional. El libro TAOCP está lleno de esas perlas (para ser justos, hay muchas cosas extrañas, como la clasificación de burbujas ).

"Buscar, buscar
Tanto tiempo
Buscar, buscar
Solo quería bailar ".
- Luther Wandross, Búsqueda (1980)

Error tipográfico 2

El segundo error tipográfico está en el Volumen 4A, Algoritmos combinatorios, Parte 1. En la página 60, describimos la tarea de planificar las actuaciones de los comediantes en varios casinos. Algunos verdaderos comediantes son citados como ejemplo, incluidos Lily Tomlin, Strange Al Jankovic y Robin Williams, que todavía estaba vivo cuando salió el libro. Whip siempre da nombres completos en el índice , por lo que en la página 882 se hace referencia a Williams como "Williams, Robin McLorim". Pero su segundo nombre termina con "n", y no con "m", es decir, McLoreen.

McLorin es el apellido de soltera de su madre. Ella era la bisnieta de Anselm Joseph McLorin, 34º gobernador de Mississippi. Su regla, aparentemente, no fue recordada por nada bueno. Del libro Mississippi: Historia :

“El evento más importante durante la administración de McLorin fue que Estados Unidos declaró la guerra de España en la primavera de 1898 ... Desafortunadamente, la guerra pudo haber permitido que algunos funcionarios del gobierno practicaran el soborno. McLorin ha sido acusado de varias prácticas dudosas, incluido el nepotismo y el uso excesivo de los poderes de perdón. En la era de la sobriedad, los críticos acusaron al gobernador de embriaguez, lo cual admitió públicamente ".

Error histórico

Considere el algoritmo de multiplicación tradicional del currículo escolar. ¿Cuánto requiere operaciones de multiplicación de un bit? Supongamos que multiplicas $$$m$-número de bit $$$x$en $$$n$-bit $$$y$. Primero, multiplique el primer dígito $$$x$por cada dígito $$$y$turnarse. Luego multiplica el segundo dígito $$$x$por cada dígito $$$y$turnarse y así sucesivamente hasta pasar por todos los números $$$x$. Por lo tanto, la multiplicación tradicional requiere $$$mn$multiplicaciones primitivas En particular, la multiplicación de dos números por $$$n$las descargas requieren $$$n ^ 2$multiplicaciones de un solo bit.

Esto es malo, pero puede optimizar el proceso utilizando el método desarrollado por el matemático soviético Anatoly Alekseevich Karatsuba. Asume que $$$x$y $$$y$- números decimales de dos dígitos; es decir, hay números $$$a$, $$$b$, $$$c$, $$$d$tal que $$$x = (ab) _ {10}$y $$$y = (cd) _ {10}$(la generalización de este algoritmo a grandes cantidades requiere ciertas manipulaciones; aunque esto no es demasiado difícil, pero para no equivocarse en los detalles, mejor me quedo con un ejemplo simple). Entonces $$$x = 10a + b$, $$$y = 10c + d$, $$$xy = (10a + b) (10c + d)$. La multiplicación de binomios da $$$xy = 100ac + 10ad + 10bc + bd$. Por el momento, todavía $$$n ^ 2 = 4$multiplicación de un solo bit: $$$ac$, $$$ad$, $$$bc$, $$$bd$. Ahora suma y resta $$$10ac + 10bc$. Después de algunas permutaciones, que dejaré como ejercicio para el lector, resulta que $$$xy = 110ac + 11bd + 10 (a - b) (d - c)$- ¡solo tres multiplicaciones de un dígito! (Hay algunos coeficientes constantes, pero solo se pueden calcular sumando y desplazando los dígitos).

No solicite pruebas, pero el algoritmo de Karatsuba (generalizado recursivamente del ejemplo anterior) mejora el método tradicional de multiplicación con $$$O (n ^ 2)$operaciones antes $$$O (n ^ {(lg 3)})$. Tenga en cuenta que esta es una mejora real en el algoritmo, no una optimización para cálculos mentales. De hecho, el algoritmo no es adecuado para calcular en la mente, ya que requiere una gran sobrecarga para las operaciones recursivas. Además, el efecto no será completamente aparente hasta que los números se vuelvan lo suficientemente grandes (afortunadamente, en lugar del algoritmo de Karatsuba, aparecieron métodos aún más rápidos: en marzo de 2019, se publicó un algoritmo que requería solo n log n multiplicaciones; la aceleración es aplicable solo a inimaginablemente grande números).

Este algoritmo se describe en la página 295 del segundo volumen, Algoritmos derivados. Allí Knuth escribe: "Es curioso que esta idea se descubriera solo en 1962 " cuando se publicó un artículo que describe el algoritmo Karatsuba. Pero! En 1995, Karatsuba publicó un artículo, "Complejidad de la informática", que dice varias cosas: 1) alrededor de 1956, Kolmogorov sugirió que la multiplicación no se puede hacer en menos de $$$O (n ^ 2)$pasos 2) en 1960 , Karatsuba asistió a un seminario donde Kolmogorov presentó su hipótesis n². 3) "Exactamente en una semana" Karatsuba desarrolló el algoritmo "divide y vencerás"; 4) en 1962, Kolmogorov escribió y publicó un artículo en nombre de Karatsuba con una descripción del algoritmo. "Solo me enteré de este artículo después de que fue reimpreso".

Por lo tanto, el error es que 1960 debería indicarse en lugar de 1962 . Eso es todo

Análisis

La búsqueda de errores no requirió mucha habilidad.

1. El primer error fue lo más común posible, y fue en un lugar relativamente prominente (el comienzo del capítulo). Cualquier idiota la encontraría; Simplemente resultó ser ese idiota.
   
2. Encontrar un segundo error tipográfico requería suerte y diligencia, pero no habilidad. El índice de "Williams" está en la penúltima página del volumen, una parte bastante destacada del libro. Estaba hojeando el índice (no es tan patético como parece porque los huevos de Pascua están ocultos en los índices de Knuth. Por ejemplo, hay entradas en árabe y hebreo, y ambas apuntan a la página 66. Pero esta página tampoco menciona idiomas; en cambio, se refiere a "idiomas que se leen de derecha a izquierda"). Y mi atención fue atraída por el segundo nombre. Como generalmente leo Wikipedia, revisé a Robin Williams y noté una discrepancia.
   
3. Me gustaría decir que realicé un estudio serio para encontrar un error histórico, pero en realidad solo miré la página de Wikipedia sobre el algoritmo Karatsuba . Las primeras líneas dicen: “El algoritmo de Karatsuba es un algoritmo para la multiplicación rápida. Descubierto por Anatoly Karatsuba en 1960 y publicado en 1962. " Después de eso, solo quedaba doblar dos veces.

En el futuro, me gustaría encontrar un error más significativo, especialmente en el código de Knuth. También me gustaría encontrar un error en el primer volumen, Algoritmos fundamentales. Tal vez lo habría encontrado, pero por alguna razón solo hay volúmenes 2, 3 y 4A en la biblioteca local.

Hechos financieros:

• En total, mi contribución a TAOCP consta de solo tres caracteres: uno que agrega s , reemplazando m con ny 2 con 0 . Con un precio de $ 2.56, estos son símbolos bastante lucrativos; si le pagaran ese tipo de dinero, un artículo de 1000 palabras (en promedio, cuatro caracteres cada una) le traería diez piezas.
  
• Con tres dólares hexadecimales, yo, junto con otros 29 ciudadanos, comparto el puesto 69 en la lista de los depositantes más ricos del Banco de San Serriff (al 1 de mayo de 2019).

Otras discusiones sobre cheques Knut

• Cómo obtener un cheque de Knut
  
  Pautas generales para encontrar errores en los libros de Knut. Principalmente errores técnicos que no tengo. Hay una sugerencia que tomé en serio:
  
  

  Es mejor esperar hasta que recopile un conjunto de errores para enviar. Al combinar varios errores reales, pero no muy valiosos, aumentará la probabilidad de que uno de ellos sea realmente considerado como un error o un consejo. Si envía errores de uno en uno, cada uno puede ser rechazado individualmente.

  
  No quería enviar errores tipográficos sin sentido, pero obedecí el consejo y envié una carta solo cuando encontré un error histórico que parecía lo suficientemente grave.
  
• Cheques de Ashutosh Mehra
  
  Ashutosh Mehra es el tercer contribuyente más rico de San Serriff con una fortuna enorme de 0x $ 207, f0 en BoSS.
  
• Verifique algunos errores no funcionales en el código TeX real
  
• Varios: # 1 # 2 # 3 # 4 # 5 # 6