Average BitComplexity of Euclidean Algorithms
Brigitte Vallée
GREYC, Université de Caen
Algorithms Seminar
May 22, 2000
[summary by Marni Mishna]
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).
Abstract
The complexity the Euclidean algorithm and its variants is well
studied. This work refines the problem further by considering precise
average bitcomplexity. The technique is sufficiently general as to
apply to a wide class of gcdtype algorithms. It determines elementary
transformations for each algorithm and derives asymptotic information
from their analytic behaviour. The methods rely on properties of
transfer operators adapted from dynamical systems theory. The use of
Ergodic Theorems in the continuous case (continued fraction
algorithms) foreshadows the results, which use Tauberian Theorems as
replacement. This is joint work with Ali Akhavi
[1].
1 Why the Bit Case?
Since the initial average case analysis of the Euclidean algorithm in
1969 by Heilbronn and Dixon a wide variety of approaches have been
used to examine variants, the most recent of which is the
method of using transfer operators [3, 4].
The technique involves viewing the algorithm as a dynamical system and
each iterative step as a linear fractional transformation
(LFT). Previous talks by the speaker [2] shed some light
on this technique, how several classes of GCD algorithms fell under
a unified approach and furthermore, why they were naturally divided
into two categories: slow (Q(log^{2} n)) and fast (Q(log n)).
This same technique will now aid in the study of bitwise
complexity. The motivation for this refinement is the following. It is
not a priori evident whether the properties which make the slow
algorithms slow extend to the bit case. It is true that there are more
iterations, but what of the size of each iteration? This work answers
the question definitively, yielding the same divisions between slow
and fast algorithms, however with new complexity descriptions,
Q(log^{3}n) and Q(log^{2}n). Furthermore, it is of interest to
consider a practical complexity measure. The method offers precise
insights on the distribution of costs. This enables a further
refinement on the classification between the fast and slow algorithms.
1.1 Standard algorithm
The standard Euclidean algorithm determines the gcd of v_{0} and v_{1}
by a finite number of steps of the form v_{i}=m_{i}v_{i1} +v_{i+1},
with final step v_{k}=0. Define l(x)=ëlog_{2} xû +1, the
binary length of x. At each step there is one ``naive'' division
with bit cost l(v_{i})l(m_{i}), and two assignment steps involving v_{i}
and v_{i+1}. The total bitcomplexity of one iteration is
l(v_{i})l(m_{i})+l(v_{i})+l(v_{i+1}). The cost for the standard algorithm
is then
C(v_{1}, v_{0})= 

l(v_{i})· 
( 
l(m_{i})+2 
) 
. 
2 Main Result: BitWise Complexity
The following two sets are valid input to the Euclidean
algorithm:
W={ (u,v)
gcd(u,v)=1, 1£ u<v } and W_{N}={ (u,v) (u,v)Î
W, v£ N }.
The goal is to estimate the mean value of a cost
C:W® R on W_{N}. More precisely, to determine
the asymptotic value as N®¥ of the mean value
E_{N}[C] satisfying E_{N}[C]=C_{N}/W_{N}, where
C_{N}=å_{(u,v)ÎW}_{N}C(v, u).
The function of interest in this presentation is the bitcost of the
standard Euclidean algorithm, and consequently the cost is as defined
in the previous section, but the methods are sufficiently general as
to apply to a number of cases. The technique views the algorithm as a
dynamical system
[c]4in
with each
iterative step a LFT. Modifying the LFT yields the variants. The
continued fraction expression of the problem motivates the use of
the transformations U(x)=1/xë1/xû
and M(x)=ë1/xû. Notice that
m_{i+1}=M(U^{i}(v_{1}/v_{0})). The value of k in the
continued fraction to the right is the depth.
[c]2inv_{1}/v_{0}=1/m_{1}+1/m_{2}+1/m_{3}+...
+1/m_{k}
2.1 Ergodic theory estimates
Gauss observed that the iteration of the transformation U has invariant density
Y(t)=1/log 21/1+t.
For any A:N® R such that å A(m) m^{2}<¥, define
E_{¥}[A(m)]= ò_{0}^{1}A[m(t)]Y(t)
dt. This is equal to
E 

[ 
A(m) 
] 
=


A(m) 
æ ç ç è 
log_{2} 
æ ç ç è 
1+ 

ö ÷ ÷ ø 
log_{2} 
æ ç ç è 
1+ 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
. 
For example, when applied to l(m):
E_{¥}[l(m)]=(1/log
2) log(Õ_{k³1}1+2^{k}).
In the continuous case, ergodic theory is applicable and gives the
result that the expected value E_{N}[å_{k=1}^{m}A(U^{k}(x))] approaches
E_{¥}[A] almost everywhere. Although ergodic theory does not
apply in the discrete case, it does give plausible estimates as to
what to expect. The assignment A(m)=l(m) gives the expected size of m_{i}
in bits. The discrete version is formulated as
E_{N}[å_{k=1}^{p(x)}A(U^{k}(x))], where p(x) is the depth of the
necessarily finite continued fraction expansion of the rational x. In this
framework one can study the aymptotic behaviour of several functions
on W_{N}, such as:
A^{~}(x)=å_{k=1}^{p(x)} A(m_{k}(x)) and
C^{~}(x)=å_{k=1}^{p(x)} l(m_{k}(x))·log_{2} v_{k}(x).
One might anticipate that the value of E_{N}[A^{~}] under
certain conditions should relate to the expected depth and the
expected size of an iteration. The expected depth, E[p],
corresponds to the number of iterations of the Euclidean algorithm on
input W_{N}, and is asymptotic to 6/p^{2} log^{2}N. So, in the
case of A(m)=l(m),
E_{N} 
é ê ê ë 

ù ú ú û 
~ E_{N}[p]× E 

[ 
A(m) 
] 
= 
æ ç ç è 

log 

æ ç ç è 
1+ 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
log_{2}N.

This is the mean size of the continued fraction encoding of a rational
number. A similar heuristic analysis of E_{N}[C^{~}] shows the relation
E_{N} 
é ê ê ë 

ù ú ú û 
~ E_{N}[p] 

log_{2} N
· 
E 

[ 
l(m) 
] 
.

These observations give a context for the main result.
Theorem 1
The average bitcomplexity of the standard Euclidean algorithm on the
set of valid inputs of denominator less than N is asymptotically of
logsquared order:
E_{N}[C]~ 
æ ç ç è 

log 

æ ç ç è 
1+ 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
log_{2}^{2}N. 
This agrees with the heuristic argument. Numerically, this
values satisfies E_{N}[C]~1.24237log_{2}^{2} N.
3 Summary of Methods
The general method for obtaining this result is similar to the
speaker's analysis of gcdtype functions. The average is expressible
by partial sums of coefficients of Dirichlet series. Tauberian theory
transfers the analytic behaviour of the series near singularities into
asymptotic behaviour of coefficients. When seen as a dynamical system
the generating functions of bitcost relate to the Ruelle operators
associated to the algorithm. The singularities of the Dirichlet series are
related to spectral projections of the operators and are easy to describe.
3.1 Dirichlet generating functions
Define w_{n} to be the set of all pairs (u,v) in W with
v=n and C_{n} as the cumulative value of C over w_{n}. Then
the corresponding encoding into Dirichlet generating functions is
F 

(s)= 


= 

C(v_{1}, v_{0}) 

v_{0}^{s} 

. 
Thus the expected average cost is E_{N}[C]=(å_{ n£
N}C_{n})/(å_{n£ N}w_{n}).
3.2 Tauberian theorem
The Tauberian theorems are a natural tool to
consider as they give asymptotic information about the partial sums of
coefficients of Dirichlet series. They rely on the nature and
position of the singularities of F(s)=å a_{n} n^{s}.
Theorem 2 [Delange]
Let F(s) be a Dirichlet series with nonnegative coefficients such
that F(s) converges for Â(s)>s>0. Assume that:

F is analytic on Â(s)=s, where s¹s;
 F(s)=A(s)(ss)^{g1} +C(s) for some g³ 0,
and A(s) and C(s) analytic with A(s)¹0.
Then, as N®¥, the partial sum of coefficients is

a_{n}= 

N 

log 


N 
( 
1+e(N) 
) 
,
where
e(N)® 0. 
However, the conditions are difficult to verify for
F_{á cñ}(s) in its present form. A transformation gives the
required information about the singularities.
3.3 Ruelle operators
The classical operator is
G_{s}[F](x)= 


F 
æ ç ç è 

ö ÷ ÷ ø 
. 
Let H={ h h(x)=(m+x)^{1}, m³ 1 }, the set of
inverse
branches of U. If D[h] is the denominator of the LFT h(x), then
since D[h° g](x)=D[h]g(x)· D[g](x), the iterates
of G_{s} are given by
G_{s}^{k}[F](x)= 


F° h(x). 
Rationals of W can be written x=h(0) for some h in
H^{k} where k³ 0. Then the Dirichlet generating
function for w_{n} is equal to
å_{n³1}w_{n}n^{s}=å_{hÎ}_{ H}^{*}D[h](0)^{s}=(IG_{s})^{1}[1](0).
A cost version of R_{s,h}[F](x)=D[h](x)^{1}F° h(x) is
defined as R_{s,h}^{[c]}[F](x)=c(h)D[h](x)^{1}F°
h(x). Similarly the cost companion to
G_{s}=å_{hÎ}_{ H}R_{s,h} is
G_{s}^{[c]}=å_{hÎ}_{ H}R_{s,h}^{[c]}.
Recall that C(v_{0}, v_{1})~ å_{i=1}log_{2}(v_{i})c(m_{i}). If
x=v_{1}/v_{0}=h_{1}° h_{2}°...° h_{k}(0), then c(m_{i}) only
depends on h_{i} and v_{i} only depends on h_{i+1}°...°
h_{k}(0).
That is, the function can be expressed as
h=(h_{1}°...° h_{i1})° h_{i}°(h_{i+1}°...° h_{k})
=b_{i}(h)° h_{i}° e_{i}(h).
Defining C_{s,h}=å_{i=1}^{k}¶/¶
sR_{s,e}_{i}_{(h)}° R_{s,h}_{i}^{[c]}° R_{s, b}_{i}_{(h)} yields
F_{á cñ}(s)=å_{hÎ}_{ H}^{*}C_{s,h}[1](0).
3.4 Functional analysis
The singularities of the cost
function can now be described in terms of the singularities of the
C_{s,h}, and subsequently of (IG_{s})^{1}. Analysis of
(IG_{s})^{1} determines the values for the Tauberian theorem to be
s=2 and g=2. Using this, Theorem 1 now follows. In the
case of the operators related to the slow algorithms, the
corresponding result is g=3, accounting for the logcubed
behaviour.
4 Variants and Encoding
As before, the technique applies to a family of variants. For
example, the bitcomplexity of the centred algorithm is asymptotic to

log 
æ ç ç ç ç ç è 
f^{2} 


ö ÷ ÷ ÷ ÷ ÷ ø 
log_{2}^{2}N,
where f=((5)^{1/2}+1)/2.

Finally, the average length of a continued fraction encoding is
computable. This is the
room occupied in memory by (m_{1}, m_{2},..., m_{k}, v_{k}). The encoding
uses the same principles as FanoShannon.
Theorem 3
The average FanoShannon codelength D_{N} of the continued fraction expansion produced
by the standard algorithm on valid inputs with denominator size N
satisfies
D_{N}~ 

æ ç ç è 
1+ 

log 

æ ç ç è 
1+ 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
log_{2} N. 
The numerical value is 2.04868 log_{2}N, which is close
to the optimal 2log_{2} N.
References
 [1]

Akhavi (A.) and Vallée (B.). 
Average bitcomplexity of Euclidean algorithms. In Montanari (Ugo),
Rolim (José D. P.), and Welzl (Emo) (editors), Automata, languages
and programming. Lecture Notes in Computer Science, vol. 1853,
pp. 374387. 
Springer, New York, 2000. Proceedings of the 27th
ICALP Conference, Geneva, Switzerland, July 2000.
 [2]

Salvy (B.). 
Algorithms Seminar, 19981999. 
Research Report n°3830, Institut National de Recherche en
Informatique et en Automatique, December 1999.
 [3]

Vallée (B.). 
Dynamics of the binary Euclidean algorithm: functional analysis and
operators. Algorithmica, vol. 22, n°4, 1998,
pp. 660685. 
Averagecase analysis of algorithms.
 [4]

Vallée (Brigitte). 
A unifying framework for the analysis of a class of Euclidean
algorithms. In Gonnet (Gastón H.), Panario (Daniel), and Viola (Alfredo)
(editors), LATIN 2000: Theoretical Informatics. Lecture Notes in
Computer Science, vol. 1776, pp. 343354. 
Springer, Berlin, 2000. Proceedings of the 4th Latin
American Symposium, Punta del Este, Uruguay, April 2000.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.