Euclidean algorithm

From Free net encyclopedia

Revision as of 16:08, 13 April 2006; view current revision
←Older revision | Newer revision→

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. Its major significance is that it does not require factoring the two integers. It is also significant in that it is one of the oldest algorithms known, dating back to the Greeks. The algorithm works by repeatedly dividing the two numbers and the remainder in turns. The Euclidean algorithm is not restricted to integers; it may be used to compute gcd of elements of any Euclidean domain, for example polynomials over a field.

1 History
2 Description of the algorithm
3 Proof of correctness
4 Running time
5 Relation with continued fractions
6 Generalisation to Euclidean domains
7 See also
8 References
9 External links

[edit]

History

The Euclidean algorithm is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. 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. However, the algorithm was probably 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.

[edit]

Description of the algorithm

Given two natural numbers a and b, and assuming a is greater than or equal to 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 by b (written a modulo b below). The algorithm can be naturally expressed using tail recursion such as the following pseudocode:

 function gcd(a, b)
     if b = 0 return a
     else return gcd(b, a mod b)

The original algorithm as described by Euclid treated it as a geometric problem, and hence used repeated subtraction of the smaller number from the larger number rather than integer division. This is equivalent to the following pseudocode, 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

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

As an example, consider computing the gcd of 1071 and 1029, which is 21, with this algorithm:

a	b	Explanation
1071	1029	Step 1: We start by putting the larger number on the left, and the smaller on the right.
1029	42	Step 2: The remainder of 1071 divided by 1029 is 42, which is put on the right, and the divisor 1029 is put on the left.
42	21	Step 3: We repeat step 2, dividing 1029 by 42, and get 21 as remainder.
21	0	Step 4: Repeat step 2 again, since 42 is divisible by 21, we get 0 as remainder, and the algorithm terminates. The number on the left, that is 21, is the gcd as required.

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. Applying the algorithm to the more general case other than natural number will be discussed in more detail later in the article.

[edit]

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.

[edit]

Running time

Image:Euclidean algorithm running time X Y.png

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(2ⁿ) steps. Consequently, this version of the algorithm requires O(n2ⁿ) 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.

[edit]

Relation with 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

<math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}}</math>.

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.

[edit]

Generalisation to Euclidean domains

The Euclidean algorithm can be applied to some rings, not just the integers. The most general context in which the algorithm terminates with the greatest common divisor is the so-called Euclidean domain. These include the Gaussian integers and polynomial rings over a field.

As an example, consider the ring of polynomials with rational coefficients. In this ring, division with remainder is carried out using long division, also known as synthetic division. The resulting polynomials are then made monic by factoring out the leading coefficient.

We calculate the greatest common divisor of

and

Following the algorithm gives these values:

a	b
<math>x^4-4x^3+4x^2-3x+14</math>	<math>x^4+8x^3+12x^2+17x+6</math>
<math>x^3+\frac{2}{3}x^2+\frac{5}{3}x-\frac{2}{3}</math>	<math>x^4-4x^3+4x^2-3x+14</math>
<math>x^2+x+2</math>	<math>x^3+\frac{2}{3}x^2+\frac{5}{3}x-\frac{2}{3}</math>
<math>0</math>	<math>x^2+x+2</math>

This agrees with the explicit factorization. For general Euclidean domains, the proof of correctness is by induction on some size function. For the integers, this size function is just the identity. For rings of polynomials over a field, it is the degree of the polynomial (note that each step in the above table reduces the degree by one).

[edit]