Programming Assignment I - A Solution

Problem:

Given two integer, a and b, with a < b, find the greatest common divisor of the two numbers, and find a linear combination of a and b which equals the greatest common divisor.
Solution:

Let us begin with our standard example to get an idea of how to proceed.

We carry out the Euclidean Algorithm as follows.
13 = 1*8 + 5
8 = 1*5 + 3
5 = 1*3 + 2
3 = 1*2 + 1
2 = 2*1 + 0
The last non-zero remainder is the greatest common divisor.

Now we find the coefficients to give us a linear combination. 

      1   1   1   1
0  1  1   2   3   5
1  0  1   1   2   3
So the absolute value of the coeffient of 8 is 5, and the absolute value of the coefficient of 13 is 3. Since 5*8 > 3*13, the actual coefficient of 13 is -3, and the actual coefficient of 8 is 5.

So for this example we have the following outcome.
a b Greatest Common Divisor Coefficient of a Coefficient of b
8 13 1 5 -3

Examine the first line of the algorithm. 

13 = 1*8 + 5
We divide 13 by 8 to get quotient 1 and remainder 5. Note our two operations which will give us the quotient and remainder.

To get the quotient of 13/8 we can use the casting operator. To get the remainder we can use the modulus operator, 13 % 8.

In the first line of the algorithm, b = 13, and a = 8. 

(int)(b/a) = 1

b % a = 5
In the second line of the algorithm the new value of b is the old value of a, and the new value of a is the remainder from the previous line.

This process continues until the remainder is found to be 0.

So let's list the algorithm used to find the greatest common divisor. 

1. Get a and b with a < b.

2. Introduce a variable called remainder and initialize it to 1.
(Note that since our condition for stopping the Euclidean
Algorithm is that the remainder become 0, we can set remainder
to any integer value greater than 0.)

3. Repeat the following steps as long as remainder is greater than 0.

   Let quotient equal to the integer value of b/a.

   Let remainder equal to the remainder in the division b/a.

   Let b equal to the current value of a.

   Let a equal to remainder
Now what is the value of the greatest common divisor?

Recall that the last non-zero remainder is the greatest common divisor.

Now notice the last two lines of our example. 

3 = 1*2 + 1

2 = 2*1 + 0
Now notice what happens when b = 3 and a = 2.

The value of the quotient is 1.

The value of the remainder is 1.

Then b is reset to 2, and a is reset to 1.

We know that the greatest common divisor is 1 and this value has been placed into a after we complete the next to last line in the algorithm.

Now b is 2 and a is 1.

The quotient is 2, and the remainder is 0.

So we know that this is the last step in the algorithm.

However we don't make the test until the top of the loop so we still reset the values of a and b.

b is reset to 1, and a is reset to 0.

Notice that the greatest common divisor has been placed into b.

Now we go to the top of the loop and since the remainder is now 0, the loop stops.

So after we complete the Euclidean Algorithm, the variable b contains the greatest common divisor.

The code used to accomplish the Euclidean Algorithm is as follows. Assume that quotient, b, and a are defined to be integers. 

int remainder = 1;

while (remainder > 0) {
   quotient = (int)(b/a);
   remainder = b % a;
   b = a;
   a = remainder;
}
Notice the placement of the assignment statements.

Now let us modify this algorithm to compute the coefficients in the table.

First b is reassigned to the value of a. Then a is reassigned to the value of remainder.

The order is important. If we reassign the value of a first, then we have lost the old value of a. Now let us modify this algorithm to compute the coefficients in the table.

Examine the first column of the table. 

      1
0  1  1
1  0  1
Let us assign variable names to make the discussion easier to follow. In the first row let us call the two entries coef_a and coef_a1, and the two entries in the second row coef_b and coef_b1. 

                                
                                     1 (quotient)
0 (coef_a) 1 (coef_a1)               1
1 (coef_b) 0 (coef_b1)               1
Now to compute the entry in the top row we use the formula 
quotient*coef_a1 + coef_a
To compute the entry in the bottom row we use the formula 
quotient*coef_b1 + coef_b
Once these values have been computed, we then will adjust these variables to point to the new values. 
              1 (quotient)
0  1 (coef_a) 1 (coef_a1)
1  0 (coef_b) 1 (coef_b1)
Now let us see how these values change as we go through the Euclidean Algorithm. 
      1          1 (quotient)
0  1  1 (coef_a) 2 (coef_a1)
1  0  1 (coef_b) 1 (coef_b1)

      1  1          1 (quotient)
0  1  1  2 (coef_a) 3 (coef_a1)
1  0  1  1 (coef_b) 2 (coef_b1)

      1  1  1          1 (quotient)
0  1  1  2  3 (coef_a) 5 (coef_a1)
1  0  1  1  2 (coef_b) 3 (coef_b1)
Notice that the computation of a new column in the table depends upon the quotient and the two values directly to the left of the position.

So we can modify the Euclidean Algorithm to make these computations.

Note one problem however.

When we wish to compute the new value of coef_a1, it depends upon both coef_a1 and coef_a. 

the new value of coef_a1 = quotient*coef_a1 + coef_a
After this computation is complete, the value of coef_a is the old value of coef_a1.

But how can I make these two variables the correct values?

I can't simply make the assignment 

coef_a1 = quotient*coef_a1 + coef_a
because I will lose the current value of coef_a1.

I can't assign coef_a1 into coef_a before I compute the new value of coef_a1 because I need the current value of coef_a.

One solution is to store the value of coef_a1 into a temporary variable, compute the new value of coef_a1, and then assign the stored value of coef_a1 into coef_a.

The algorithm for doing this is 

store coef_a1 into a temporary integer variable
compute the new value of coef_a1
copy the stored value of coef_a1 into coef_a
We can compute the new value of coef_b in the same way. Now a question to ask is what will be the values of these variables when the Euclidean Algorithm stops. Notice that in the last column listed we have the last non-zero remainder. That is after we compute the quotient 2 and the remainder 0 we again recompute the values of coef_a1 and coef_a. So we will have one more column included. 

      1  1  1  1           2 (quotient)
0  1  1  2  3  5 (coef_a) 13 (coef_a1)
1  0  1  1  2  3 (coef_b)  8 (coef_b1)
After the variables are calculated, then the Algorithm stops. So after the Euclidean Algorithm stops, the absolute values of the coefficients of a and b are stored in the variables coef_a and coef_b, respectively.

So now we can test to see which product is larger, coef_a*a or coef_b*b, and then the one that is smaller will have a negative coefficient.

Now let us modify our Algorithm. 

1. Get a and b with a < b.

2. Introduce a variable called remainder and initialize it to 1.
(Note that since our condition for stopping the Euclidean
Algorithm is that the remainder become 0, we can set remainder
to any integer value greater than 0.)

3. Introduce a new variable called coef_a and initialize it to 0.
   Introduce a new variable called coef_a1 and initialize it to 1.
   Introduce a new variable called coef_b and initialize it to 1.
   Introduce a new variable called coef_b1 and initialize it to 0.
   Introduce an integer called temp.

4. Repeat the following steps as long as remainder is greater than 0.

   Let quotient equal to the integer value of b/a.

   Store coef_a1 into temp.

   Compute the new value of coef_a1.

   Store temp into coef_a.

   Store coef_b1 into temp.

   Compute the new value of coef_b1.

   Store temp into coef_b.

   Let remainder equal to the remainder in the division b/a.

   Let b equal to the current value of a.

   Let a equal to remainder
So when this algorithm completes, the greatest common divisor will be in the variable b, the absolute value of the coefficient of a will be in coef_a, and the absolute value of the coefficient of b will be in coef_b. To decide which coefficient should be negative we make a simple test.

(Note here that we need to use the original values of a and b.) 

if (coef_a*a < coef_b*b)
   negate coef_a
else
   negate coef_b
One last part of the program is to test for the case where a is a divisor of b. In this case we don't need to carry out the Euclidean Algorithm because we know that the greatest common divisor of a and b is a. The coeffients of a and b will be 1 and 0.

The algorithm to accomplish this is 

if (a is a divisor of b)
   report that a is the greatest common divisor of a and b.
   report that the coefficient of a is 1.
   report that the coefficient of b is 0.
else {
   carry out the Euclidean Algorithm.
   report the greatest common divisor.
   report the coefficient of a.
   report the coefficient of b.
}
Now let's list the complete algorithm. One thing we need to keep in mind is that the values of b and a will be changed through the algorithm. So since I need those original values later, I will store them in temporary variables once they are read in. 

1. Introduce the integer variables, a, b, quotient, remainder,
temp, coef_a, coef_a1, coef_b, coef_b1, temp_a, and temp_b. a
and b will be input from the user. We can swap their values
if necessary. After a and b are read in, copy them into temp_a
and temp_b, respectively.

2. if (a is a divisor of b) {
      report that a is the greatest common divisor of a and b.
      report that the coefficient of a is 1.
      report that the coefficient of b is 0.
   } else
      go to step 3.

3. while (remainder is greater than 0) {
      let quotient = (int)(b/a)

      let temp = coef_a1

      let coef_a1 = quotient*coef_a1 + coef_a

      let coef_a = temp

      let temp = coef_b1

      let coef_b1 = quotient*coef_b1 + coef_b

      let coef_b = temp

      let remainder = b % a

      let b = a

      let a = b
   }

   report that b is the greatest common divisor
   
   if (coef_a*temp_a is less than coef_b*temp_b)
      let coef_a = -1*coef_a
   else
      let coef_b = -1*coef_b

   report that coef_a is the coefficient of temp_a

   report that coef_b is the coefficient of temp_b
Now let us translate this algorithm into Java code. 
import java.io.*;

public class GCD {

   public static void main(String[] args) throws IOException {
      int a,b,quotient,remainder = 1;
      int coef_a = 0,coef_a1 = 1,coef_b = 1,coef_b1 = 0;
      int temp,temp_a,temp_b;

      InputStreamReader stream = new InputStreamReader(System.in);
      BufferedReader keyboard = new BufferedReader(stream);

      System.out.println("Please enter the value of a");

      a = new Integer(keyboard.readLine()).intValue();

      temp_a = a;

      System.out.println("Please enter the value of b");

      b = new Integer(keyboard.readLine()).intValue();

      temp_b = b;

      if (b % a == 0) {
         System.out.println("The greatest common divisor of " + a + " and " + b + " is " + a + ".");
         System.out.println("The coefficient of " + a + " is 1.");
         System.out.println("The coefficient of " + b + " is 0.");
      } else {
         while (remainder > 0) {
            quotient = (int)(b/a);
            temp = coef_a1;
            coef_a1 = quotient*coef_a1 + coef_a;
            coef_a = temp;
            temp = coef_b1;
            coef_b1 = quotient*coef_b1 + coef_b;
            coef_b = temp;
            remainder = b % a;
            b = a;
            a = remainder;
         }
         System.out.println("The greatest common divisor of " + temp_a + " and " + temp_b + " is " + b + ".");
         if (coef_a*temp_a < coef_b*temp_b)
            coef_a *= -1;
         else
            coef_b *= -1;
         System.out.println("The coefficient of " + temp_a + " is " + coef_a + ".");
         System.out.println("The coefficient of " + temp_b + " is " + coef_b + ".");
      }
   }

}
Here is sample output from the program. 
Please enter the value of a
8
Please enter the value of b
13
The greatest common divisor of 8 and 13 is 1.
The coefficient of 8 is 5.
The coefficient of 13 is -3.

Please enter the value of a
15
Please enter the value of b
100
The greatest common divisor of 15 and 100 is 5.
The coefficient of 15 is 7.
The coefficient of 100 is -1.

Please enter the value of a
5
Please enter the value of b
10
The greatest common divisor of 5 and 10 is 5.
The coefficient of 5 is 1.
The coefficient of 10 is 0.

Please enter the value of a
10
Please enter the value of b
40
The greatest common divisor of 10 and 40 is 10.
The coefficient of 10 is 1.
The coefficient of 40 is 0.