Geodesic
The Lyapunov tortoise and the dyadic hare
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_249_a20,
     author = {Daireaux, Beno{\^\i}t and Maume-Deschamps, V\'eronique and Vall\'ee, Brigitte},
     title = {The {Lyapunov} tortoise and the dyadic hare},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3372},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3372/}
}
TY  - JOUR
AU  - Daireaux, Benoît
AU  - Maume-Deschamps, Véronique
AU  - Vallée, Brigitte
TI  - The Lyapunov tortoise and the dyadic hare
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3372/
DO  - 10.46298/dmtcs.3372
LA  - en
ID  - DMTCS_2005_special_249_a20
ER  - 
%0 Journal Article
%A Daireaux, Benoît
%A Maume-Deschamps, Véronique
%A Vallée, Brigitte
%T The Lyapunov tortoise and the dyadic hare
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3372/
%R 10.46298/dmtcs.3372
%G en
%F DMTCS_2005_special_249_a20
Daireaux, Benoît; Maume-Deschamps, Véronique; Vallée, Brigitte. The Lyapunov tortoise and the dyadic hare. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3372. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3372/

Cité par Sources :