Computer Science 2611
Summer 1999
Laboratory Assignment 2

Terminology, facts and an algorithm

All of the numbers for this assignment are nonnegative integers.

The greatest common divisor of two numbers n and m is the largest number k such that k is a divisor of both m and n. For example, the greatest common divisor of 15 and 35 is 5, and the greatest common divisor of 20 and 52 is 4. Notice that 1 is a divisor of every number, so there is always at least one common divisor to choose from. The greatest common divisor of 5 and 7 is 1. The greatest common divisor of m and n is written gcd(m,n).

One way to find the greatest common divisor of m and n is to try each possible number, starting at the smaller of m and n and counting down until a divisor of both is found. That turns out to be extremely slow. Another approach is to find the prime factorization of m and n, and to multiply together the common factors. That also turns out to be extremely slow.

The Greek mathematician Euclid discovered a simple and efficient way to find the greatest common divisor of two numbers. It is based on the following facts. 

        gcd(0,n) = n
        gcd(m,n) = gcd(n mod m, m)   (when m > 0)
where n mod m is the remainder when you divide n by m. (It is written n % m in C++.) An algorithm starts with two variables i and j set to m and n, respectively. At each stage, it replaces i and j by j mod i and i, respectively, using the fact 
        gcd(i,j) = gcd(j mod i, i)   (when i > 0)
That way, gcd(i,j) is always the same. Here is a sample run for n = 36 and m = 10. 
                i               j
              _____           _____
               10               36
                6               10
                4                6
                2                4
                0                2
Notice that gcd(10,36) = gcd(6,10) = gcd(4,6) = gcd(2,4) = gcd(0,2) = 2. The loop stops when i = 0, with the answer being j.

Assignment

Write a program that reads two integers m and n and prints the greatest common divisor of m and n. It should use Euclid's algorithm.

Include in your program an invariant for the loop that is used to compute the greatest common divisor. Also include the facts that are being used.

Make your program print the values of i and j, in a form similar to that shown above, so that you can see whether it is performing the algorithm correctly. Test your program. Do not just presume that it works.

Print this version. Then make a copy of your program, and remove the debugging prints so that it only shows the greatest common divisor of the two numbers. Also print the second version.

Turn in both printouts.