Greatest Common Divisor (GCD) by Euclidean algorithm in Java

Question

I wrote this code for Greatest Common Divisor- GCD. I subtract smaller integer from bigger integer, then I remove biggest integer and subtract smaller integer from bigger integer again until two integers are equal and it's result. I'd like to know if this is correct and if it can be made simpler? Thank You.

public static void main(String[] args) {
    int firstInteger=114, secondInteger=67;


    if (firstInteger>secondInteger) {

        int result=firstInteger-secondInteger;

        while (firstInteger != secondInteger) {

            if (secondInteger > result) {
                firstInteger = secondInteger;
                secondInteger = result;
                result = firstInteger - secondInteger;
            } else {
                firstInteger = result;
                result = firstInteger - secondInteger;
            }
        }
        System.out.println(firstInteger);
    }
    else {

        int result=secondInteger-firstInteger;

        while (secondInteger!=firstInteger) {

            if (firstInteger>result)  {
                secondInteger=firstInteger;
                firstInteger=result;
                result=secondInteger-firstInteger;

            }
            else {
                secondInteger=result;
                result=secondInteger-firstInteger;
            }
        }
        System.out.println(secondInteger);
    }


}

"*I'd like to know if this is correct*" - Why not write some [tests](https://stackoverflow.com/questions/8751553/how-to-write-a-unit-test)? — Turing85, Aug 15 '20 at 23:02
Start with defining a method `int gcd(int a, int b)` so that you can call your code with several combinations of test values. When happy with your version, you can then re-implement gcd to call itself to recursively to cut down the number of lines considerably. — DuncG, Aug 16 '20 at 11:11

score 0 · Answer 1 · answered Aug 16 '20 at 15:38

The attitude is correct and the code will function as intended however, it will fail (lock into a continuous loop) if 0 is applied as a value to either firstInteger or secondInteger. The same applies to signed integer values. You would need to handle these situations should it they ever arise.

Although the code is quite long for the task it is intended to do, it does work. It can be shortened considerably if you approach the task with a different concept, for example, by utilizing the Modulo (%) Operator (aka: Remainder Operator) and carrying out a form of division to see if there is a remainder rather that carrying out subtractions and, ignoring which argument value is greater to begin with. Here is an example which can actually be used as a method:

public static int getGreatestCommonDivisor(int numerator, int denominator) {
    if (numerator <= 0 || denominator <= 0) {
        System.err.println("getGreatestCommonDivisor() Method Error! A value of "
                         + "zero (0) or less can not be supplied as an argument!");
        return -1;
    }
    int temp = numerator % denominator;
    while (temp > 0) {
        numerator = denominator;
        denominator = temp;
        temp = numerator % denominator;
    }
    return denominator;
}

If you want to handle signed argument values internally within the method then you can utilize the Math#abs() method which returns the absolute (Positive) value of a int value. This method gives the absolute value of the argument. The argument can be int, double, long and float but for this method we're only concerned with int type arguments. Here is an example:

public static int getGreatestCommonDivisor(final int numerator, final int denominator) {
    if (numerator == 0 || denominator == 0) {
        System.err.println("greatestCommonDivisor() Method Error! A value of "
                         + "zero (0) can not be supplied as an argument!");
        return -1;
    }
    int num = numerator;
    num = Math.abs(numerator);          // Ensure an absolute value
    int gcd = Math.abs(denominator);    // Ensure an absolute value
    int temp = num % gcd;
    while (temp > 0) {
        num = gcd;
        gcd = temp;
        temp = num % gcd;
    }
    return gcd;
}

combat womble · Answer 2 · 2020-08-16T22:54:20.910

Your code does work. Below is what I have programmed.

    public int calculateGCD(int highNumber, int lowNumber){
        boolean GCDFound = false;
        int quotient, remainder, GCD = 1;
         while(!GCDFound)
         {
            quotient = highNumber / lowNumber;
            remainder = Math.floorMod(highNumber, lowNumber);
            if(remainder == 0)
            {
                GCD = lowNumber;
                GCDFound = true;
            }
            else
            {
                highNumber = lowNumber;
                lowNumber = remainder;
            }
         }
         return GCD;
}`

There is no error handling. Neither number is zero or minus something.

I completed three tests on your (kamilP) code and on my code. Each test uses a 2d array of 1,000,000 pairs of numbers. The first array numbers are between 1 and 107,374,143, the second array numbers are between 107,374,143 and 2,147,483,646 and the third array numbers are between 1 and 2,147,483,646. The tests time how long it takes for the program to go through the array.

Results are as follows (in miliseconds): KamilP & CombatWomble

Array 1 273ms 155ms
Array 2 274ms 175ms
Array 3 285ms 173ms

This is my way of making it simpler and faster.

I tested @DevilsHnd codes he provided in his answer and the results were slightly quicker than mine: Array 1 = 138ms, Array 2 = 157ms, Array 3 = 150ms. — combat womble, Aug 16 '20 at 20:10
Thank You for your answer.I have a question.How did you do those tests? You created arrays in your code and put random numbers to those arrays to find GCD for each pair? — kamilP, Aug 20 '20 at 01:25
Each solution has been created as its own class, which has a constructor and a 'calculateGCD()' method. Each class then has multiple unit tests written to ensure their code works. e.g 2147483646 and 1368768 have a GCD of 6. Each class is then instantisated. Then I time how long it takes each class to iterate through the 2d array using claculateGCD(). I do not print the GCD number nor save it to file as this would add time. — combat womble, Aug 20 '20 at 13:09

WJS · Answer 3 · 2020-08-17T13:21:22.847

if it can be made simpler?

There are several ways to simplify it. Here are three.

The first case modifies your algorithm. I did not do performance analysis because it would require something like JMH which I don't have installed.
All cases handle positive and negative values.
The math automatically adjusts for numerator and denominator so the order of r and s when calling the method does not matter.
The second and third methods employ Euclids Algorithm
Both methods will throw exceptions upon division by 0.

In your method I used a single loop and corrected the two values to ensure positive results during subtraction.

public static int gcd(int r, int s) {
      // absolute value of r and s
      r = r > 0 ? r : -r;
      s = s > 0 ? s : -s;

      while (s > 0) {
          // find min(r,s)
          int t = r > s ? s : r;

          // find max(r,s)
          r = r > s ? r : s;

          s = t;
          r = r - s;
      }
      return r;
}

The second method is simple iteration and is probably the most efficient. However, the sign must be corrected before returning the GCD.

public static int gcd(int r, int s) {
    while (s != 0) {
        int t = r % s;
        r = s;
        s = t;
    }
    return r > 0 ? r : -r;
}

This is the recursive method. Once again the sign needs to be corrected.

public static int gcd(int r, int s) {
    if (s != 0) {
        return gcd(s, r % s);
    }
    return r > 0 ? r : -r;
}

Here is a test of possible variations of order and signs.

System.out.println(gcd(24, 36));
System.out.println(gcd(-24, 36));
System.out.println(gcd(24, -36));
System.out.println(gcd(-24, -36));
System.out.println(gcd(36, 24));
System.out.println(gcd(-36, -24));
System.out.println(gcd(36, -24));
System.out.println(gcd(-36, 24));

All three methods print.

Greatest Common Divisor (GCD) by Euclidean algorithm in Java

3 Answers3