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.
I have at least one Knuth check¹ from the days when they were actual checks, but to be honest, I’m not 100% sure where it (they?) are. I’m on the mailing list where potential TeX-related bugs appear and it’s crazy the level of detail people go to in looking for any remaining bugs in that software.
⸻
1. I know at least one of these came from porting lesser-known utilities to VM/CMS. By that time, DEK already had adopted a practice of having his secretary print his emails and he’d hand-write a reply and you’d get it in the mail.
Wait, I thought I was going to frame you, but it turns out you're you're blackmailing me. I don't have to frame you anymore. I have evidence of a real crime.
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.
> "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...
I'm happy to see someone commenting on Knuth's note.
Don't worry, you probably won't need to correct anything unless you have a computer with an odd radix :)
Wow I had forgotten that I had answered that question on StackOverflow!
So at the time my conclusion had been that there was no mistake (interpreting the "repeat" as a loop), but it's arguable… maybe if the person who posted the question had asked Knuth instead, he'd have had a reward check?
Thank you! Indeed it's the infamous Step D3. In my opinion, with the new changes and the new Theorem B, this step will feel more natural, because it's essentially extending the 2/1 division into a 3/2 division.
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.
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?
Honestly, while waiting for the check I wondered what it would be, and 0x$1.00 feels just right. The name in the book came unexpectedly, it's really a reward on its own.
No bug in MIX, and there is no MMIX implementation yet. The transition of the first three volumes from MIX to MMIX is still far ahead.
The MIX program actually implements Step D3 differently from what's written in Algorithm D, and this implementation, more aligned with 1st and 2nd editions of the book, avoids the error. The bug is due to a 1995 change in the trial quotient computation (that from my perspective came as part of a transition to MMIX). This broke correctness of Theorem B, which then led to overflows post Step D3 (in only one peculiar, rare, odd case).
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 too were yellowed from those rollies. I learned that he'd never finished college his first time around, instead getting hired into industry and riding the wave of the dot-com boom. When the crash eventually landed, he washed out and found himself living the surf bum life in Mexico, soaked in alcohol and seawater. When he eventually decided he had to get his life together, he sobered up and moved back to the States. But he was unemployed, homeless - living out of his VW van - and a 40-something college student. He was a misfit.
So, let's see..right, Algorithm D. So for our Comparative Languages class, the OCaml project was an arbitrary-precision calculator. We worked through addition, subtraction, and multiplication, and then as the project deadline approached we turned our sights towards division. Me, I took one look at Knuth and decided to start instead with a brute-force implementation. But once that worked, we began tackling Algorithm D. Around 2am, still not done, I threw up my hands and said I was going home - I'd take whatever grade was coming. My partner also went home - to his van parked in the Engineering lot. I knew he didn't own his own computer, so imagine my surprise when I saw him the next day and he told me he had finished the Algorithm D implementation overnight.
Turned out he had gone back to his van that night with a pen and a ream of paper and worked the code out by hand, only typing it up in the morning. We were lab partners but I wasn't going to copy something I'd had no hand in; I got whatever grade I deserved and he got the perfect score. I'm sure the older heads have plenty of stories of coding by hand, but even by that time, circa 2005, such a thing seemed arcane, almost unheard of. I was duly impressed.
I occasionally wonder what happened to him - he was a smart guy and a good engineer, and I learned some important lessons from him. I hope he found his footing. And for the sake of his cubicle mates, maybe also kicked the cigarette habit.
A loop would also call for additional run-time analysis. And Knuth changed Step D3, if it were a loop he wouldn't have had to. Additionally, there is no loop in Program D, his implementation of Algorithm D in MIX.
If you read the whole chapter and not just the statement itself (though I'd argue the statement is enough), it's very clearly two if's.
... on page 274 the MIX jumps in lines 058 and 060 to label 3H if the tests fail, where qhat is decremented again. I'm not at all a Mix expert, but where is the counter that the loop is only executed twice?
You are absolutely right. My mistake, the MIX computed the trial quotient in step 043 in a saturated way (which was enough to control the bug, thus my comment). It does indeed loop at step 62-64 (third edition book labels).
I nevertheless stand my ground on the intention of Step D3.
Colloquially "repeat" means "repeat once", but in the algorithm sense it means go back to the beginning of the block I think.
I think Knuth originally wanted a loop but obviously needed a proof that it terminates and does not waste too many iterations. That is why he mentions <= 2 in the text..
I mean, as you say, every implementation apart from LLVM understood the text as a loop.
Anyway, extremely nice work to correct Theorem B to <= 3!
I was curious so checked to see how I implemented it in 2010. I did indeed use a while loop with a conditional break for the "repeat this test if" part. It just seems like the obvious implementation in C, to be honest. The book Hacker's Delight implements it more literally as an implicit loop using goto, but I was taught not to use goto and probably followed that rule at the time.
I don't think I interpreted it as strictly a loop, though, because normally that's a bigger deal and not casually hidden in one step of an algorithm. Algorithm M, for example has the loop parts annotated as such and always "go back to step M3" etc. My copy also has a comment in step D3 saying the test eliminates all cases where the guess is two too large, to it's completely understandable to not interpret it as a loop IMO.
I got through only part of reducing long division to medium division before I couldn’t understand the nomenclature being used in the algorithms. If I picked up TAOCP from the begging does it help you get to the point of reading this or is there other prerequisites you need.
It probably wouldn't help, and TAOCP from the beginning is too many pages.
It would help to read the division algorithm chapter.
I introduce my own notation from medium->small division onwards. If it's any help u'', v'' are the limbs that the division instruction sees (the ones pertinent to qhat) and u',v' are all the lower limbs.
Get a copy of Vol 2 and read section 4.1 - Positional number systems - before tackling 4.3 - Multiple-precision arithmetic. It will give you the necessary grounding and notation. It's also an absolutely fascinating topic and will change the way you think about numbers.
If you have vol 2 you also might as well read at least the intro to chapter 3 which is beautiful.
I doubt it would have unlooped itself from re-counting the steps in Program D and calculating the complexity of the algorithm. I couldn't get it to do it with a weeks worth of Claude pro, and in my experience once it's stuck it's stuck.
Thank you for letting me now, but I cannot replicate the issue on Firefox.
There are some issues with math and the animations not breaking on mobile, which I am working on repairing. (fixed)
EDIT: I have added a different fallback font so it should work on your Firefox now.
It renders fine for me, but I've also had the "extreme gaps between lines" thing happen before on Firefox, and in my case it was caused by a bad font fallback - I forget the precise details but I think it had something to do with having Arabic fonts installed, which were erroneously taking preference for certain non-arabic glyphs. (Check the Fonts tab in dev tools)
I believe this is a missing font issue, whereupon Firefox chooses very poor substitutes. I ran into this recently on one of my machines and solved it by installing the Microsoft fonts package (or possibly another one… I can’t remember now exactly which one did the trick).
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.
Congratulations! Wow, you got a legendary $2.56 check....
Unfortunately, one no longer gets physical checks, instead, one gets an account in The Bank of the Island of San Seriffe:
https://www-cs-faculty.stanford.edu/~knuth/boss.html
(unfortunately, I have yet to find another typo since getting my $2.88 for _Digital Typography_)
Close enough. If I ever got such a check it would be professionally framed and hung on my wall. As would most people reading this.
I have at least one Knuth check¹ from the days when they were actual checks, but to be honest, I’m not 100% sure where it (they?) are. I’m on the mailing list where potential TeX-related bugs appear and it’s crazy the level of detail people go to in looking for any remaining bugs in that software.
⸻
1. I know at least one of these came from porting lesser-known utilities to VM/CMS. By that time, DEK already had adopted a practice of having his secretary print his emails and he’d hand-write a reply and you’d get it in the mail.
Most people reading this would be hung on your wall?
After being framed, of course. You need to have a justification.
I heard philipallstar and sandbach were doing treason.
@bluGill, you owe me some money or this framing won't be professional. ;)
Wait, I thought I was going to frame you, but it turns out you're you're blackmailing me. I don't have to frame you anymore. I have evidence of a real crime.
This is some very unprofessional framing.
You still get a physical piece of paper that looks like a check; it's just not a valid check.
It can still be cashed in, though not in any bank, you need to contact Knuth beforehand.
For me it will stay framed on the wall.
I wonder if one can do the reverse? Turn in a physical check and get an account?
But but... that's all serif.
Hopefully framed it and put it on the wall.
Wow, congratulations on finding this most epic bug!
Thank you!
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.
It's definitely up there. However, I really do enjoy the post linked below solely because of one particular comment chain.
https://news.ycombinator.com/item?id=35015#35079
Thank you, i'm flattered!
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.
> "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...
I'm happy to see someone commenting on Knuth's note. Don't worry, you probably won't need to correct anything unless you have a computer with an odd radix :)
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-...
Wow I had forgotten that I had answered that question on StackOverflow!
So at the time my conclusion had been that there was no mistake (interpreting the "repeat" as a loop), but it's arguable… maybe if the person who posted the question had asked Knuth instead, he'd have had a reward check?
Thank you! Indeed it's the infamous Step D3. In my opinion, with the new changes and the new Theorem B, this step will feel more natural, because it's essentially extending the 2/1 division into a 3/2 division.
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.
What a nice comment. Indeed, it feels like it was just waiting for you to find it.
That is a rather nice ritual, I think I will use it now to motivate myself to learn Scala.
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?
Thank you!
Honestly, while waiting for the check I wondered what it would be, and 0x$1.00 feels just right. The name in the book came unexpectedly, it's really a reward on its own.
No bug in MIX, and there is no MMIX implementation yet. The transition of the first three volumes from MIX to MMIX is still far ahead. The MIX program actually implements Step D3 differently from what's written in Algorithm D, and this implementation, more aligned with 1st and 2nd editions of the book, avoids the error. The bug is due to a 1995 change in the trial quotient computation (that from my perspective came as part of a transition to MMIX). This broke correctness of Theorem B, which then led to overflows post Step D3 (in only one peculiar, rare, odd case).
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 too were yellowed from those rollies. I learned that he'd never finished college his first time around, instead getting hired into industry and riding the wave of the dot-com boom. When the crash eventually landed, he washed out and found himself living the surf bum life in Mexico, soaked in alcohol and seawater. When he eventually decided he had to get his life together, he sobered up and moved back to the States. But he was unemployed, homeless - living out of his VW van - and a 40-something college student. He was a misfit.
So, let's see..right, Algorithm D. So for our Comparative Languages class, the OCaml project was an arbitrary-precision calculator. We worked through addition, subtraction, and multiplication, and then as the project deadline approached we turned our sights towards division. Me, I took one look at Knuth and decided to start instead with a brute-force implementation. But once that worked, we began tackling Algorithm D. Around 2am, still not done, I threw up my hands and said I was going home - I'd take whatever grade was coming. My partner also went home - to his van parked in the Engineering lot. I knew he didn't own his own computer, so imagine my surprise when I saw him the next day and he told me he had finished the Algorithm D implementation overnight.
Turned out he had gone back to his van that night with a pen and a ream of paper and worked the code out by hand, only typing it up in the morning. We were lab partners but I wasn't going to copy something I'd had no hand in; I got whatever grade I deserved and he got the perfect score. I'm sure the older heads have plenty of stories of coding by hand, but even by that time, circa 2005, such a thing seemed arcane, almost unheard of. I was duly impressed.
I occasionally wonder what happened to him - he was a smart guy and a good engineer, and I learned some important lessons from him. I hope he found his footing. And for the sake of his cubicle mates, maybe also kicked the cigarette habit.
What a lovely story
thank you, and a big congrats on your bounty!
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.
I beg to differ.
A loop would also call for additional run-time analysis. And Knuth changed Step D3, if it were a loop he wouldn't have had to. Additionally, there is no loop in Program D, his implementation of Algorithm D in MIX.
If you read the whole chapter and not just the statement itself (though I'd argue the statement is enough), it's very clearly two if's.
In the edition here (I also have a legal hard copy but not with me)...
https://www.scribd.com/document/956350280/The-Art-of-Compute...
... on page 274 the MIX jumps in lines 058 and 060 to label 3H if the tests fail, where qhat is decremented again. I'm not at all a Mix expert, but where is the counter that the loop is only executed twice?
You are absolutely right. My mistake, the MIX computed the trial quotient in step 043 in a saturated way (which was enough to control the bug, thus my comment). It does indeed loop at step 62-64 (third edition book labels). I nevertheless stand my ground on the intention of Step D3.
Colloquially "repeat" means "repeat once", but in the algorithm sense it means go back to the beginning of the block I think.
I think Knuth originally wanted a loop but obviously needed a proof that it terminates and does not waste too many iterations. That is why he mentions <= 2 in the text..
I mean, as you say, every implementation apart from LLVM understood the text as a loop.
Anyway, extremely nice work to correct Theorem B to <= 3!
I was curious so checked to see how I implemented it in 2010. I did indeed use a while loop with a conditional break for the "repeat this test if" part. It just seems like the obvious implementation in C, to be honest. The book Hacker's Delight implements it more literally as an implicit loop using goto, but I was taught not to use goto and probably followed that rule at the time.
I don't think I interpreted it as strictly a loop, though, because normally that's a bigger deal and not casually hidden in one step of an algorithm. Algorithm M, for example has the loop parts annotated as such and always "go back to step M3" etc. My copy also has a comment in step D3 saying the test eliminates all cases where the guess is two too large, to it's completely understandable to not interpret it as a loop IMO.
I got through only part of reducing long division to medium division before I couldn’t understand the nomenclature being used in the algorithms. If I picked up TAOCP from the begging does it help you get to the point of reading this or is there other prerequisites you need.
It probably wouldn't help, and TAOCP from the beginning is too many pages. It would help to read the division algorithm chapter.
I introduce my own notation from medium->small division onwards. If it's any help u'', v'' are the limbs that the division instruction sees (the ones pertinent to qhat) and u',v' are all the lower limbs.
I appreciate the info but it’s unfortunately no help.
I have a passing interest in mathematics and especially comp sci but I routinely find myself stymied just by trying to understand the notation.
Get a copy of Vol 2 and read section 4.1 - Positional number systems - before tackling 4.3 - Multiple-precision arithmetic. It will give you the necessary grounding and notation. It's also an absolutely fascinating topic and will change the way you think about numbers.
If you have vol 2 you also might as well read at least the intro to chapter 3 which is beautiful.
Given enough tokens, all bugs are shallow.
I doubt it would have unlooped itself from re-counting the steps in Program D and calculating the complexity of the algorithm. I couldn't get it to do it with a weeks worth of Claude pro, and in my experience once it's stuck it's stuck.
The typesetting of this looks very broken on firefox with extreme gaps between lines of text. Seems to render fine on chromium.
Thank you for letting me now, but I cannot replicate the issue on Firefox. There are some issues with math and the animations not breaking on mobile, which I am working on repairing. (fixed)
EDIT: I have added a different fallback font so it should work on your Firefox now.
It renders fine for me, but I've also had the "extreme gaps between lines" thing happen before on Firefox, and in my case it was caused by a bad font fallback - I forget the precise details but I think it had something to do with having Arabic fonts installed, which were erroneously taking preference for certain non-arabic glyphs. (Check the Fonts tab in dev tools)
I believe this is a missing font issue, whereupon Firefox chooses very poor substitutes. I ran into this recently on one of my machines and solved it by installing the Microsoft fonts package (or possibly another one… I can’t remember now exactly which one did the trick).
Right, missing fonts could be the issue on my end.
I use firefox and it renders approximately the same as Chrome for me.
Assuming OP didn't patch something, you may have a misbehaving extension.