Euclidean algorithm

This article is not about Euclidean geometry.

In number theory, the Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (GCD) of two integers or elements of any Euclidean ___domain (for example, polynomials over a field) by repeatedly dividing the two numbers and the remainder in turns. Its major significance is that it does not require factoring the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks.

History of the Euclidean algorithm

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.

this boring and i dont like to do this on my course

This is boring i hate this stuff lol

Running time

Plot of the running time for gcd(x,y). Red indicates a fast computation, while successively bluer points indicate slower computations

When analyzing the running time of Euclid's algorithm, it turns out that the inputs requiring the most divisions are two successive Fibonacci numbers (because their ratios are the convergents in the slowest continued fraction expansion to converge, that of the golden ratio), and the worst case requires O(n) divisions, where n is the number of digits in the input. However, the divisions themselves are not constant time operations; the actual time complexity of the algorithm is $O(n^{2})$ . The reason is that division of two n-bit numbers takes time $O(n(m+1))$ , where m is the length of the quotient. Consider the computation of gcd(a,b) where a and b have at most n bits, let $a_{0},\dots ,a_{k}$ be the sequence of numbers produced by the algorithm, and let $n_{0},\dots ,n_{k}$ be their lengths. Then $k=O(n)$ , and the running time is bounded by

O{\Big (}\sum _{i<k}n_{i}(n_{i}-n_{i+1}+2){\Big )}\leq O{\Big (}n\sum _{i<k}(n_{i}-n_{i+1}+2){\Big )}\leq O(n(n_{0}+2k))\leq O(n^{2}).

This is considerably better than Euclid's original algorithm, in which the modulus operation is effectively performed using repeated subtraction in $O(2^{n})$ steps. Consequently, that version of the algorithm requires $O(2^{n}n)$ time for n-digit numbers, or $O(m\log {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.

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

{\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.

boring boring broing lol

boring lol

boring

ummmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm boring

PHP/JavaScript implementation

PHP

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

JavaScript

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

References

Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sections 4.5.2–4.5.3, pp.333–379.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp.856–862.

External links