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, Automatique 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 metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00210493
Contributor : Hal System <>
Submitted on : Monday, January 21, 2008 - 11:36:12 AM
Last modification on : Tuesday, April 2, 2019 - 1:36:17 AM
Long-term archiving on : Wednesday, April 14, 2010 - 11:41:58 PM

File

Lhote-Vallee.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00210493, version 1

Citation

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

Share

Metrics

Record views

154

Files downloads

151