I got through only part of reducing long division to medium division before I couldn’t understand the nomenclature being used in the algorithms. If I picked up TAOCP from the begging does it help you get to the point of reading this or is there other prerequisites you need.
A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
41–50 of 55 posts
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#42Earlier quoted context omitted.
I beg to differ. A loop would also call for additional run-time analysis. And Knuth changed Step D3, if it were a loop he wouldn't have had to. Additionally, there is no loop in Program D, his implementation of Algorithm D in MIX. If you read the whole chapter and not just the statement itself (though I'd argue the statement is enough), it's very clearly two if's.
In the edition here (I also have a legal hard copy but not with me)... https://www.scribd.com/document/956350280/The-Art-of-Compute... ... on page 274 the MIX jumps in lines 058 and 060 to label 3H if the tests fail, where qhat is decremented again. I'm not at all a Mix expert, but where is the counter that the loop is only executed twice?
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.
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#43I got through only part of reducing long division to medium division before I couldn’t understand the nomenclature being used in the algorithms. If I picked up TAOCP from the begging does it help you get to the point of reading this or is there other prerequisites you need.
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.
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#44> "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…
I'm happy to see someone commenting on Knuth's note.
Don't worry, you probably won't need to correct anything unless you have a computer with an odd radix :)
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#45Given enough tokens, all bugs are shallow.
I doubt it would have unlooped itself from re-counting the steps in Program D and calculating the complexity of the algorithm. I couldn't get it to do it with a weeks worth of Claude pro, and in my experience once it's stuck it's stuck.
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#46Earlier quoted context omitted.
In the edition here (I also have a legal hard copy but not with me)... https://www.scribd.com/document/956350280/The-Art-of-Compute... ... on page 274 the MIX jumps in lines 058 and 060 to label 3H if the tests fail, where qhat is decremented again. I'm not at all a Mix expert, but where is the counter that the loop is only executed twice?
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 <= 3!
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#47A story from my life about not judging a book by its cover...and Algorithm D: Some years after the turn of the millennium I was a CS student at UC Santa Cruz. I was taking various classes for my major and I ended up in a Comparative Programming Languages class, which was a quarter-long survey of different modalities - I remember Haskell, OCaml, C++, and there were maybe two others. Anyway I had started noticing a par…
What a lovely story
thank you, and a big congrats on your bounty!
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#48I got through only part of reducing long division to medium division before I couldn’t understand the nomenclature being used in the algorithms. If I picked up TAOCP from the begging does it help you get to the point of reading this or is there other prerequisites you need.
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.
Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#49Re: A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
#50Earlier quoted context omitted.
After being framed, of course. You need to have a justification.
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.