Sharp estimates for the main parameters of the Euclid Algorithm - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Sharp estimates for the main parameters of the Euclid Algorithm

(1) , (1)
1
Loïck Lhote

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.
Fichier principal
Vignette du fichier
Lhote-Vallee.pdf (179.98 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-00210493 , version 1 (21-01-2008)

Identifiers

  • HAL Id : hal-00210493 , version 1

Cite

Loïck Lhote, Brigitte Vallée. Sharp estimates for the main parameters of the Euclid Algorithm. 2008. ⟨hal-00210493⟩
94 View
179 Download

Share

Gmail Facebook Twitter LinkedIn More