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:
  • Author of the bug find shares context and confirms Knuth's acknowledgment and errata publication
  • Awe and celebration of finding a decades-old bug in a Knuth algorithm
  • Personal anecdotes about implementing division algorithms without hitting this bug
  • Fellow Knuth-check recipients share their own experiences of finding errors in TAOCP
  • Technical clarification question about whether the bug affects MIX/MMIX implementations too