Rendered at 18:58:15 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
nk_kolja 6 days ago [-]
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.
jason_s 1 days ago [-]
Congratulations! Wow, you got a legendary $2.56 check....
WillAdams 6 hours ago [-]
Unfortunately, one no longer gets physical checks, instead, one gets an account in The Bank of the Island of San Seriffe:
(unfortunately, I have yet to find another typo since getting my $2.88 for _Digital Typography_)
bluGill 4 hours ago [-]
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.
dhosek 2 hours ago [-]
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.
sandbach 2 hours ago [-]
Most people reading this would be hung on your wall?
philipallstar 2 hours ago [-]
After being framed, of course. You need to have a justification.
malisper 6 hours ago [-]
You still get a physical piece of paper that looks like a check; it's just not a valid check.
nk_kolja 5 hours ago [-]
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.
WillAdams 5 hours ago [-]
I wonder if one can do the reverse? Turn in a physical check and get an account?
actionfromafar 1 hours ago [-]
But but... that's all serif.
warmwaffles 6 hours ago [-]
Hopefully framed it and put it on the wall.
AndruLuvisi 4 hours ago [-]
Wow, congratulations on finding this most epic bug!
nickdrozd 5 minutes ago [-]
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?
enriquto 3 hours ago [-]
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.
hirvi74 16 minutes ago [-]
It's definitely up there. However, I really do enjoy the post linked below solely because of one particular comment chain.
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.
6 hours ago [-]
5 hours ago [-]
hirvi74 4 hours ago [-]
That is so cool. Exceptional work, friend.
That makes this thread a bit more interesting now.
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.
globular-toast 5 hours ago [-]
> "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...
ginko 6 hours ago [-]
The typesetting of this looks very broken on firefox with extreme gaps between lines of text. Seems to render fine on chromium.
nk_kolja 5 hours ago [-]
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.
Retr0id 5 hours ago [-]
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)
voakbasda 4 hours ago [-]
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).
ginko 4 hours ago [-]
Right, missing fonts could be the issue on my end.
metalliqaz 6 hours ago [-]
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.
While searching for vulnerable implementations I also found a "bug" in llvm, so I expanded a bit on that too.
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_)
⸻
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.
For me it will stay framed on the wall.
This bug is only in the English description of the algorithm, right? No bug in either the MIX or MMIX implementations?
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.
https://news.ycombinator.com/item?id=35015#35079
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.
That makes this thread a bit more interesting now.
https://stackoverflow.com/questions/60479571/is-there-a-bug-...
"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.
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...
EDIT: I have added a different fallback font so it should work on your Firefox now.
Assuming OP didn't patch something, you may have a misbehaving extension.