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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00263891
Contributor : Hal System <>
Submitted on : Monday, June 12, 2017 - 10:10:57 PM
Last modification on : Thursday, February 7, 2019 - 5:46:54 PM
Long-term archiving on : Thursday, September 14, 2017 - 11:55:18 AM

File

loick4.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00263891, version 1

Citation

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

Share

Metrics

Record views

194

Files downloads

58