Euclidean algorithms are Gaussian
| dc.creator | Baladi, Viviane | |
| dc.creator | Vallee, Brigitte | |
| dc.date | 2003-07-28 | |
| dc.date | 2004-05-05 | |
| dc.date.accessioned | 2026-07-07T03:20:08Z | |
| dc.date.available | 2026-07-07T03:20:08Z | |
| dc.description | This study provides new results about the probabilistic behaviour of a class of Euclidean algorithms: the asymptotic distribution of a whole class of cost-parameters associated to these algorithms is normal. For the cost corresponding to the number of steps Hensley already has proved a Local Limit Theorem; we give a new proof, and extend his result to other euclidean algorithms and to a large class of digit costs, obtaining a faster, optimal, rate of convergence. The paper is based on the dynamical systems methodology, and the main tool is the transfer operator. In particular, we use recent results of Dolgopyat. | |
| dc.description | fourth revised version - 2 figures - the strict convexity condition used has been clarified | |
| dc.identifier | https://arxiv.org/abs/cs/0307062 | |
| dc.identifier | http://arxiv.org/abs/cs/0307062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31723 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.1, I.1.2 | |
| dc.title | Euclidean algorithms are Gaussian | |
| dc.type | text |