Euclidean algorithms are Gaussian

Details Euclidean algorithms are Gaussian Euclidean algorithms are Gaussian

2003-07-28

arxiv.org/abs/cs/0307062v4

Computer Science

Data Structures and Algorithms

fourth revised version - 2 figures - the strict convexity condition used has been clarified

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Euclidean algorithms are Gaussian does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Euclidean algorithms are Gaussian, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Euclidean algorithms are Gaussian will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107904