Euclid's algorithm for computing the greatest common divisor of two numbers. This implementation assumes n is not zero.

{{{EuclidGCD(n, m):

• if m = 0:
  • return n
  else:
  • return EuclidGCD(m, n mod m)

}}}

Since the above is tail-recursive, we can trivially rewrite it to get this iterative version:

{{{IterativeEuclidGCD(n, m):

• while m > 0:

  • (n, m) = (m, n mod m)
  return n

}}}

(Here the multiple assignment means to compute both values on the right hand side and then assign them to the variables on the left-hand side.)

1. Proof of correctness

We'll show that g divides n and m if and only if it divides m and n mod m; this implies that the GCD of n and m never changes during each pass through the loop. At the end, we have GCD(n,0) = n.

Suppose g divides both n and m, i.e., that n = ag and m = bg for some a and b. Then n mod m = ag - cm for some c, which is ag - cbg = (a-cb)g. Thus any common divisor of n and m is also a common divisor of m and n mod m, which implies that the algorithm does not return anything smaller than the GCD.

Conversely, suppose that g divides both m and n mod m. Then n = (n mod m) + cm = ag + cbg is a multiple of g. So any common divisor of n and n mod m is also a common divisor of n and m. This implies that the algorithm does not return anything greater than the GCD.

2. Run time

Let's write a recurrence in terms of the sum of n and m. When the algorithm is first called, it may be that n is less than m, and so n = n mod m and the sum does not drop on the first pass through the loop. After the first call, we have than n > m. When n > m, consider two cases:

1. If n < 2m, then the sum is reduced by m > (n+m)/3.

2. If n > 2m, then the sum is reduced by at least n-m, which is again greater than (n+m)/3.

So we have

• T(n+m) <= T((2/3)(n+m)) + Theta(1)

which has the solution

• T(n+m) = O(log(n+m)).

By paying more attention to what happens during the first few iterations it is possible to reduce this still further to O(log(min n, m)).

---

CategoryAlgorithmNotes