Sharp estimates for the main parameters of the Euclid Algorithm

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.
Type de document :
Pré-publication, Document de travail
2008
Liste complète des métadonnées


https://hal.archives-ouvertes.fr/hal-00210493
Contributeur : Hal System <>
Soumis le : lundi 21 janvier 2008 - 11:36:12
Dernière modification le : mercredi 27 mai 2015 - 10:50:50
Document(s) archivé(s) le : mercredi 14 avril 2010 - 23:41:58

Fichier

Lhote-Vallee.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

107

Téléchargements du document

65