Unified Analysis of Euclidean Algorithms

Brigitte Vallée

Université de Caen

Algorithms Seminar

March 29, 1999

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

Abstract
The average behavior of nine algorithms derived from the Euclidean Algorithm is analysed. Some of them are useful in computing the Jacobi symbol. It is shown that these algorithms form two classes: the fast and the slow algorithms (Q(ln N)) versus Q(ln2 N)). The author suggests a general method, in which the algorithm and the set of its data are viewed as a dynamical system. The Ruelle operator and functional analysis are key tools. This unified approach gives not only the previously known results for classical Euclidean algorithms but also new results about the binary GCD and Jacobi symbol algorithms. In particular, conjectures due to Brent, Bach and Shallit are solved. The average behavior is linked to the entropy of the dynamical system, thus new universal constants (explicit for classical cases, computed numerically in the other cases) are exhibited.

1   Euclidean Algorithms

A previous talk of Brigitte Vallée (see the summary in the proceedings of year 97/98) was devoted to the complete analysis of the binary GCD algorithm. The summary ended by mentioning the application of Vallée's method to the Jacobi Symbol. The last year has seen a unification of the approaches and the reader will find here the analysis of nine algorithms. These are ``flip and reduce'' algorithms and are more or less variations of the ``classical Euclid algorithm'', an algorithm which dates from 300BC and which can also be found in a first-century AD Chinese text (Chiu Chang Suan Shu).

Before the ``functional analytic number theoretical dynamical systematic'' approach of Vallée, the state of the art was due to Brent [1], Knuth [5], Heilbron [4], Dixon [3], Vardi [10], Bach, Shallit [7].

Vallée and her student, C. Lemée, gave some new results for the analysis of the average complexity of the computation of a fundamental function in number theory: the Jacobi symbol, which allows to determine whether a number is a square in a given modular arithmetic or not.

The Legendre symbol is defined for an odd prime number v as
(
u
v
)=
ì
í
î
0,   if uº 0 mod v;
1,   if v is a square modulo v;
-1,   if v is not a square mod v.
The Jacobi symbol extends the Legendre symbol and is defined as
J(u,v):=
 
Õ
iÎ I
(
u
vi
)
ei
 
    for v=
 
Õ
iÎ I
v
ei
 
i
with odd primes vi.
Of course one does not need to know the factorisation of v in order to compute J(u,v). Instead, one uses the following formulæ:
Quadratic reciprocity law:    J(u,v) =(-1)(u-1)(v-1)/4J(v,u)    for u,v odd positive integers,
Modulo law:   J(v,u) =J(v-bu,u),
Multiplicativity law:   J(vw,u) =J(v,u)J(w,u),
Special values:   J(2,v)
=(-1)
(v2-1)/8
 
,      J(e,u)=e(u-1)/2   for e=± 1.
Then one has several Euclidean-like possible algorithms. We distinguish the nine following cases (name, constraints of the algorithm and an example are given):
Classical with positive remainders
v=cu+r, 0£ r<u 13/75=1/5+1/1+1/3+1/3+0
Subtractive classical
v=u+(v-u) 13/75=1/1+1+1+1+1+1/1+1/1+1+1+1/1+1+1
Classical with negative remainders
v=cu-r
0£ r <u 13/75=1/6-1/5-1/2-1/2+0
Classical with centred remainders
v=cu+e r
c³ 2, e=±1, (c,e)¹ (2,-1)
0£ r £ u/2 13/75=1/6-1/4+1/3
Even CF
v=cu+e s,
c even, e=± 1 s odd, 0<s<u 13/75=1/6-1/4+1/4-1
Odd CF
v=cu+e 2k s,
c odd, e=± 1,
s odd, k³ 1, 0£ 2ks <u 13/75=1/5+2/3-2/5+0
Ordinary CF
v=cu+2ks, s=0 or s odd,
k³ 0,
0£ 2ks<u 13/75=1/5+2/2+1/1+2/3+0
Centred CF
v=cu+e2ks,
s=0 or s odd, k³ 0,
0£ 2k s<u/2 13/75=1/6-1/4+1/3+0
Binary GCD
v=au+2kr,
a odd,
a<2k, r£ u 13/75=1/1+2+22/1+22/1+23

2   Functional Analytic Number theory

Performing l steps of one of the above algorithms gives a continued fraction of height l and the expression of the rational u/v as
u
v
=h1° h2 ° ...° hl(a)     (1)
where a is 1 or 0 and where the hi's are ``linear fractional transformations'' or LFT (``homographie'' in French). Of course the values of a,b,c,d in hi=az+b/cz+d depend on the algorithms. What is more, the shape of the first and last LFT can be different from the other ``intermediate'' generic LFT, depending on the initial and stopping conditions of the algorithm.

Introduce the double Dirichlet generating function
S(s,w):=
 
å
l³ 1
 
å
n>1
nn[l]
ns
wl
where nn[l] is the number of rationals of W (set of valid inputs in [0,1] or [0,1/2], depending on the algorithm) of the form u/n which give a continued fraction of height l. Defining an and bn by
S(s,1)=:
 
å
n> 1
an
ns
     and     
w
S(s,w)|w=1=:
 
å
n>1
bn
ns
allows to express SN, the average number of steps of the algorithm on the rationals u/v of W for u£ N, as
SN=
 
å
n£ N
bn
 
å
n£ N
an
=
 
å
n£ N
 
å
l³ 0
l nn[l]
 
å
n£ N
 
å
l³ 0
nn[l]
.

Thus the average behavior of the algorithm is dictated by the asymptotics of partial sums of coefficients of the function S.

For any Dirichlet series F(s) with nonnegative coefficients an converging in Â(s)>s>0, a theorem of Delange gives
 
å
n£ N
an=
A
sG(g+1)
N
s
 
ln
g
 
N (1+o(N)).
As for any Tauberian theorem, F(s) has to fulfill some hypotheses (analyticity on Â(s)=s for s¹ s and there exist A,B analytic at s such that F(s)=A(s)(s-s)-g-1+B(s)). A major part of the the work consists in proving that these properties hold.

Recall that for each algorithm, there are 4 sets of LFT: the single LFT's  K, the initial LFT's  I, the final LFT's  F and the intermediate LFT's  H. Now define the ``Ruelle operator'' A relative to a set  A of LFT's by
As(f)=
 
å
hÎ A
f° h
denom(h)s
.
The decomposition of an algorithm as a single LFT or as final+sequence(intermediate)+initial LFT's (for short K+FH*J) leads to S(s,w)=wKs(1)(a)+w2Fs° (I-wHs)-1° Js(1)(a) (where a is defined as in equation 1 and where ° is the composition over the space of operators). Variations for Markovian cases are possible and lead to the same treatment.

Finally, spectral properties of I-Hs allow to determine s=2 and g=1 or 2 (in some cases, one needs to choose an adequate functional space in order to establish this).

Here is a summary of the average number of steps performed by the nine algorithms:
 
positive remainders 12ln 2/p2ln N .842 ln N Heilbron & Dixon 70
subtractive 6/p2(ln N)2 .607(ln N)2 Knuth & Yao 75
negative remainders 3/p2 (ln N)2 .303(ln N)2 Vardi 92
centred remainders 12ln f/p2ln N .585ln N Rieger 80
even 2/p2(ln N)2 .202(ln N)2 Vallée & Lemée 98
odd AOln N .435 ln N Vallée & Lemée 98
ordinary AUln N .535 ln N Vallée & Lemée 98
centred ACln N .430 ln N Vallée & Lemée 98
binary GCD ABln N .555 ln N Vallée 98

The author also makes the link between the constants given here and the entropy of the dynamical system related to the algorithm.

The results presented here are mainly in [9] and in a preprint of Brigitte and her student [6]. Like other preprints of the author, it is available at her home page
http://www.info.unicaen.fr/~brigitte/Publications/

References

[1]
Brent (Richard P.). -- Analysis of the binary Euclidean algorithm. In Algorithms and complexity, pp. 321--355. -- Academic Press, New York, 1976. Proceedings of a Symposium held at Carnegie-Mellon 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. 213--242.

[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. 87--96. -- Plenum, New York, 1969.

[5]
Knuth (Donald E.). -- The Art of Computer Programming. -- Addison-Wesley, 1997, third edition, vol. 2.

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

[7]
Shallit (Jeffrey). -- Origins of the analysis of the Euclidean algorithm. Historia Mathematica, vol. 21, n°4, 1994, pp. 401--419.

[8]
Vallée (Brigitte). -- The complete analysis of the binary Euclidean algorithm. In Proceedings ANTS'98. -- 1998.

[9]
Vallée (Brigitte). -- A Unifying Framework for the Analysis of a Class of Euclidean Algorithms. In Proceedings FOCS'99. -- 1999.

[10]
Vardi (Ilan). -- Dedekind sums have a limiting distribution. Duke Mathematical Journal, n°1, 1993, pp. 1--12.
This document was translated from LATEX by HEVEA.