Lehmer's GCD algorithm: Difference between revisions

Revision as of 18:21, 16 August 2008

Revision as of 14:16, 25 September 2008

Line 2:

== 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>.)

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

Line 18:

*** If ''B'' = 0, we have reached a ''deadlock''; perform a normal step of the euclidean algorithm with ''a'' and ''b'', and recompute the matrix.

** Set ''a'' to ''aA'' + ''bB'' and ''b'' to ''Ca'' + ''Db'' (again simultaneously). This applies the steps of the euclidean algorithm that were performed on the leading digits in compressed form to the long integers ''a'' and ''b''. Restart the outer iteration.

==References==

<references/>

== References ==