Donald Knuth es un científico informático que se preocupa tanto por la precisión de sus libros que sugiere un dólar hexadecimal ($2,56, 0x$1,00) por cualquier "error" encontrado, donde un error se define como cualquier cosa que sea "técnica, histórica, tipográfica o políticamente incorrecta". Tenía muchas ganas de recibir un cheque de Knuth, así que decidí buscar errores en su obra maestra. "El arte de programar" (TAOCP). Logramos encontrar tres. Fiel a su palabra, Knut envió un cheque por 0x$3,00.

Como puede ver, este no es un control real. Knuth solía enviar cheques reales, pero dejó de enviarlos en 2008 debido a fraude desenfrenado. Ahora envía "certificados de depósito personales" a Banco de San Serriff (Jefe). Dice que está dispuesto a enviar dinero real si es necesario, pero parece que es demasiado complicado.

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

Error tipográfico n.° 1

El primer error tipográfico se encuentra en la página 392 del tercer volumen de “Clasificación y búsqueda”, octava línea desde abajo: “Después de una búsqueda fallida, a veces (a veces) es deseable 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 eso algun tiempo debe ser a veces.

Por supuesto, tal error no es sorprendente. Es probable que haya algunos errores tipográficos solo en este artículo (no hay recompensa por encontrarlos). Lo realmente sorprendente es que haya pasado desapercibido durante tanto tiempo. La página 392 no está enterrada profundamente en la sección de matemáticas, está la primera página Capítulo XNUMX "Buscar"! Posiblemente una de las secciones más leídas del libro. En teoría, debería haber la menor cantidad de errores tipográficos, pero no.

Por cierto, si alguna vez has pensado en leer TAOCP, inténtalo. Muchos dirán que esto es directorio, no está destinado a lectura directa, pero esto no es cierto. El autor tiene un punto de vista claro y un estilo distintivo. Lo único que dificulta la legibilidad es la complejidad de las matemáticas. Sin embargo, hay una solución simple: lea hasta que llegue a las matemáticas que no comprende, omítalas y pase a la siguiente sección que pueda comprender. Al leer de esta manera, me pierdo al menos el 80% del libro, ¡pero el otro 20% es genial!

También se dice que TAOCP irrelevante, está desactualizado o no es aplicable a la "programación real". Esto tampoco es cierto. Por ejemplo, la primera sección después de la introducción analiza cómo encontrar un elemento en una matriz sin clasificar. El algoritmo más simple es familiar para todos los programadores. Inicie el puntero al principio de la matriz, luego haga lo siguiente en un bucle:

1. Compruebe si el elemento actual es el deseado. Si es así, lo devolvemos; de lo contrario
2. Compruebe si el puntero está fuera del límite de la matriz. Si es así, devuelve un error; de lo contrario
3. Acércate y continúa.

Ahora considere: ¿cuántas comprobaciones de límites requiere este algoritmo, en promedio? En el peor de los casos, cuando la matriz no contiene ningún elemento, cada elemento de la lista requerirá una verificación y, en promedio, será algo así como . Un algoritmo de búsqueda más inteligente podría salirse con la suya con solo una verificación de límites. Adjunte el elemento deseado al final de la matriz, luego inicie el puntero al principio de la matriz y haga lo siguiente en un bucle:

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

De una forma u otra, se garantiza que se encontrará el elemento y la verificación de límites se realiza solo una vez cuando esto sucede. Esta es una idea profunda, pero bastante simple incluso para un programador novato. Probablemente no pueda hablar de la relevancia del trabajo para los demás, pero inmediatamente pude aplicar esta sabiduría al código tanto personal como profesional. El libro TAOCP está lleno de esas joyas (para ser justos, también hay muchas cosas extrañas allí, como ordenamiento de burbuja).

"Buscar Buscar
Hasta la vista
Buscar Buscar
Sólo quería bailar"
— Luther Vandross, "La búsqueda" (1980)

Error tipográfico n.° 2

El segundo error tipográfico se encuentra en el Volumen 4A, Algoritmos combinatorios, Parte 1. La página 60 describe un problema que implica programar comediantes para actuar en varios casinos. Se citan como ejemplos varios comediantes de la vida real, incluidos Lily Tomlin, Weird Al Yankovic y Robin Williams, que todavía estaba vivo cuando se publicó el libro. Knuth siempre enumera los nombres completos en el índice, por lo que Williams aparece en la página 882 como "Williams, Robin McLorim". Pero su segundo nombre termina en “n” y no en “m”, es decir, McLaurin.

McLaurin era el apellido de soltera de su madre. Era bisnieta de Anselm Joseph McLaurin, 34º gobernador de Mississippi. Su reinado, aparentemente, no fue recordado por nada bueno. Del libro "Mississippi: Historia":

“El acontecimiento más importante durante la administración McLaurin fue la declaración de guerra de Estados Unidos a España en la primavera de 1898... Desafortunadamente, la guerra puede haber brindado a algunos funcionarios del gobierno la oportunidad de participar en sobornos. McLaurin fue acusado de varias prácticas cuestionables, incluido el nepotismo y el uso excesivo de los poderes de indulto. Durante el movimiento por la templanza, los críticos acusaron al gobernador de ser un borracho, lo cual él admitió públicamente”.

Error histórico

Considerar algoritmo de multiplicación tradicional del currículum escolar. ¿Cuántas multiplicaciones de un solo dígito se requieren? Supongamos que multiplicas -dígito en -poco . Primero multiplica el primer dígito. para cada dígito uno a uno. Luego multiplica el segundo dígito para cada dígito uno por uno y así sucesivamente hasta pasar por todos los números . Por lo tanto, la multiplicación tradicional requiere multiplicaciones primitivas. En particular, multiplicar dos números por rangos requeridos multiplicaciones de un solo dígito.

Esto es malo, pero es posible optimizar el proceso utilizando un método desarrollado por el matemático soviético Anatoly Alekseevich Karatsuba. pretendamos que и  - números decimales de dos dígitos; es decir, hay números , , , tal que и (Generalizar este algoritmo a números mayores requiere cierta manipulación; aunque no es demasiado difícil, para no cometer errores en los detalles, será mejor que me ciña a un ejemplo sencillo). Entonces , , . Multiplicar binomios da . Por el momento todavía tenemos multiplicación de un solo dígito: , , , . Ahora sumamos y restamos . Después de algunos arreglos, que dejaré como ejercicio para el lector, resulta  - ¡sólo tres multiplicaciones de un solo dígito! (Hay algunos coeficientes constantes, pero solo se pueden calcular sumando y desplazando los dígitos).

No pidas pruebas, pero algoritmo de karatsuba (generalizado recursivamente del ejemplo anterior) mejora el método de multiplicación tradicional con operaciones antes . Tenga en cuenta que se trata de una mejora real del algoritmo, no de una optimización de los cálculos mentales. De hecho, el algoritmo no es adecuado para la aritmética mental, ya que requiere grandes costos generales para las operaciones recursivas. Además, el efecto no se manifestará completamente hasta que los números sean lo suficientemente grandes (afortunadamente, el algoritmo de Karatsuba ha sido reemplazado por métodos aún más rápidos: en marzo de 2019, se publicó un algoritmo que solo requiere registro norte multiplicaciones; La aceleración sólo se aplica a números inimaginablemente grandes).

Este algoritmo se describe en la página 295 del Volumen XNUMX, Algoritmos seminuméricos. Allí Knuth escribe: “Es curioso que esta idea sólo se descubriera en 1962 año”, cuando se publicó un artículo que describía el algoritmo de Karatsuba. ¡Pero! En 1995, Karatsuba publicó un artículo "Complejidad computacional", que dice varias cosas: 1) alrededor de 1956, Kolmogorov sugirió que la multiplicación no se puede hacer en menos de pasos; 2) en 1960 año Karatsuba asistió al seminario donde Kolmogorov presentó su hipótesis n². 3) “En exactamente una semana”, Karatsuba desarrolló el algoritmo de “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 se volvió a publicar".

Entonces el error es que en lugar de 1962 debe ser especificado 1960 año. Eso es todo.

análisis de

Encontrar errores no requirió ninguna habilidad especial.

1. El primer error fue lo más trivial posible y estuvo en un lugar relativamente visible (el comienzo del capítulo). Cualquier idiota lo habría encontrado; Simplemente resulté ser ese idiota.
2. Encontrar el segundo error tipográfico requirió suerte y diligencia, pero no habilidad. El índice de "Williams" se encuentra 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 hay huevos de Pascua escondidos en los índices de Knuth. Por ejemplo, hay entradas en árabe y hebreo, ambas apuntando a la página 66. Pero esa página no menciona cualquiera de los dos idiomas; en cambio se refiere a “idiomas que se leen de derecha a izquierda”). Y el segundo nombre me llamó la atención. Como suelo leer Wikipedia, revisé Robin Williams y noté una discrepancia.
3. Ojalá pudiera decir que hice una investigación seria para encontrar un error histórico, pero en realidad solo miré Página de Wikipedia sobre el algoritmo de Karatsuba. Las primeras líneas dicen: “El algoritmo de Karatsuba es un algoritmo de multiplicación rápida. Descubierto por Anatoly Karatsuba en 1960 y publicado en 1962." Después de eso lo único que quedaba era sumar dos más dos.

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

Datos financieros:

• En total, mi contribución a TAOCP consta de sólo tres caracteres: una adición s, reemplazo m en n и 2 en 0. A 2,56 dólares, estos son algunos símbolos bastante lucrativos; Si le pagaran esa cantidad de dinero, un artículo de 1000 palabras (un promedio de cuatro caracteres) le reportaría diez mil dólares.
• Con tres dólares hexadecimales, yo, junto con otros 29 ciudadanos, estoy empatado en el puesto 69 en la lista de los depositantes más ricos del Banco San Serriff (al 1 de mayo de 2019).

Otras discusiones sobre cheques de Knuth

• Cómo obtener un cheque de Knuth

  Recomendaciones generales para encontrar errores en los libros de Knuth. Principalmente se refieren a errores técnicos, que no tengo. Hay una sugerencia que tomé en serio:

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

  No quería enviar sólo errores tipográficos sin sentido, sino que seguí el consejo y envié la carta sólo cuando encontré un error histórico que parecía suficientemente grave.

• Los cheques de Ashutosh Mehra

  Ashutosh Mehra es el tercer inversor más rico de San Serriff con un enorme patrimonio neto de 0x$207.f0 en BoSS.

• Compruebe si hay algunos errores no funcionales en el código TeX real
• Varios: #1 #2 #3 #4 #5 #6

Fuente: habr.com