... 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 <= 2 in the text..
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!
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.
Comments
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 <= 2 in the text..
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!
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.