Lehmer's GCD algorithm: Difference between revisions

Revision as of 16:56, 21 December 2006

Revision as of 00:31, 23 December 2006

Line 2:

== Algorithm ==

[[Derrick Lehmer|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, for example, comprise 67.7% of all quotients .{{ref|0}}.)

[[Derrick Lehmer|Lehmer]] noted that that most of the [[quotient]]s from each step of the division part of the standard algorithm are small. ([[Donald Knuth|Knuth]] observed that the quotients 1, 2 and 3, for example, comprise 67.7% of all quotients {{ref|0}}.)

Say we want to obtain the GCD of the two integers ''a'' and ''b''. Let <math>\textstyle a \ge b</math>.

* If ''b'' contains only one digit (in somethe choosenchosen [[radix|base]]), use some other method, such likeas 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.

* Let ''x'' be the leading (most significant) digit in ''a'' and ''y'' the leading digit in ''b''.

Line 15 ⟶ 14:

** Set ''x'' to ''y'' and ''y'' to ''x'' - ''wy'' (simultaneously).

** If ''B'' = 0, we have reached a ''deadlock''; perform a normal division with ''a'' and ''b'', and recompute the matrix. Otherwise, set ''a'' to ''aA'' + ''bB'' and ''b'' to ''Ca'' + ''Db'' (again simultaneously), and iterate.

== References ==