Un error oculto durante décadas en el algoritmo de división larga de Knuth

Un programador que implementaba una biblioteca de aritmética multiprecisión para criptografía detectó, al estudiar el Algoritmo D de la división larga descrito en 'The Art of Computer Programming' de Donald Knuth, un fallo en el Teorema B del que depende su corrección. El demostructura le pareció antinatural y obligaba a tratar un caso que no era marginal, por lo que intentó probar el teorema por su cuenta. Fracasó, pero el fracaso le proporcionó un contraejemplo que invalida el algoritmo tal como está presentado: el error llevaba décadas oculto en el texto de referencia. Como consecuencia, el autor formuló un teorema propio sobre la corrección del algoritmo, que ahora lleva su nombre. El artículo explica paso a paso cómo funciona la división larga multiprecisión, desde las instrucciones primitivas de un solo word (addc, subc, mul, div) hasta la reducción de la división larga (n+m+1/n) a la división media (n+1/n) y, finalmente, a la división corta (2/1) que ofrece el hardware. El texto incluye el pseudocódigo del Algoritmo 1, sus invariantes y el análisis de por qué el contraejemplo pasó inadvertido durante tanto tiempo. Además, el autor descubrió un fallo en la implementación de este algoritmo en LLVM, que también se aborda en la entrada.