Continued Fractions, Comparison Algorithms and Fine Structure Constants

Philippe Flajolet

Algorithms Project, INRIA Rocquencourt

Algorithms Seminar

November 8, 1999

[summary by 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 simple problems of comparing fractions (Gosper's algorithms for continued fractions from the Hacker's Memorandum) and of deciding the orientation of triangles in computational geometry lead to a complexity analysis with an incursion into a surprising variety of domains: dynamical systems (symbolic dynamics), number theory (continued fractions), special functions (multiple zeta values), functional analysis (transfer operators), numerical analysis (series acceleration), and complex analysis (Riemann hypothesis). These domains all eventually contribute to a detailed characterization of the complexity of comparison and sorting algorithms, either on average or in probability. (Joint work with Brigitte Vallée.)



1   Introduction

To compare two rational numbers (or similarly, to determine the sign of a 2×2 determinant, a relevant problem in computational geometry) is a delicate problem when you have to work with a numerical calculator limited to a given number of digits. For example, since 312689/99532-833719/265381» 3× 10-11, a computer with 10-digit accuracy cannot compare ``naively'' the two rational numbers.

In the ``Hacker's Memorandum'' [2], it is showed that it is always possible to solve this comparison problem without exceeding the accuracy of the calculator. The algorithm consists in expanding both rational numbers in continued fractions, but stopping as soon as one gets two different coefficients. This algorithm is easily generalized to any number representation system (binary, d-ary, centered or classical continued fraction, etc.) and also to the comparison of n rational numbers.

2   Results

The functions U_(x)={1/x} and U^(x)={{1/x}} (where {{y}} stands for the distance to the nearest integer from y) are the maps of classical continued fractions and centred continued fractions respectively. Under a uniform probabilistic model (over the set of legal inputs, that is, an interval of the shape [ 0,a ]), the number L of iterations needed to compare two numbers satisfies P(L³ k+1)= å|h|=k |h(0)-h(a)/a|2 and the moment sums of order l satisfy r(l)=åh |h(0)-h(a)/a|l. These sums are over the inverse branches of U, which appear to be linear fraction operators of a specific shape [6], thus:

Theorem 1   The expected cost of the basic (r_) and centred (r^) comparison algorithms are expressible as sums over lattice points in N2
_
r
 
(l)=1+
1
2l
+
2
z(2l)
 
å
d<c<2d
1
cldl
  and   
^
r
 
(l)=
2l
z(2l)
 
å
df<c<df2
1
cldl
     ( f= ( 1+(5)1/2  ) /2 ) .

With the help of double zeta values (also known as Euler--Zagier sums), defined as
z
+ +
 
(s,t)=
¥
å
n=1
n-1
å
q=1
1
nsqt
  and    z
- +
 
(s,t)=
¥
å
n=1
n-1
å
q=1
(-1)n
nsqt
,
it is possible to rewrite r_(2) as a peculiar value of these multiple zeta values (this implies that r_(2) can be computed to any precision in polynomial time):
Theorem 2   The mean number r_(2) of comparisons in the classical continued fraction can be expressed in terms of double zeta values as
_
r
 
(2) =
3
4
+
360
p4
z
- +
 
(2,2) =17-
60
p4
( 24Li4 ( 1/2 ) -p2(ln2)2+21z(3)ln 2+(ln 2)4 ) =1.35113157...

There exists a lot of alternative expressions, due to intriguing relations between multiple zeta values, which is a topic of active research (see [1, 5, 7]), nowadays relevant to knot invariants, Feynman diagrams and even the theory of perverse sheaves. For all the other moment sums, polynomial time computations are also possible, via some nice series/integral representations [6].

For the comparison of n real numbers, the cost of sorting n numbers depends on the position of the nontrivial zeroes of the Riemann zeta function (see [3] for an approach by Dirichlet depoissonization and Mellin transform, using the Vallée secant operator or [6] for an approach by Nörlund--Rice integrals, via a complex lifting of the moment sums):
Theorem 3   The expected cost of sorting n uniform real numbers given by their classical continued fraction representations satisfies
_
P
 
(n)=n
n-1
å
l-1
(-1)l-1
æ
è
n-1
l
ö
ø
_
r
 
(l+1)=K0nln n+K1 n +Q(ln n)+O(1),
where K0 is Lévy's entropy constant and K1 is a Porter-like constant (see [4]):
K0=
6ln 2
p2
  and   K1=18
gln2
p2
+9
(ln 2)2
p2
-72
ln 2  z'(2)
p4
-
1
2
.
The function Q(u) is an oscillating function with mean value 0 that satisfies Q(n)=O(ud/2), where d is any number such that d>sup  { Â(s) | z(s)=0 }.

For more details, we refer to Flajolet and Vallée's articles, available on their web pages:
http://algo.inria.fr/flajolet  and  http://www.info.unicaen.fr/~brigitte.

References

[1]
Bailey (David H.), Borwein (Jonathan M.), and Girgensohn (Roland). -- Experimental evaluation of Euler sums. Experimental Mathematics, vol. 3, n°1, 1994, pp. 17--30.

[2]
Beeler (M.), Gosper (R. W.), and Schroeppel (R.). -- HAKMEM. -- Artificial Intelligence Memorandum n°239, Massachusetts Institute of Technology, A. I. Laboratory, February 1972. Retyped version available from http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html.

[3]
Clément (J.), Flajolet (P.), and Vallée (B.). -- Dynamical sources in information theory: A general analysis of trie structures. Algorithmica. -- 61 pages. To appear.

[4]
Finch (S.). -- Favorite mathematical constants. -- http://www.mathsoft.com/asolve/constant/constant.html.

[5]
Flajolet (Philippe) and Salvy (Bruno). -- Euler sums and contour integral representations. Experimental Mathematics, vol. 7, n°1, 1998, pp. 15--35.

[6]
Flajolet (Philippe) and Vallée (Brigitte). -- Continued fractions, comparison algorithms, and fine structure constants. In Théra (M.) (editor), Analysis and Applications, Canadian Mathematical Society. -- To appear.

[7]
Zagier (Don). -- Values of zeta functions and their applications. In First European Congress of Mathematics, Vol. II (Paris, 1992), pp. 497--512. -- Birkhäuser, Basel, 1994.
This document was translated from LATEX by HEVEA.