Live data from Hacker News

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

kolja.rs

51–55 of 55 posts

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

#51

Earlier quoted context omitted.

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

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.

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

#52
post #48

Earlier quoted context omitted.

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.

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

#53

Earlier quoted context omitted.

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

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

[deleted]

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

#54
post #50
post #49

Earlier quoted context omitted.

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.

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

#55

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

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.

Post reply on HN