The Lyapunov tortoise and the dyadic hare

Benoît Daireaux 1 Véronique Maume-Deschamps 2 Brigitte Vallée 1
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : We study a gcd algorithm directed by Least Significant Bits, the so―called LSB algorithm, and provide a precise average―case analysis of its main parameters [number of iterations, number of shifts, etc...]. This analysis is based on a precise study of the dynamical systems which provide a continuous extension of the algorithm, and, here, it is proved convenient to use both a 2―adic extension and a real one. This leads to the framework of products of random matrices, and our results thus involve a constant $γ$ which is the Lyapunov exponent of the set of matrices relative to the algorithm. The algorithm can be viewed as a race between a dyadic hare with a speed of 2 bits by step and a "real'' tortoise with a speed equal to $γ /\textit{log} \ 2 \sim 0.05$ bits by step. Even if the tortoise starts before the hare, the hare easily catches up with the tortoise [unlike in Aesop's fable [Ae]\ldots], and the algorithm terminates.
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.71-94, 2005, DMTCS Proceedings
Liste complète des métadonnées


https://hal.inria.fr/hal-01184044
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:52:48
Dernière modification le : mercredi 10 mai 2017 - 17:39:24
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:57

Fichier

dmAD0108.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184044, version 1

Citation

Benoît Daireaux, Véronique Maume-Deschamps, Brigitte Vallée. The Lyapunov tortoise and the dyadic hare. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.71-94, 2005, DMTCS Proceedings. <hal-01184044>

Partager

Métriques

Consultations de
la notice

366

Téléchargements du document

76