Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

kolja.rs

Post reply on HN
Print view View original

21–30 of 55 posts

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

#21

Post by vjerancrnjak »

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.

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

#22

Post by rna-mall »

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̂ That clearly a while loop. Lather, rinse, repeat.

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

#23

Post by enriquto »

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.

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

#24

Post by sandbach »

bluGill wrote: post #19
WillAdams wrote: post #5

Earlier quoted context omitted.

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.

Most people reading this would be hung on your wall?

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

#25

Post by philipallstar »

sandbach wrote: post #24
bluGill wrote: post #19

Earlier quoted context omitted.

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.

Most people reading this would be hung on your wall?

After being framed, of course. You need to have a justification.

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

#26

Post by dhosek »

bluGill wrote: post #19
WillAdams wrote: post #5

Earlier quoted context omitted.

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.

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

#27

Post by actionfromafar »

WillAdams wrote: post #5
jason_s wrote: post #3

Earlier quoted context omitted.

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

But but... that's all serif.

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

#28

Post by hirvi74 »

enriquto wrote: post #23

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 2…

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

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

#29

Post by nickdrozd »

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?

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

#30

Post by WalterBright »

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.

Post reply on HN