Complete Analysis of the Binary GCD Algorithm
Brigitte Vallée
Université de Caen
Algorithms Seminar
April 27, 1998
[summary by Cyril Banderier]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
1 Introduction
The analysis of the classical Euclidean algorithm
has been performed by Heilbronn [4] and Dixon [3], using different approaches.
For a random pair of rational numbers, the average number of divisions is
Here, we will analyse the binary Euclidean algorithm, which uses only
subtractions and right binary shifts. This ``binary GCD algorithm'' takes as
input a pair of odd integers (u,v) from the set
W={(u,v) odd, 0<u £ v}.
Then the GCD is recursively defined by
ì ï í ï î 
gcd(u,v)=gcd 
æ ç ç ç è 

,v 
ö ÷ ÷ ÷ ø 

gcd(u,v)=gcd(v,u) 

where Val_{2}(n) is the greatest integer b such 2^{b} divides n,
i.e., the dyadic valuation of n.
The corresponding binary GCD algorithm is as follows:

while u¹ v do

while u<v do

b:=Val_{2}(vu);
 v:=(vu)/2^{b};
 end;
 exchange u and v;
 end;
 return u.
Example 1
If the input is (u,v):=(7,61) then
b:=Val_{2}(617)=1. Thus v:=54/2^{1}=27,
and the algorithm continues because u<v.
Now b:=Val_{2}(277)=2. Thus v:=20/2^{2}=5.
Now the algorithm restarts with (u,v):=(5,7).
It leads to v:=(75)/2^{1}=1 and therefore one restarts with (u,v):=(1,5)
which leads to v=1=u so the algorithm stops
and returns u, namely 1 (as expected since 7 and 61 are coprime).
One can write:
In general, for each ``inner while loop'', one has
where x_{i}:=u/v (with (u,v) as in the beginning of the loop),
x_{i+1}:=u/v (with (u,v) as after the exchange), where
a_{i}:=1+2^{b}_{1}+2^{b}_{1}^{+b}_{2}+...+2^{b}_{1}^{+...+b}_{l1}
and k_{i}:=b_{1}+...+b_{l1}+b_{l}
(the sum of all the b's obtained during the ith inner while loop).
The algorithm thus produces the following binary continued fraction expansion
Three interesting parameters are:

r, the depth of the continued fraction or equivalently the number of outer loops performed;
 å_{i=1}^{r} n(a_{i}), the number of subtractions (where n(w) is the number of 1's in the binary expansion of the integer w);
 å_{i=1}^{r} k_{i}, number of rights shifts performed or equivalently inner loop executions.
Their average values on the set
W_{n}={(u,v) odd, 0<u £ v £ n}
are respectively noted E_{n}, P_{n} and S_{n}.
Note that E_{n} is also the average number of exchanges in the algorithm, and
that P_{n} is the average number of operations that are necessary to obtain
the expansion.
2 A Ruelle Operator for a Tauberian Theorem
In order to establish that these three parameters have averages that are
asymptotic to log n,
we introduce the following Ruelle operator:
V_{s}[f](x):= 





f 
æ ç ç è 

ö ÷ ÷ ø 
. 
The average E_{n} is easily expressed in term of V_{s},
with the help of the following definitions:
F(s):=(IdV_{s})^{1}[Id](1), G(s):=(IdV_{s})^{2} ° V_{s}[Id 
](1),


(s):= 



= 
æ ç ç è 
1 

ö ÷ ÷ ø 
z(s). 
Proposition 1
E_{n} is a ratio of partial sums of the two Dirichlet series
z^{~}(s) F(s) and z^{~}(s) G(s).
Proof.
Let W^{[l]} be the subset of W for which the algorithm performs exactly l exchanges. Then,
V_{s}^{l}[f](1)= 



f 
æ ç ç è 

ö ÷ ÷ ø 
. 
Summing over all the possible heights (l³ 0) yields:
(Id 
w V_{s})^{1}[f](1)= 

w^{l} V_{s}^{l}[f](1) = 



f 
æ ç ç è 

ö ÷ ÷ ø 
. 
Differentiating with respect to w, and then choosing f=1 and w=1 yields
E_{n}= 



l  W_{n}^{[l]}
= 

. 
The proof is completed by observing that
F(s)= 





v_{k}^{[l]},
G(s)= 





l v_{k}^{[l]}.

The key is now to prove that the following theorem may be used:
Theorem 1 [Tauberian theorem]
If F(s) is a Dirichlet series with nonnegative coefficients
that is convergent for Â(s)>s>0 and if

F is analytic on the line Â(s)=s except at s=s;
 F(s)=A(s)/(ss)^{g+1}+C(s) where A,C are
analytic at s (with A(s) ¹ 0);
then one has, as n ® ¥,

a_{k} = 

n 

log 

n (1+e(n)), 
where e(n) ® 0.
Proof.
See Delange [2].
Lemma 1
The Tauberian theorem applies to F with s=2 and g=0.
Proof.
Indeed
F(s):=(IdV_{s})^{1}[Id](1)=1+ 





= 


æ ç ç ç ç ç è 

+1 
ö ÷ ÷ ÷ ÷ ÷ ø 
. 
The last member of the equality clearly satisfies the conditions of
the Tauberian theorem, and the same holds for z^{~}F
with s=2 and g=0.
Lemma 2
The Tauberian theorem applies to G with s=2 and g=1.
Proof.
Here lies the complex part of Brigitte Vallée's proof. It is impossible to
conclude as quickly as in lemma 1, indeed, this time we need to find an
appropriate functional space on which V_{s} is a compact operator. A mixture of
various functional analysis theorems (FejerRiesz' inequality, Gabriel's
inequality, Krasnoselsky's theorem and other works by Shapiro and Grothendieck)
show that it is the case on the Hardy space H^{2}(D), where D is an open disk
containing ]0,1]. This leads to the fact that for s>3/2, V_{s} has a unique
positive dominant eigenvalue, equal to 1 when s=2. In addition V_{s} has a
spectral radius <1 on Â(s)³ 2, s¹ 2. Thus (IdV_{s})^{1}
is regular on the domain D and condition 1 of the Tauberian
theorem is fulfilled. Condition 2 is proved by means of perturbation theory
applied to V_{s}=P_{s}+N_{s} (P_{s} is the projection of V_{s} on
the dominant eigensubspace), in a neighbourhood of s=2.
See [7] for a detailed proof.
This implies the following fundamental result:
Theorem 2
The average number of exchanges of the binary Euclidean algorithm on W_{n}
is
where f_{2} is the fixed point of the operator V_{2}
that is normalised by ò_{0}^{1} f_{2}(t) dt =1.
3 The Other Two Parameters
In order to study the other two parameters (total number of subtractions,
total number of shifts)
one still uses the Tauberian theorem but with a more intricate
Ruelle operator, see Vallée [7].
This leads to the following two results.
Theorem 3
The average number of total iterations is
P_{n} ~ A log n with A:= 





F_{2} 
æ ç ç è 

ö ÷ ÷ ø 
where f_{2} is defined as above, F_{2}(x):=ò_{0}^{x} f_{2}(t) dt, F_{2}(1)=1
(where k_{a} is the integer part of log_{2} a).
Theorem 4
The average number of the sum of exponents of 2 used in the numerators
of the binary continued fraction expansions, i.e., average total number
of right shifts is
S_{n} ~ 


æ ç ç ç è 
2 



F_{2} 
æ ç ç è 

ö ÷ ÷ ø 
ö ÷ ÷ ÷ ø 
log n. 
4 All Roads Lead to Rome
In Brent's paper [1], one can find a different approach which suggests that
P_{n} ~ 

log n where
M=log 2 


ó õ 

log (1x) g_{2}(x) dx 
and
where g_{2} is the fixed point (and normalised as f_{2}) of
B_{2}[f](x):= 



^{2}
f 
æ ç ç è 

ö ÷ ÷ ø 
+ 



^{2} f 
æ ç ç è 

ö ÷ ÷ ø 
. 
Unfortunately, this approach is based on a heuristic
hypothesis (exercise 36, section 4.5.2, rated HM49 by Knuth in [5]).
Brigitte Vallée explored this approach
with a Brent operator B_{s},
without heuristic arguments but providing a spectral conjecture holds,
this leads to the following result:
P_{n} ~ B log n where B:= 

. 
The miracle holds and, after numerical experiments,
A=1/M=B=1.0185....
But nobody has proved these equalities.
We can also note that a similar method was used by Brigitte
Vallée and one of her students to analyse
the Jacobi symbol algorithm [6].
Finally, the binary Euclidian algorithm is only a slight variation on one of
the oldest known algorithms but there is still some unknown
territories in its ``complete'' analysis!
References
 [1]

Brent (Richard P.). 
Analysis of the binary Euclidean algorithm. In Algorithms and
complexity, pp. 321355. 
Academic Press, New York, 1976. Proceedings of a
Symposium held at CarnegieMellon University, 1976.
 [2]

Delange (Hubert). 
Généralisation du théorème de Ikehara. Annales
Scientifiques de l'École Normale Supérieure, vol. 71, n°3,
1954, pp. 213242.
 [3]

Dixon (John D.). 
The number of steps in the Euclidean algorithm. Journal of
Number Theory, vol. 2, 1970.
 [4]

Heilbronn (H.). 
On the average length of a class of finite continued fractions. In
Number Theory and Analysis (Papers in Honor of Edmund Landau),
pp. 8796. 
Plenum, New York, 1969.
 [5]

Knuth (Donald E.). 
The Art of Computer Programming. 
AddisonWesley, 1997, third edition, vol. 2.
 [6]

Lemée (Charlie) and Vallée (Brigitte). 
Analyse des algorithmes du symbole de Jacobi. GREYC,
1998.
 [7]

Vallée (Brigitte). 
The complete analysis of the binary Euclidean algorithm. In Proceedings ANTS'98. 
1998.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.