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 recently 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).
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