Continued Fraction Algorithms, Functional Operators, and Structure Constants - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1996

Continued Fraction Algorithms, Functional Operators, and Structure Constants

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

Résumé

Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a 2-dimensional generalization. This paper surveys the main properties of functional operators, ---transfer operators--- due to Ruelle and Mayer (also following Lévy, Kuzmin, Wirsing, Hensley, and others) that describe precisely the dynamics of the continued fraction transformation. Spectral characteristics of transfer operators are shown to have many consequences, like the normal law for logarithms of continuants associated to the basic continued fraction algorithm, where better convergence terms are obtained, and a purely analytic estimation of the average number of steps of the Euclidean algorithm. Transfer operators also lead to a complete analysis of the «Hakmem» algorithm for comparing two rational numbers via partial continued fraction expansions, and of the «digital tree» algorithm for completely sorting $n$ real numbers by means of their continued fraction representations. Thus, a small number of «structure constants» appear to govern the behaviour of a variety of continued fraction based algorithms.

Domaines

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

Dates et versions

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

Identifiants

  • HAL Id : inria-00073768 , version 1

Citer

Philippe Flajolet, Brigitte Vallée. Continued Fraction Algorithms, Functional Operators, and Structure Constants. [Research Report] RR-2931, INRIA. 1996. ⟨inria-00073768⟩
95 Consultations
194 Téléchargements

Partager

Gmail Facebook X LinkedIn More