کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431737 | 688618 | 2007 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Existence of a limiting distribution for the binary GCD algorithm Existence of a limiting distribution for the binary GCD algorithm](/preview/png/431737.png)
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 was conjectured by Richard Brent in his original paper [R.P. Brent, Analysis of the binary Euclidean algorithm, in: J.F. Traub (Ed.), New Directions and Recent Results in Algorithms and Complexity, Academic Press, New York, 1976, pp. 321–355]. Donald Knuth also supposes its existence in [D.E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, third ed., Addison-Wesley, Reading, MA, 1997] where developments of its properties lead to very good estimates in relation to 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 B2B2, proving rigorously that its derivative is a fixed point of B2B2.
Journal: Journal of Discrete Algorithms - Volume 5, Issue 1, March 2007, Pages 176–186