[FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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)).

2014-06-17 11:58