Existence of a Limiting Distribution for the Binary GCD Algorithm

الأصل · EN

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 brent. Donald Knuth also supposes its existence in 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 binary Euclidean operator B₂, proving rigorously that its derivative is a fixed point of B₂.