Computation of a class of continued fraction constants - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Proceeding of Alenex Année : 2004

Computation of a class of continued fraction constants

Loïck Lhote

Résumé

We describe a class of algorithms which compute in polynomial– time important constants related to the Euclidean Dynamical System. Our algorithms are based on a method which has been previously introduced by Daudé Flajolet and Vallée. However, the authors did not prove the correctness of the algorithm and did not provide any complexity bound. Here, we describe a general framework where the DFV–method leads to a proven polynomial–time algorithm that computes ”spectral constants” relative to a class of Dynamical Systems. These constants are closely related to eigenvalues of the transfer operator. Since it acts on an infinite dimensional space, exact spectral computations are almost always impossible, and are replaced by (proven) numerical approximations. The transfer operator can be viewed as an infinite matrix M which is the limit (in some precise sense) of the sequence of truncated matrices M_n of order n where exact computations are possible. We prove that each isolated eigenvalue s of M is a limit of a sequence s_n in the spectrum of M_n , with exponential speed. Then, coming back to the Euclidean Dynamical System, we compute (in polynomial time) three important constants which play a central rôle in the Euclideanalgorithm: (i) the Gauss-Kuzmin-Wirsing constant related to the speed of convergence of the continued fraction algorithm to its limit density; (ii) the Hensley constant which occurs in the leading term of the variance of the number of steps of the Euclid algorithm; (iii) the Hausdorff dimension of the Cantor sets relative to constrained continued fraction expansions.
Fichier principal
Vignette du fichier
loick4.pdf (267.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00263891 , version 1 (12-06-2017)

Identifiants

  • HAL Id : hal-00263891 , version 1

Citer

Loïck Lhote. Computation of a class of continued fraction constants. Proceeding of Alenex, 2004, pp.199-210. ⟨hal-00263891⟩
145 Consultations
76 Téléchargements

Partager

Gmail Facebook X LinkedIn More