Handed out: 9/1/09
You should find this a challenging assignment. Follow the instructions. Ask questions when you have trouble and do not see what to do. Do not just stare at the computer hoping for inspiration.
All of the numbers for this assignment are nonnegative integers.
The greatest common divisor (also called the greatest common factor) 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. Here is a Java program fragment 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. Recall that x % y is the remainder when you divide integer x by integer y. So x % y is 0 if x is divisible by y.
long g,m,n;
... (give m and n values 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 = g - 1;
}
We have not discussed how to get information from the user. Unfortunately, it is not a simple thing to do in Java, and it employs some advanced ideas. Here is a program fragment that will read two integers (of type long) from the keyboard and store them into m and n. For now, we will just use this without trying to understand what it is saying. Later, we will look at it in more detail. First, you will need to write
import java.io.*;
in your file, before the class starts, and you will need to add
throws Exception after the line that introduces the
main method. (See the program below.)
Then, when you need to read the numbers, do
the following.
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());
Notice that it writes a request for the numbers, and reads
each one.
You create a Java program by defining a class (a group of related things) and putting a main method in the class. Here is a complete program that asks the user for two integers and shows their greatest common divisor.
// Your name here
// Computer science 2311
// Lab assignment 2A
// 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 = g - 1;
}
System.out.println("The gcd of " + m + " and " + n + " is " + g);
}
}
Create a project. In your project, create a class called Program2a, and put the above program into it. Do not type it yourself. Just copy it from your browser and paste it into your program.
Try your program on small numbers. Does it seem to work?
Now try it on two 9 digit numbers. For example, try to get gcd(123456789, 987654321). Does it still work? Time it, and record how long it takes. (You can display a clock by double-clicking the clock at the lower-right of the screen.)
Now try it on two 10 digit numbers. For example try to get gcd(1234567890, 9123456789). Does it work? How long does it take?
How long do you think it will take to find the greatest common divisor of two 11 digit numbers?
If m is the smaller of the two numbers, then the loop might go through m times. So if m is about one million, it might need to go around one million times.
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) = 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 % i and i, respectively, using the fact
(2) gcd(m, n) = gcd(n % m, m) (when m > 0)
gcd(i, j) = gcd(j % 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 % 36 is 10. Does it work?
Create another project, with a class called Program2b. Copy what is in Program2a.java into Program2b.java. Leave the part that gets m and n from the user, and the part that writes out the answer. But delete the part that computes the greatest common divisor.
Remove variable g, and add two new variables i and j. Make them have type long.
Now make the program compute the greatest common divisor of m and n using Euclid's algorithm. Before starting the loop, make i = m and j = n. Then keep going as long as i > 0. How should you update i and j?
Test your program? Does it give correct answers? Whether or not it does, move on to the next section.
Good programmers do not just presume that their programs work. They turn on the lights to see what is happening. Make your program write out the values of i and j each time around the loop. Just inside the loop, before modifying i and j, add the following.
System.out.println("Loop: i = " + i + " j = " + j);
This is called a trace print.
Now run your program. Try it on 10 and 36.
Is the trace information what you expect?
If the trace is not what you expect, do a hand simulation to see why. Just run your loop carefully by hand. Can you duplicate what you are getting when you run the program? Can you see how to fix the problem? Feel free to create additional variables.
After you get Program2b.java working, comment out the trace print by writing // in front of it. Do not delete it entirely. Now try the program on numbers of 9, 10 and 11 digits. Does it produce the answer quickly?
Print both versions, Program2a.java and Program2b.java. Be sure that your name is part of both of them, in the comment at the top. The comment in Program2a.java should say that it is lab assignment 2A, and the comment in Program2b.java should say that it is lab assignment 2B. Turn in both.