Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Sharp estimates for the main parameters of the Euclid Algorithm

Loïck Lhote 1 Brigitte Vallée 1
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
Abstract : We provide sharp estimates for the probabilistic behaviour of the main parameters of the Euclid algorithm, and we study in par- ticular the distribution of the bit-complexity which involves two main parameters : digit–costs and length of continuants. We perform a “dy- namical analysis” which heavily uses the dynamical system underlying the Euclidean algorithm. Baladi and Vall´ee [2] have recently designed a general framework for “distributional dynamical analysis”, where they have exhibited asymptotic gaussian laws for a large class of digit–costs. However, this family contains neither the bit–complexity cost nor the length of continuants.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Hal System Connect in order to contact the contributor
Submitted on : Monday, January 21, 2008 - 11:36:12 AM
Last modification on : Tuesday, October 19, 2021 - 11:34:56 PM
Long-term archiving on: : Wednesday, April 14, 2010 - 11:41:58 PM


Publisher files allowed on an open archive


  • HAL Id : hal-00210493, version 1


Loïck Lhote, Brigitte Vallée. Sharp estimates for the main parameters of the Euclid Algorithm. 2008. ⟨hal-00210493⟩



Les métriques sont temporairement indisponibles