Computation of a class of continued fraction constants

Loïck Lhote 1
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : 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.
Type de document :
Article dans une revue
Proceeding of Alenex, 2004, pp.199-210
Liste complète des métadonnées
Contributeur : Hal System <>
Soumis le : lundi 12 juin 2017 - 22:10:57
Dernière modification le : mardi 27 juin 2017 - 01:05:37
Document(s) archivé(s) le : jeudi 14 septembre 2017 - 11:55:18


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00263891, version 1



Loïck Lhote. Computation of a class of continued fraction constants. Proceeding of Alenex, 2004, pp.199-210. <hal-00263891>



Consultations de
la notice


Téléchargements du document