The greatest common divisor of two numbers n and m, written gcd(m,n), is the largest number k such that k is a divisor of both m and n. For example,
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.
(1) gcd(0,n) = n (2) 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
m = 10 and n = 36.
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.
So, as i and j change, gcd(i,j) is always the same as gcd(m,n),
even though m and n do not change.
The loop stops when i = 0, with the answer being j.
Question: We tried Euclid's algorithm for m = 10 and n = 36. Does Euclid's algorithm work for the case of m = 36 and n = 10? Try it. What is 10 mod 36?
Put the gcd computation in a function, and use that function in your main program. The function should be called gcd, and should have the following form. Fill in the parts that are in italics.
////////////////////////////////////////////////////////////////////
// gcd
////////////////////////////////////////////////////////////////////
// gcd(m,n) returns the greatest common divisor of m and n.
//
// Requirement: m and n must be nonnegative integers, and they must
// not both be 0.
//
// Algorithm:
// The algorithm is Euclid's algorithm, based on the following facts.
//
// gcd(0,n) = n
// gcd(m,n) = gcd(n mod m, m) (when m > 0)
////////////////////////////////////////////////////////////////////
int gcd(int m, int n)
{
Declare i and j here.
i = m;
j = n;
Put the invariant here, as a comment.
Put the loop here.
return j;
}
Include in your function definition a comment stating an invariant for the loop that is used to compute the greatest common divisor. Put the comment just above the loop, and clearly label it as a loop invariant.
Make your program print the values of i and j each time around the loop, in a form similar to that shown in the description, 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 the program only shows the greatest common divisor of the two numbers. Also print the second version.
Turn in both printouts. Please put both your name and the assignment number at the top of both versions, as comments. Write "Assignment 2, part 1" on the first part and "Assignment 2, part 2" on the second.