Euclidean algorithm

From Example Problems
Jump to: navigation, search
This article is not about Euclidean geometry.

The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. However, the algorithm probably was not discovered by Euclid and it may have been known up to 200 years earlier. It was almost certainly known by Eudoxus of Cnidus (about 375 BC); and Aristotle (about 330 BC) hinted at it in his Topics, 158b, 29-35. The algorithm does not require factoring the two integers.

Algorithm and implementation

Given two natural numbers a and b, check if b is zero. If yes, a is the gcd. If not, repeat the process using b and the remainder after integer division of a and b (written a modulo b below). The algorithm can be naturally expressed using tail recursion.

By keeping track of the quotients occurring during the algorithm, one can also determine integers p and q with ap + bq = gcd(ab). This is known as the extended Euclidean algorithm.

These algorithms can be used in any context where division with remainder is possible. This includes rings of polynomials over a field as well as the ring of Gaussian integers, and in general all Euclidean domains.

Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. This is equivalent to the following implementation, which is considerably less efficient than the method explained above:

 function gcd(a, b)
     while a ≠ b
         if a > b
             a := a - b
         else
             b := b - a
     return a

Proof of correctness

Suppose a and b are the numbers whose gcd has to be determined. And suppose the remainder of the division of a by b is t. Therefore a = qb + t where q is the quotient of the division. Now any common divisor of a and b also divides t (since t can be written as t = a − qb); similarly, any common divisor of b and t will also divide a. Thus the greatest common divisor of a and b is the same as the greatest common divisor of b and t. Therefore it is enough if we continue the process with the numbers b and t. Since t is smaller in absolute value than b, we will reach t = 0 after finitely many steps.

Running time

File:Euclidean algorithm running time X Y.png
Plot of the running time for gcd(x,y)

When analyzing the running time of Euclid's algorithm, it turns out that the inputs requiring the most divisions are two successive Fibonacci numbers, and the worst case requires O(n) divisions, where n is the number of digits in the input. However, it must be noted that the divisions themselves are not atomic operations (if the numbers are larger than the natural size of the computer's arithmetic operations), since the size of the operands could be as large as n digits. The actual running time is therefore O(n²).

This is, nevertheless, considerably better than Euclid's original algorithm, in which the modulus operation is effectively performed using repeated subtraction in O(2n) steps. Consequently, this version of the algorithm requires O(n2n) time for n-digit numbers, or O(mlog m) time for the number m.

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. An alternative algorithm, the binary GCD algorithm, exploits the binary representation used by computers to avoid divisions and thereby increase efficiency, although it too is O(n²); it merely shrinks the constant hidden by the big-O notation on many real machines.

Continued fractions

The quotients that appear when the Euclidean algorithm is applied to the inputs a and b are precisely the numbers occurring in the continued fraction representation of a/b. Take for instance the example of a = 1071 and b = 1029 used above. Here is the calculation with highlighted quotients:

1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0

From this, one can read off that

{\frac  {1071}{1029}}={\mathbf  {1}}+{\frac  {1}{{\mathbf  {24}}+{\frac  {1}{{\mathbf  {2}}}}}}.

This method can even be used for real inputs a and b; if a/b is irrational, then the Euclidean algorithm will not terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of a/b.

C/C++ code

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

This can be rewritten iteratively as:

int gcd(int a, int b) {
  while (b != 0) {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}


For example, the gcd of 1071 and 1029 is computed by this algorithm to be 21 with the following steps:

a       b       t

1071102942
10294221
42210
210

See also

References

Donald Knuth, The Art of Computer Programming, volume 1 and volume 2. Addison-Wesley.

External links

ca:Algorisme d'Euclides cs:Euklidův algoritmus de:Euklidischer Algorithmus es:Algoritmo de Euclides fr:Algorithme d'Euclide ko:유클리드 호제법 id:Algoritma Euklidean it:Algoritmo di Euclide lt:Euklido algoritmas hu:Euklidészi algoritmus nl:Algoritme van Euclides ja:ユークリッドの互除法 pl:Algorytm Euklidesa pt:Algoritmo de Euclides ru:Алгоритм Евклида sl:Evklidov algoritem fi:Eukleideen algoritmi zh:輾轉相除法