A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
A developer implementing Algorithm D from Knuth's TAOCP found a counterexample to Theorem B, revealing a bug that had gone unnoticed for decades. The bug, now fixed in the errata, also led to the discovery of a related issue in LLVM's implementation. This post explains the algorithm, the bug's origin, and why it remained hidden, plus modern alternatives.
The correctness of the algorithm relied on Theorem B, and its proof bugged me.
- nk_kolja
I found a bug in Algorithm D, the long division algorithm in Knuth's "The Art of Computer Programming". It was discussed on HN a couple of times https://news.ycombinator.com/item?id=26562819 as well as on other websites.
I sent a letter to Knuth and received a check and an annotated reply. The updated Theorem B, which was unchanged since 1969 is now dated 2026.
While searching for vulnerable implementations I also found a "bug" in llvm, so I expanded a bit on that too.
- Retr0id
> I am not aware of any systems that store integers in limbs of odd size.
On 32-bit platforms, CPython's (big)integers use 15-bit limbs (to make carry handling easier).
https://github.com/python/cpython/blob/20e6c2fc7c174342214d5...
Odd limb sizes are also fairly common in cryptographic implementations e.g. x25519, but there's also no division there.
- ginko
The typesetting of this looks very broken on firefox with extreme gaps between lines of text. Seems to render fine on chromium.