# The Lyapunov tortoise and the dyadic hare

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.
Keywords :
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
Domaine :

Littérature citée [24 références]

https://hal.inria.fr/hal-01184044
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:52:48
Dernière modification le : jeudi 7 février 2019 - 17:27:27
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:57

### Fichier

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〉

### Métriques

Consultations de la notice

## 495

Téléchargements de fichiers