logoalt Hacker News

nk_koljayesterday at 8:18 PM1 replyview on HN

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.


Replies

as2j-1298yesterday at 8:39 PM

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!