ALCOMFT-TR-01-1

Philippe Flajolet and Brigitte Vallée
Continued Fractions, Comparison Algorithms, and Fine Structure Constants
INRIA. Work packages 4 and 5. January 2001.

Abstract: There are known algorithms based on continued fractions for comparing fractions and for determining the sign of 2x2 determinants. The analysis of such extremely simple algorithms leads to an incursion into a surprising variety of domains. We take the reader through a light tour of dynamical systems (symbolic dynamics), number theory (continued fractions), special functions (multiple zeta values), functional analysis (transfer operators), numerical analysis (series acceleration), and complex analysis (the 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.

Postscript file: ALCOMFT-TR-01-1.ps.gz (393 kb).