Euclid's algorithm for computing the greatest common divisor of two numbers. This implementation assumes n is not zero.
- if m = 0:
- return n
- return EuclidGCD(m, n mod m)
Since the above is tail-recursive, we can trivially rewrite it to get this iterative version:
while m > 0:
- (n, m) = (m, n mod m)
(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:
If n < 2m, then the sum is reduced by m > (n+m)/3.
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)).