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

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.

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.

Great find and write up. This year if I remember correctly 40+ people got the check, ~1000 have an account at the bank. I got mine this year, an exercise I revisit every few years since 2012 to learn a new programming lang or approach had a newer update that made it have 2 offbyone errors. I had extra time this year so went to the beginning of the chapter to attempt an open problem and in the preliminaries another off by two error. I was quite surprised.

Really made me appreciate how unlikely it is to find an error. It feels as if it was planned just for me to find it. Just like the author studied cryptography and then decided to do some exercises to hone his skills, an unlikely journey towards a check.

Nice work! I don't find all implementations using "while" or "goto loop" surprising though.

"Now test if q̂ ≥ b or q̂·vₙ₋₂ > b·r̂ + uₙ₋₂; if so, decrease q̂ by 1, increase r̂ by vₙ₋₁, and repeat this test if r̂ < b."

That clearly a while loop. Lather, rinse, repeat.

That is so cool. Exceptional work, friend.

That makes this thread a bit more interesting now.

https://stackoverflow.com/questions/60479571/is-there-a-bug-...

> "I'm especially glad to have this correction, because I think the readers of TAOCP Vol 2 look at Algorithm 4.3.1 D more than any other algorithm!"

If you look at the fore edge of my copy of vol 2 will see a noticeably grubby line. Open the book at that page and you do indeed arrive at Algorithm D!

I've implemented multiple-precision arithmetic at least a couple of times. I'm tempted to dig up an old project I haven't touched for over a decade and make the correction...

The typesetting of this looks very broken on firefox with extreme gaps between lines of text. Seems to render fine on chromium.