Euclidean algorithms are Gaussian

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
fourth revised version - 2 figures - the strict convexity condition used has been clarified

Keywords

Data Structures and Algorithms, Computational Complexity, F.2.1, I.1.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/31723

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0307062
 http://arxiv.org/abs/cs/0307062

Collections

arXiv