Lehmer's GCD algorithm: Difference between revisions

Revision as of 14:57, 18 June 2009

Revision as of 15:01, 18 June 2009

Line 5:

Say we want to obtain the GCD of the two integers ''a'' and ''b''. Let ''a'' ≥ ''b''.

* If ''b'' contains only one digit (in the chosen [[radix|base]], say <math>\''&beta;''&nbsp;=&nbsp;1000</math> or <math>\''&beta;''&nbsp;=&nbsp;2^{<sup>32}</mathsup>), 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''.

* ''Outer loop:'' Iterate until one of ''a'' or ''b'' is zero:

** Decrease ''m'' by one. Let ''x'' be the leading (most significant) digit in ''a'', <math>''x''&nbsp;=&nbsp;''a \text{ ''&nbsp;div } \&nbsp;''&beta^;''<sup>&nbsp;''m''</mathsup> and ''y'' the leading digit in ''b'', <math>''y''&nbsp;=&nbsp;''b \text{ ''&nbsp;div } \&nbsp;''&beta^;''<sup>&nbsp;''m''</mathsup>.

** Initialize a 2 &nbsp;by &nbsp;3 [[matrix (mathematics)|matrix]]

*::<math>\textstyle

\begin{bmatrix} A & B & x\\ C & D & y \end{bmatrix}

Line 15:

\begin{bmatrix} 1 & 0 & x \\ 0 & 1 & y\end{bmatrix}

</math>,

*:and perform the euclidean algorithm simultaneously on the pairs <math>(''x''&nbsp;+&nbsp;''A'',&nbsp;''y''&nbsp;+&nbsp;''C'')</math> and <math>(''x''&nbsp;+&nbsp;''B'',&nbsp;''y''&nbsp;+&nbsp;''D'')</math>, until the quotients differ. That is, iterate as an ''inner loop'':

*:* Compute the quotients ''w''₁ of the long divisions of (''x'' + ''A'') by (''y'' + ''C'') and ''w''₂ of (''x'' + ''B'') by (''y'' + ''D'') respectively. Also let ''w'' be the (not computed) quotient from the current long division in the chain of long divisions of the euclidean algorithm.

*** If ''w''₁ &ne; ''w''₂, then break out of the inner iteration. Else set ''w'' to ''w''₁ (or &nbsp;''w''₂).

*** Replace the current matrix

**::<math>\textstyle \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}</math>

Line 28:

</math>

**:according to the matrix formulation of the extended euclidean algorithm.

***If ''B''&nbsp;&ne; &nbsp;0, go to the start of the inner loop.

** If ''B'' &nbsp;= &nbsp;0, we have reached a ''deadlock''; perform a normal step of the euclidean algorithm with ''a'' and ''b'', and restart the outer loop.

** Set ''a'' to ''aA'' &nbsp;+ &nbsp;''bB'' and ''b'' to ''Ca'' &nbsp;+ &nbsp;''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''. If ''b''&nbsp;&ne; &nbsp;0 go to the start of the outer loop.

==References==