HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal.inria.fr/inria-00072561
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:17:27 AM
Last modification on : Thursday, February 3, 2022 - 11:14:02 AM
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

135

Files downloads

196