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.
- WalterBright
Back in the 1980s, before there was a DIV instruction, I implemented integer division.
I used the same long division algorithm I was taught in 3rd grade, except in binary rather than base 10. Shift and subtract.
It was also the basis for implementing FDIV (floating point division) for those who did not have an x87 chip.
Nobody ever reported a bug in it.
- enriquto
This may very well be the most epic post in HN history.
EDIT : I recall fondly algorithm D... one of my first programming experiences in the 90s was trying to implement knuth's arithmetic algorithms for addition, substraction, etc. in 8086 asm. Got them right up until long multiplication (that one was a tremendous effort). Algorithm D was too formidable to even dare me attempt. Feel extremely happy to see people in 2026 looking at these algorithms closely.
- nickdrozd
Congratulations! It's funny that the reward schedule is not based on importance. It's just 0x$1.00 for an error and 0x$0.20 for a suggestion, no matter what. Personally I have 0x$4.40 in the bank, more than the author's 0x$1.00, but none of my four errors and two suggestions were as important as this one. Getting your name in the book is pretty cool though!
This bug is only in the English description of the algorithm, right? No bug in either the MIX or MMIX implementations?
- seekup
A story from my life about not judging a book by its cover...and Algorithm D:
Some years after the turn of the millennium I was a CS student at UC Santa Cruz. I was taking various classes for my major and I ended up in a Comparative Programming Languages class, which was a quarter-long survey of different modalities - I remember Haskell, OCaml, C++, and there were maybe two others.
Anyway I had started noticing a particular student showing up in some of my classes. He stood out. Firstly because he was always asking questions, sometimes to the point of annoying other students. And then because he was older than the rest of us - in hindsight he probably wasn't older than his early 40s - but I was ~20 and as I came to learn, he'd lived hard. He had a stout, platinum blonde beard that seemed yellowed from the hand-rolled cigarettes I always saw him smoking outside the computer lab.
After class one day I started chatting with him. I wasn't much of a question-asker, and I found his willingness to do so in the face of obvious annoyance to actually be kind of brave, so I think I probably opened by complimenting him and asking if the reactions from other students bothered him. His answer, gravely-voiced, was clear: he was paying for these classes same as anyone else, and he wanted to get his money's worth. I found it a refreshingly self-centered take. I decided I liked the guy.
Over time we became lab-mates, working on projects together. He always reeked of tobacco; his fingers […]