Donald Knuth es un científico en el campo de la informática que se preocupa tanto por la precisión de sus libros que ofrece un dólar hexadecimal ($2.56, 0x$1.00) por cualquier «error» encontrado, donde un error se considera todo lo que es «técnicamente, históricamente, tipográficamente o políticamente incorrecto». Tenía muchas ganas de recibir un cheque de Knuth, así que decidí buscar errores en su obra maestra «El arte de la programación» (TAOCP). Logré encontrar tres. Cumpliendo con mi palabra, Knuth envió un cheque por 0x$3.00.

Como pueden ver, este no es un cheque real. Antes, Knuth enviaba cheques reales, pero dejó de hacerlo en 2008 debido a fraudes desenfrenados. Ahora envía «certificados de depósito personales» en el Banco San Serrif (BoSS). Dice que está dispuesto a enviar dinero real si es necesario, pero parece que eso es demasiado engorroso.

Encontré dos erratas y un error histórico. Los enlistaré en orden de trivialidad decreciente.

Errata nº 1

La primera errata se encuentra en la página 392 del tercer volumen «Ordenación y búsqueda», octava línea desde abajo: «Después de una búsqueda fallida, a veces (sometime) es recomendable ingresar un nuevo registro en la tabla que contenga K; el método que realiza esto se llama algoritmo de búsqueda e inserción. El error es que en vez de sometime debe ser sometimes.

Por supuesto, no hay nada sorprendente en tal error. Solo en este artículo, seguramente habrá varios errores tipográficos (sin recompensas por encontrarlos). Lo que realmente es sorprendente es que no haya sido notado durante tanto tiempo. La página 392 no está enterrada profundamente en la sección de matemáticas, es la primera página del capítulo seis «Búsqueda»! Tal vez, una de las secciones más leídas del libro. Teóricamente, debería haber menos errores allí, pero no es así.

A propósito, si alguna vez has pensado en leer TAOCP, inténtalo. Muchos dirán que es un manual, no diseñado para lectura directa, pero eso no es cierto. El autor tiene una clara visión y un estilo peculiar. Lo único que obstaculiza la legibilidad es la complejidad de las matemáticas. Sin embargo, hay una solución simple: lee hasta que llegues a las matemáticas que no entiendes, saltéate esa parte y abre la siguiente sección que puedas comprender. Leyendo de esta manera, me salto al menos el 80% del libro, ¡pero el resto del 20% es magnífico!

También se dice que TAOCP no es relevante, obsoleta o de alguna manera irrelevante para la «programación real». Esto también es falso. Por ejemplo, en la primera sección después de la introducción se analiza la búsqueda de un elemento en un array desordenado. El algoritmo más sencillo es conocido por todos los programadores. Inicie el puntero al principio del array y luego realice las siguientes acciones en un ciclo:

1. Verifique si el elemento actual es el deseado. Si es así, devuélvalo; de lo contrario,
2. Verifique si el puntero está fuera del array. Si es así, devuelva un error; de lo contrario,
3. Aumente el puntero y continúe.

Ahora consideremos: ¿cuántas verificaciones de límites requiere este algoritmo en promedio? En el peor de los casos, cuando el array no contiene el elemento, cada elemento de la lista requerirá una verificación, y en promedio esto será algo así como . Un algoritmo de búsqueda más inteligente puede requerir solo una verificación de límites. Adjunte el elemento deseado al final del array, luego inicie el puntero al principio del array y realice las siguientes acciones en un ciclo:

1. Verifique si el elemento actual es el deseado. Si es así, devuelva la respuesta si el puntero está dentro del array, o un error si no lo está. De lo contrario,
2. Aumente el puntero y continúe.

De una manera u otra, el elemento se encontrará garantizado, y la verificación de límites se realiza solo una vez, cuando esto ocurre. Esta es una idea profunda, pero es lo suficientemente simple incluso para un programador principiante. Probablemente no puedo hablar sobre la relevancia del trabajo para otros, pero pude aplicar inmediatamente esta sabiduría tanto en mi código personal como profesional. El libro TAOCP está lleno de estas joyas (y para ser justos, también hay muchas cosas extrañas, como ordenamiento burbuja).

«Buscar, buscar
Tanto tiempo
Buscar, buscar
Solo quería bailar»
— Luther Vandross, «Search» (1980)

Error tipográfico #2

La segunda errata se encuentra en el volumen 4A, "Algoritmos Combinatorios", parte 1. En la página 60 se describe un problema sobre la planificación de las presentaciones de comediantes en varios casinos. Como ejemplo, se mencionan varios comediantes reales, incluyendo a Lily Tomlin, "Weird Al" Yankovic y Robin Williams, quien aún estaba vivo cuando se publicó el libro. Knuth siempre incluye los nombres completos en el índice, así que Williams se menciona en la página 882 como "Williams, Robin Mac-Lorin". Pero su segundo nombre termina en "n", no en "m", es decir, Mac-Lorin.

Mac-Lorin es el apellido de soltera de su madre. Ella era bisnieta de Anselm Joseph Mac-Lorin, el 34º gobernador de Mississippi. Su mandato, aparentemente, no fue recordado por nada bueno. Del libro "Mississippi: Historia":

"El evento más importante durante la administración de Mac-Lorin fue la declaración de guerra de los Estados Unidos a España en la primavera de 1898... Desafortunadamente, la guerra puede haber dado a algunos funcionarios estatales la oportunidad de practicar la corrupción. Mac-Lorin fue acusado de varias prácticas dudosas, incluyendo nepotismo y abuso excesivo de su poder de indulto. En la época del movimiento por la sobriedad, los críticos acusaron al gobernador de embriaguez, lo cual él admitió públicamente."

Error histórico

Consideremos algoritmo tradicional de multiplicación del programa escolar. ¿Cuántas operaciones de multiplicación de un solo dígito requiere? Supongamos que multiplicas un número de -dígitos en de -dígitos. Primero multiplicas el primer dígito por cada dígito uno por uno. Luego multiplicas el segundo dígito por cada dígito uno por uno y así sucesivamente, hasta que hayas pasado por todos los dígitos. De este modo, la multiplicación tradicional requiere multiplicaciones primitivas. En particular, multiplicar dos números de dígitos requiere multiplicaciones de un solo dígito.

Es malo, pero se puede optimizar el proceso usando un método desarrollado por el matemático soviético Anatoly Alexeyevich Karatsuba. Supongamos que y  son números decimales de dos dígitos; es decir, existen números , , , tales que y (la generalización de este algoritmo a cifras mayores requiere ciertas manipulaciones; aunque no es muy complicado, pero para no equivocarme en los detalles, mejor seguiré con un ejemplo simple). Entonces , , . La multiplicación de binomios da . Hasta ahora, todavía tenemos multiplicaciones de un solo dígito: , , , . Ahora sumemos y restemos. . Después de varios reordenamientos, que dejaré como ejercicio para el lector, se obtiene  — ¡solo tres multiplicaciones de un solo dígito! (Hay algunos coeficientes constantes, pero se pueden calcular solo con suma y desplazamiento de dígitos).

No pidas pruebas, pero el algoritmo de Karatsuba (generalizado recursivamente del ejemplo anterior) mejora el método tradicional de multiplicación de operaciones a . Ten en cuenta que esta es una mejora real del algoritmo y no una optimización para cálculos mentales. De hecho, el algoritmo no es adecuado para hacer cálculos mentales, ya que implica grandes sobrecargas por las operaciones recursivas. Además, el efecto no se manifestará completamente hasta que los números sean lo suficientemente grandes (afortunadamente, en lugar del algoritmo de Karatsuba han surgido métodos aún más rápidos: en marzo de 2019 se publicó un algoritmo que requiere solo n log n multiplicaciones; la aceleración es aplicable solo a números inconcebiblemente grandes).

Este algoritmo está descrito en la página 295 del segundo volumen de «Algoritmos generados». Allí, Knuth escribe: «Curiosamente, esta idea fue descubierta solo en 1962 año», cuando se publicó el artículo que describe el algoritmo de Karatsuba. ¡Pero! En 1995, Karatsuba publicó un artículo titulado «Complejidad de los cálculos», en el que menciona varias cosas: 1) alrededor de 1956 Kolmogorov supuso que la multiplicación no podría llevarse a cabo en menos de pasos; 2) en 1960 año, Karatsuba asistió a un seminario donde Kolmogorov expuso su hipótesis n². 3) «Justo hace 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 describiendo el algoritmo. «Solo supe de este artículo después de que fue reimpreso».

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

Análisis

Buscar errores no requería habilidades especiales.

1. El primer error fue tan básico como es posible y estaba en un lugar relativamente visible (al comienzo del capítulo). Cualquiera podría haberlo encontrado; simplemente yo fui ese cualquiera.
2. La búsqueda del segundo error tipográfico requirió suerte y esfuerzo, pero no habilidad. El índice para "Williams" se encuentra en la penúltima página del volumen, una parte bastante notable del libro. Justo estaba hojeando el índice (no es tan doloroso como parece, ya que en los índices de Knuth se esconden huevos de Pascua. Por ejemplo, hay entradas en árabe y hebreo, ambas apuntando a la página 66. Pero en esa página no se menciona ninguno de los idiomas; en cambio, se mencionan "idiomas que se leen de derecha a izquierda"). Y mi atención fue capturada por el segundo nombre. Dado que normalmente leo Wikipedia, verifiqué a Robin Williams y noté una discrepancia.
3. Me gustaría decir que hice una investigación seria para encontrar un error histórico, pero en realidad solo eche un vistazo a la página de Wikipedia sobre el algoritmo Karatsuba.En las primeras líneas dice: "El algoritmo Karatsuba es un algoritmo de multiplicación rápida. Descubierto por Anatoliy Karatsuba en 1960 y publicado en 1962". Después de eso, solo quedaba sumar dos más dos.

En el futuro, me gustaría encontrar un error más sustancial, especialmente en el código de Knuth. También me gustaría encontrar un fallo en el primer volumen de "Algoritmos Fundamentales". Quizás lo hubiera encontrado, pero en la biblioteca local por alguna razón solo hay disponibles los volúmenes 2, 3 y 4A.

Hechos financieros:

• En total, mi contribución a TAOCP consiste en solo tres símbolos: una adición s, un reemplazo m en n y 2 en 0. A $2.56, son símbolos bastante rentables; si te pagaran tal cantidad, un artículo de 1000 palabras (en promedio, unas cuatro símbolos) te podría generar diez.
• Con tres dólares hexadecimales, junto a otros 29 ciudadanos, ocupo el puesto 69 en la lista de los más ricos contribuyentes del banco San Serriffe (a fecha del 1 de mayo de 2019).

Otras discusiones sobre los cheques de Knuth

• Cómo obtener un cheque de Knuth

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

  Es mejor esperar hasta que no tengas un conjunto de errores que enviar. Al combinar varios errores reales, aunque no sean muy valiosos, aumentarás la probabilidad de que uno de ellos realmente sea considerado un error o consejo. Si envías errores uno por uno, cada uno individualmente puede ser rechazado.

  No quería enviar solo tonterías, así que seguí el consejo y envié el correo solo cuando encontré un error histórico que me pareció lo suficientemente serio.

• Cheques de Ashutosh Mehra

  Ashutosh Mehra es el tercer inversor más rico en San-Seriff con una fortuna colosal de 0x$207,f0 en BoSS.

• Cheque por algunos errores no funcionales en el código real de TeX
• Varios: #1 #2 #3 #4 #5 #6

Fuente: habr.com