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 <a href="https://news.ycombinator.com/item?id=26562819">https://news.ycombinator.com/item?id=26562819</a> 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.<p>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:<p><a href="https://www-cs-faculty.stanford.edu/~knuth/boss.html" rel="nofollow">https://www-cs-faculty.stanford.edu/~knuth/boss.html</a><p>(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.
You still get a physical piece of paper that looks like a check; it's just not a valid check.
Hopefully framed it and put it on the wall.
Wow, congratulations on finding this most epic bug!
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.<p>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.<p>"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."<p>That clearly a while loop. Lather, rinse, repeat.
That is so cool. Exceptional work, friend.<p>That makes this thread a bit more interesting now.<p><a href="https://stackoverflow.com/questions/60479571/is-there-a-bug-in-algorithm-4-3-1d-of-knuths-taocp" rel="nofollow">https://stackoverflow.com/questions/60479571/is-there-a-bug-...</a>
> "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!"<p>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!<p>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.
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)
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)<p>EDIT: I have added a different fallback font so it should work on your Firefox now.
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 use firefox and it renders approximately the same as Chrome for me.<p>Assuming OP didn't patch something, you may have a misbehaving extension.