Un error de décadas en la división larga de Knuth (TAOCP Vol II, Algoritmo 4.3.1D)
A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
Al implementar el Algoritmo D de Knuth para división larga, el autor encontró un error que ha pasado desapercibido durante décadas. La demostración del Teorema B le resultaba artificial, lo que lo llevó a intentar probarlo por su cuenta y fracasar, obteniendo un contraejemplo que invalida el algoritmo. Este hallazgo le valió un teorema propio en las erratas de TAOCP. El artículo explica el algoritmo desde cero, analiza cómo el error pudo permanecer oculto tanto tiempo, y también señala un posible bug en la implementación de LLVM. Además, ofrece una visión de métodos modernos para implementar división larga.
El fracaso me entregó un contraejemplo al Algoritmo D que había pasado por correcto durante décadas, y con él un teorema sobre la corrección del algoritmo que lleva mi nombre.
- nk_kolja
Encontré un error en el Algoritmo D, el algoritmo de división larga en "El Arte de Programar Computadoras" de Knuth. Se discutió en HN un par de veces https://news.ycombinator.com/item?id=26562819 así como en otros sitios web. Envié una carta a Knuth y recibí un cheque y una respuesta anotada. El Teorema B actualizado, que no había cambiado desde 1969, ahora tiene fecha de 2026. Mientras buscaba implementaciones vulnerables, también encontré un "error" en llvm, así que también profundicé un poco en eso.
- WalterBright
En los años 80, antes de que existiera la instrucción DIV, implementé la división de enteros. Usé el mismo algoritmo de división larga que me enseñaron en tercer grado, excepto en binario en lugar de base 10. Desplazar y restar. También fue la base para implementar FDIV (división de punto flotante) para aquellos que no tenían un chip x87. Nadie reportó nunca un error en él.
- enriquto
Este puede ser fácilmente el post más épico en la historia de HN. EDIT: Recuerdo con cariño el Algoritmo D... una de mis primeras experiencias de programación en los 90 fue intentar implementar los algoritmos aritméticos de Knuth para suma, resta, etc. en ensamblador 8086. Los logré hasta la multiplicación larga (esa fue un esfuerzo tremendo). El Algoritmo D era demasiado formidable como para siquiera atreverme a intentarlo. Me siento extremadamente feliz de ver a personas en 2026 examinando estos algoritmos de cerca.