Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://en.wikipedia.org/wiki/Lehmer's_GCD_algorithm below:

Lehmer's GCD algorithm - Wikipedia

From Wikipedia, the free encyclopedia

Fast greatest common divisor algorithm

Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a fast 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 numeral system base, say β = 1000 or β = 2³².

Lehmer noted that most of the quotients from each step of the division part of the standard algorithm are small. (For example, Knuth observed that the quotients 1, 2, and 3 comprise 67.7% of all quotients.^[1]) 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 b. Let a ≥ b.

• If b contains only one digit (in the chosen base, say β = 1000 or β = 2³²), 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, x = a div β ^m and y the leading digit in b, y = b div β ^m.
  • Initialize a 2 by 3 matrix

  [ A B x C D y ] {\displaystyle \textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}} to an extended identity matrix [ 1 0 x 0 1 y ] , {\displaystyle \textstyle {\begin{bmatrix}1&0&x\\0&1&y\end{bmatrix}},}

  and perform the euclidean algorithm simultaneously on the pairs (x + A, y + C) and (x + B, y + D), 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.

• Kapil Paranjape, Lehmer's Algorithm

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4