| A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)(kolja.rs) | |
| 223 points by nk_kolja 8 days ago | 50 comments | |
tl;dr: While implementing Knuth's long division (Algorithm 4.3.1D from TAOCP Vol II), the author found a decades-old bug introduced in 1995 when Knuth switched from a saturated (x86-style) trial quotient to an unsaturated (ARM-style) one without updating the correctness bounds—step D3's two corrections can fail when q̂ = b+2, though this only manifests with odd bases (smallest case: base 3). Knuth acknowledged the bug, paid the customary hexadecimal dollar, and published the correction in the 2026 errata. The author also flagged a related outdated check (`qp == b` vs `>= b`) in LLVM's APInt.cpp that happens to work but isn't justified by the book's proofs. | |
HN Discussion:
| |