The binary Euclidean algorithm finds the GCD of two integers \(u\) and \(v\) using subtraction, shifting and parity testing. Unlike the classical Euclidean algorithm, no divisions are required. In this paper a continuous model of the binary algorithm is analysed, and the expected number of iterations is found. Suppose that \(u\) and \(v\) are initially odd integers chosen at random subject to \(0\leq v\leq u\leq N\). Let \(F_n(x)\) be the distribution function of \(x=\min(u,v)/\max(u,v)\) at the \(n\)th iteration (assuming \(N\to\infty\) so \(x\) is regarded as continuous rather than discrete). A recurrence relation for \(F_n(x)\) is found, and it is shown that \(F_n(x)\) has the form \(\alpha_n(x)\log_2x+\beta_n(x)\), where \(\alpha_n(x)\) and \(\beta_n(x)\) are analytic and regular at the origin, and satisfy certain recurrence relations. Assuming the existence of a limiting distribution \(F_\infty(x)\), it is shown that the expected number of iterations for the binary Euclidean algorithm is \(K\log_2N+O(1)\) as \(N\to\infty\), where \(K=0.705971246\dots\). For the classical Euclidean algorithm the corresponding constant is \(12(\ln(2)/\pi)^2 = 0.58416\dots\), but each iteration may be more expensive than for the binary algorithm. Comparisons with other variants of the Euclidean algorithm are also presented in the paper.
An interesting theoretical problem is to prove the existence of the limiting distribution \(F_\infty(x)\). For the classical algorithm the corresponding problem was posed by Gauss and proved by R. O. Kusmin (and sharper results were obtained by P. Lévy, P. Szüsz and E. Wirsing).
[For the entire collection see Zbl 0363.00013].