Handed out: 1/19/05
You should find this a challenging assignment. Follow the instructions. Ask questions when you have trouble and do not see what to do.
All of the numbers for this assignment are nonnegative integers.
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,
When you learned division in grade school, you learned to compute a quotient and a remainder. For example, when you divide 20 by 3, you get a quotient of 6 and a remainder of 2.
Mathemeticians write x mod y to mean the remainder when you divide x by y. For example 20 mod 3 is 2, since when you divide 20 by 3, the remainder is 2.
Java has a somewhat peculiar notation for the same thing. In Java, you write x % y for the remainder when you divide x by y. In a Java program, I will write %, but when just discussing ideas, I will write the more common mod.
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. Here is a program fragment in Java that uses this approach to set g = gcd(m,n). It assumes that m and n have already been given values. It uses type long for integers, which is similar to int, but allows larger integers.
long g,m,n;
... (give m and n a value here)
//-------------------------------------------
// Make g be the smaller of m and n to start.
//-------------------------------------------
if(m < n) g = m;
else g = n;
//-------------------------------------------------
// Decrease g until g is a divisor of both m and n.
// This loop will have to stop, since 1 is a divisor
// of both m and n.
//-------------------------------------------------
while(n % g != 0 || m % g != 0)
{
g--;
}
Although this approach works for small values, it is
extremely slow when m and n are large.
For example, if m and n are each in the
vicinity of one million, then the loop might need to go
through about a million times.
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 for large numbers, because finding prime factors is difficult.
The Greek mathematician Euclid discovered a simple and efficient way to find the greatest common divisor of two numbers quickly. It is based on the following facts.
(1) gcd(0,n) = nAn 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
(2) gcd(m,n) = gcd(n mod m, m) (when m > 0)
gcd(i,j) = gcd(j mod i, i) (when i > 0)That way, even as i and j change, gcd(i,j) is always the same. Here is a sample run for m = 10 and n = 36. Each line shows the values of i and j when you reach the top of the loop.
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. The value of 10 mod 36 is 10. Does it work?
You want to write a program that reads two numbers m and n and prints their greatest common divisor. Here is a Java program that does the job, using the naive algorithm for computing gcd. Copy this program from the browser to Eclipse, and save it as program2a. (Just mark the section with the mouse, use edit/copy, then go to the Eclipse and use edit/paste. Do not put spaces in the file name.)
// Your name here
// Computer science 2311
// Programming assignment 2A, submission 1
// Date here
// This program reads two numbers from the user and
// prints their greatest common divisor.
import java.io.*;
public class program2a
{
public static void main(String[] args) throws Exception
{
long g,m,n;
InputStreamReader reader = new InputStreamReader(System.in);
BufferedReader keyboard = new BufferedReader(reader);
System.out.println("Compute the gcd of what two numbers?");
System.out.print(" m = ");
m = Long.parseLong(keyboard.readLine());
System.out.print(" n = ");
n = Long.parseLong(keyboard.readLine());
//-------------------------------------------
// Make g be the smaller of m and n to start.
//-------------------------------------------
if(m < n) g = m;
else g = n;
//-------------------------------------------------
// Decrease g until g is a divisor of both m and n.
// This loop will have to stop, since 1 is a divisor
// of both m and n.
//-------------------------------------------------
while(n % g != 0 || m % g != 0)
{
g--;
}
System.out.println("The gcd of " + m + " and " + n + " is " + g);
}
}
Run the program.
Try it first with some small numbers. Then try it with numbers that
are exactly 9 digits long.
Save your program as program2b. You will need to change the class name, since it must match the file name. Edit the comment at the top, since this is now assignment 2 part b. Now modify program2b so that it uses Euclid's algorithm to compute greatest common divisors.
You will need variables i and j, of type long. Be careful how you update i and j. Write the body of the loop, then try it by hand, using the example of 10 and 36. Does it work? If not, fix it. Feel free to create another variable.
Good programmers do not just presume that their programs work. They turn on the lights to see what is happening. Make your function print the values of i and j each time around the loop. Just inside the loop, put
System.out.println("i = " + i + " j = " + j);
This is called a trace print.
Now run your program. Try it on 10 and 36.
Does it seem to work? Is the trace information what you expect?
Save your program as program2c. Rename the class. Remove the trace print from it. Run it. Does it seem to work? Try it on some numbers that are exactly 9 digits long. Is it more efficient than the naive algorithm?
Print all three versions, program2a, program2b and program2c. Turn in all three parts, put together.