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

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 day ago

Congratulations! Wow, you got a legendary $2.56 check....

WillAdams•about 2 hours ago

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_)

malisper•about 2 hours ago

You still get a physical piece of paper that looks like a check; it's just not a valid check.

warmwaffles•about 2 hours ago

Hopefully framed it and put it on the wall.

AndruLuvisi•22 minutes ago

Wow, congratulations on finding this most epic bug!

globular-toast•about 1 hour 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•about 2 hours ago

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

voakbasda•33 minutes 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).

Retr0id•about 2 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)

nk_kolja•about 1 hour 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.

metalliqaz•about 2 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.

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

⚡ Community Insights

Discussion (14 Comments)Read Original on HackerNews