Lehmer's GCD algorithm

Lehmer's GCD algorithm is a rather fast GCD algorithm, an improvement on the simpler but slower Euclidean algorithm.

Algorithm

Lehmer noted that that most of the quotients from each step of the division part of the standard algorithm are small. (Knuth observed that the quotients 1, 2 and 3, for example, comprise 67.7% of all quotients ^[1].)

Say we want to obtain the GCD of the two integers a and b. Let $\textstyle a\geq b$.

• If b contains only one digit (in some choosen base), use some other method like 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.
• Initialize a square matrix $\textstyle {\begin{Bmatrix}A&B\\C&D\end{Bmatrix}}$ to the identity matrix $\textstyle {\begin{Bmatrix}1&0\\0&1\end{Bmatrix}}$, and iterate:
  • Compute the quotients w₁ of (x + A)(y + C) and w₂ of (x + B)(y + D) respectively. Also let w be the quotient from a/b.
  • If w₁ = w₂, set w to w₁ (or w₂).
  • Set our current matrix $\textstyle {\begin{Bmatrix}A&B\\C&D\end{Bmatrix}}$ to $\textstyle {\begin{Bmatrix}0&1\\1&-w\end{Bmatrix}}\bullet {\begin{Bmatrix}A&B\\C&D\end{Bmatrix}}={\begin{Bmatrix}C&D\\A-wC&B-wD\end{Bmatrix}}$
  • 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

• ^ Knuth, The Art of Computer Programming volume 4, section 5.3, Theorem E
• Kapil Paranjape, Lehmer's Algorithm