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

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00210493
Contributeur : Hal System <>
Soumis le : lundi 21 janvier 2008 - 11:36:12
Dernière modification le : lundi 25 septembre 2017 - 16:08:15
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

110

Téléchargements de fichiers

68