Continued Fractions, Comparison Algorithms, and Fine Structure Constants - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

Continued Fractions, Comparison Algorithms, and Fine Structure Constants

Philippe Flajolet
  • Fonction : Auteur
  • PersonId : 829512
Brigitte Vallée

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-4072.pdf (605.84 Ko) Télécharger le fichier

Dates et versions

inria-00072561 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072561 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More