Lehmer's GCD algorithm: Difference between revisions

Revision as of 10:25, 18 June 2009

Revision as of 14:57, 18 June 2009

Line 1:

'''Lehmer's GCD algorithm''', named after [[Derrick Henry Lehmer]], is a rather fast [[greatest common divisor|GCD]] [[algorithm]], an improvement on the simpler but slower [[Euclidean algorithm]]. It is mainly used for big integers that have a representation as a string of digits relative to some chosen numbernumeral system [[radix|base]], say <math>\''&beta;''&nbsp;=&nbsp;1000</math> or <math>\''&beta;''&nbsp;=&nbsp;2^{<sup>32}</mathsup>.

== Algorithm ==

Lehmer noted that 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''.

* If ''b'' contains only one digit (in the chosen [[radix|base]], say <math>\beta=1000</math> or <math>\beta=2^{32}</math>), use some other method, such as the [[Euclidean algorithm]], to obtain the result.

* If ''a'' and ''b'' differ in the length of digits, perform a division so that ''a'' and ''b'' are equal in length, with length equal to ''m''.