Existence of a Limiting Distribution for the Binary GCD Algorithm

Details Existence of a Limiting Distribution for the Binary GCD Algorithm Existence of a Limiting Distribution for the Binary GCD Algorithm

2005-04-21

arxiv.org/abs/math/0504426v2

Journal of Discrete Algorithms, Volume 5, 2007

Mathematics

General Mathematics

13 pages. New introduction, conclusion and several typos corrected

Scientific paper

In this article, we prove the existence and uniqueness of a certain distribution function on the unit interval. This distribution appears in Brent's model of the analysis of the binary gcd algorithm. The existence and uniqueness of such a function has been conjectured by Richard Brent in his original paper \cite{brent}. Donald Knuth also supposes its existence in \cite{knuth} where developments of its properties lead to very good estimates in relation with the algorithm. We settle here the question of existence, giving a basis to these results, and study the relationship between this limiting function and the {\it binary Euclidean operator} $B_2$, proving rigorously that its derivative is a fixed point of $B_2$.

Affiliated with

Also associated with

No associations

Rating

Existence of a Limiting Distribution for the Binary GCD Algorithm 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 Existence of a Limiting Distribution for the Binary GCD Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Existence of a Limiting Distribution for the Binary GCD Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-315599