Problem 3.3 - Finding greatest common divisors with iteration

Prime numbers and divisibility of numbers play prominent roles in current public key encryption systems. In particular, an algorithm for computing greatest common divisors reported by Euclid, circa 300 BC, is especially useful.

The greatest common divisor (GCD) of two non-negative integers is the largest integer that divides both values evenly (without producing a remainder).

A brute force approach to the problem of finding the GCD of two numbers might be to start with 2 and try dividing each of the two integers to see if it is a divisor. Then 3 could be tried, and so on, up to the smaller of the two integers, and we would thus find the largest divisor. Another approach might start with the smaller of the two integers and work down until we found a divisor. But if the two integers are very large, these approaches would still be very inefficient because they would be stepping through consecutive possibilities, and that would result in a very large number of times through a loop and a lot of division to perform.

Euclid's algorithm uses the fact that a common divisor of two numbers also divides the sum and difference of the two numbers. Euclid's original algorithm finds the GCD more quickly by doing repeated subtraction of the two numbers and replacing the larger of the numbers by this result. This process continues until the two numbers are equal. At that point, the GCD of the two numbers is just the value of either of the two equal numbers. (It should be obvious that the GCD of a number and itself is that number.)

For example, suppose we want to find the GCD of 24 and 16. The difference between the two numbers is 8, and so we replace the larger (24) by 8. Now we try again with the two values 8 and 16. The difference between these is 8, so we replace the larger (16 this time) by 8. We try again with the two values 8 and 8. But these two values are the same, so the GCD is 8.

When we code a loop, we always want to decide the test condition that determines when to quit the loop and when to keep going. In this algorithm, we are done with the loop when our two numbers are the same. It is also very important to make sure that each time through the loop, things change so that our condition for terminating the loop will evaluate differently, and eventually we will terminate the loop. In this algorithm, we are replacing the larger of the two numbers by a smaller one (we have subtracted the other one from it), so things are indeed changing. Moreover, one or the other of the numbers is getting smaller each time, so eventually our loop must terminate as the numbers are getting closer to each other.

The GCD is only defined for non-zero integers, so it might be a good idea to make sure that neither of the values is zero at the start. (What happens in this algorithm if one of the values is zero?)

It is also worth considering what happens if one or the other of our values is negative since subtracting a negative number from a positive number actually increases the number. Fortunately, when dealing with GCD, it is safe to consider the GCD to always be positive. Thus we can freely change the sign of our original numbers to be positive and still get the correct answer. For example, the GCD of -24 and 16 is also 8.

The Problem Statement

Following is a class definition that is only missing the computeGCD method that you must code.

// Calculate the GCD of two numbers

import java.util.Scanner;

class GCDTest {

    // Write the method computeGCD


    // Get two numbers from input and compute the GCD
    public static void main(String [] args) {

        Scanner input = new Scanner(System.in);
        System.out.print("Enter two integers: ");
        int a = input.nextInt();  // first argument is a
        int b = input.nextInt();  // second argument is b

        // Print value of compute method
        int gcd = computeGCD(a, b);
        System.out.println("The GCD of " + a + " and " + b + " is " + gcd);
    }
}

Test your code with examples you also verify by hand. Here are some examples:

C> java GCDTest
Enter two integers: 24 16
The GCD of 24 and 16 is 8
C> java GCDTest
Enter two integers: 512 333   
The GCD of 512 and 333 is 1
C> java GCDTest
Enter two integers: -80 75 
The GCD of -80 and 75 is 5

Note

What to turn in

Turn in your GCDTest.java. Make sure that it compiles and works for a variety of test cases.