Lehmer's GCD algorithm: Difference between revisions

Revision as of 11:30, 5 May 2014

Revision as of 20:32, 3 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''.