Lehmer's GCD algorithm: Difference between revisions

Revision as of 20:32, 3 January 2015

Revision as of 18:18, 7 January 2015

Line 2:

== Algorithm ==

Lehmer gand noted that most of the [[quotient]]s from each step of the division part of the standard algorithm are small. (For example, [[Donald Knuth|Knuth]] observed that the quotients 1, 2, and 3 comprise 67.7% of all quotients.<ref name="knuth2">[[Donald Knuth|Knuth]], ''[[The Art of Computer Programming]] vol 2 "Seminumerical algorithms"'', chapter 4.5.3 Theorem E.</ref>) Those small quotients can be identified from only a few leading digits. Thus the algorithm starts by splitting off those leading digits and computing the sequence of quotients as long as it is correct.

Say we want to obtain the GCD of the two integers ''a'' and&nbsp;''b''. Let ''a''&nbsp;&ge;&nbsp;''b''.