Continued Fractions, Comparison Algorithms, and Fine Structure Constants

Philippe Flajolet 1 Brigitte Vallée 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
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 characteriz- ation of the complexity of comparison and sorting algorithms, either on average or in probability.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072561
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:17:27 AM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Tuesday, February 22, 2011 - 12:06:17 PM

Identifiers

  • HAL Id : inria-00072561, version 1

Collections

Citation

Philippe Flajolet, Brigitte Vallée. Continued Fractions, Comparison Algorithms, and Fine Structure Constants. [Research Report] RR-4072, INRIA. 2000. ⟨inria-00072561⟩

Share

Metrics

Record views

949

Files downloads

228