HN Debrief

A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)

  • Programming
  • Algorithms
  • Developer Tools
  • Open Source

The post argues that Knuth’s famous multiple-precision long division algorithm, Algorithm 4.3.1D in The Art of Computer Programming Volume 2, has had a subtle bug in its published form for decades. The author says the problem sits in Step D3, the trial-quotient correction step, and that a 1995 wording change broke the old proof of correctness in Theorem B. Knuth acknowledged it, updated the theorem in 2026, and sent the usual reward check. The writeup also says a related misunderstanding showed up in LLVM. What landed with readers was not “TAOCP is unreliable” but almost the opposite. People took this as proof of how rarely real errors are still found in Knuth, because this one needed a very specific corner case and close reading of both the prose and the proof. The practical consensus was that most real implementations are probably safe because they already treat D3 as a loop, and because the bad case only appears under peculiar conditions such as an odd radix. The sharper point was that the failure was as much about the proof as the code. The old bound said the correction step could only need at most two decrements. The corrected result is at most three. That sounds tiny, but it is exactly the kind of tiny bound that turns into an overflow or wrong assumption in production arithmetic code if someone bakes it in too confidently.

If you maintain bigint or low-level arithmetic code, do not assume Knuth-derived division logic is correct just because it comes from TAOCP or has been copied for years. Re-check quotient-estimation edge cases, especially around unusual radices and proof assumptions that bounded the correction step too tightly.

Discussion mood

Strongly impressed and celebratory. People saw this as an unusually high-value find in a foundational algorithm, while also stressing that the bug is rare, mostly proof-level for many readers, and unlikely to break most existing implementations unless they hard-coded the old bound or copied LLVM-like logic.

Key insights

  1. 01

    Most code avoids the bug already

    Many derived implementations are probably untouched because the problematic published wording is not the same as the safer implementation strategy people actually use. The author says Knuth’s MIX program handles the trial quotient differently enough to dodge the failure, and also notes you probably will not need changes unless your arithmetic uses an odd radix. That narrows the blast radius a lot. The discovery is still important because proofs and code generators often copy the stated bound, not just the control flow.

    Audit any division code that relies on a formal bound for quotient correction, not just code that literally copies Algorithm D. If your implementation uses standard machine-word bases you may be safe in practice, but you should verify that rather than assume it.

      Attribution:
    • nk_kolja #1 #2
  2. 02

    The ambiguity was in Step D3 wording

    The dangerous part was not a blatant algebra mistake but an instruction that programmers could read two ways. The sentence ending with “repeat this test if r̂ < b” reads like an ordinary loop to many people, and commenters noted that nearly every implementation took it that way. The deeper issue is that the accompanying theorem still promised too small a maximum number of corrections. That mismatch let readers believe both “the loop is obvious” and “the bound is two” at the same time, which is how subtle arithmetic bugs survive for decades.

    When you implement from a book or paper, check that the proof obligations match the control flow you inferred from the prose. If a correctness argument depends on a tight iteration bound, test and reason about the bound separately.

      Attribution:
    • nk_kolja #1 #2
    • as2j-1298 #1
    • rna-mall #1
  3. 03

    Bad font fallback broke the math

    A few readers could not follow the article at all because Firefox substituted terrible fonts for some math glyphs and blew up line spacing. Others recognized the pattern from missing or mis-prioritized fonts, including cases involving Arabic font fallback. The author updated the site with a different fallback font. This mattered here because the post lives or dies on precise notation, and rendering glitches can make a correct proof look incomprehensible.

    If you publish technical writing with math on the web, test it across browsers and fallback-font setups, not just on your own machine. A readable PDF or alternate rendering is worth having when notation is central to the argument.

      Attribution:
    • ginko #1
    • Retr0id #1
    • voakbasda #1
    • nk_kolja #1

Against the grain

  1. 01

    Simple binary long division stayed dependable

    A low-level implementer pointed out that ordinary shift-and-subtract division in binary worked fine for decades, including as a basis for floating-point division on hardware without x87 support. That pushes back on any temptation to treat Algorithm D as the only serious path for division. The bug lives in an optimized multi-precision quotient-estimation scheme, not in the basic schoolbook idea of division itself.

    If your priority is robustness over speed, revisit whether a simpler division algorithm is good enough for your workload. Highly optimized quotient estimation buys performance, but it also creates proof and edge-case surface area.

      Attribution:
    • WalterBright #1

In plain english

Algorithm D ↩
Knuth’s classic algorithm for multiple-precision long division, used when dividing numbers larger than a machine word.
LLVM ↩
A widely used compiler infrastructure that underpins languages and tools such as Clang and parts of Rust.
MIX ↩
The hypothetical computer architecture Knuth used in earlier editions of TAOCP to present machine-level programs.
odd radix ↩
A number base that is an odd number rather than an even one, which can create unusual edge cases in arithmetic algorithms.
TAOCP ↩
The Art of Computer Programming, Donald Knuth’s multi-volume reference work on algorithms and programming.
Theorem B ↩
A correctness result in TAOCP that gives a bound used to justify the quotient-correction step in Algorithm D.
x87 ↩
The floating-point unit architecture used in older Intel-compatible processors.

Reference links

Prior discussion and related questions

Knuth reward lore

Book access and reference text

Miscellaneous historical links