Abstract: dvi (5K), pdf (109K).
Paper: pdf (1196K).
We introduce another binary Euclidean algorithm, the "left-shift" algorithm, and consider its expected behaviour on random inputs. The expected number of iterations for the left-shift algorithm is slightly greater than for the right-shift algorithm, but the left-shift algorithm is worth considering for use on a computer with a "normalize" instruction, as then the left-shifting loop may be replaced by a single instruction. Either of the binary algorithms could be implemented in hardware (or microcode) with approximately the same expense as integer division.
The probabilistic assumptions of the paper were justified by Vallée (1998): see Brent  for a summary and references.
The existence and uniqueness of a limiting distribution (conjectured in the paper) has been proved by Gerard Maze, J. Discrete Algorithms 5 (2007), 176-186; see also http://www.arxiv.org/abs/math.GM/0504426 (21 April 2005).
Further progress has been made recently by Ian Morris, paper to appear in Advances in Mathematics (preprint at http://arxiv.org/abs/1409.0729, 2 Sept 2014). In particular, Morris shows the existence of a spectral gap and a unique continuous density for the transfer operator. He deduces three conjectured formulae for the expected number of steps, resolving several open questions.
Page 342, equation (6.3): In equation (6.3) on page 342, "x" in the denominator of the last term should be replaced by "1". [Correction made in the online version.]
Some of the results are incorrect. For example, (3.1), (3.29), (3.34), and (3.35) are wrong, though a close approximation to the truth. [Corrections not made in the online version.]
Further details are given in . See also Section 4.5.2 of Knuth, The Art of Computer Programming, Volume 2, third edition, 1997.
Go to next publication
Return to Richard Brent's index page