Greatest Common Denominator/Divisor/Factor (Geek Style — Euclidean Algorithm)

I recall learning about performing fractional math when I was young. To be completely honest, I never actually learned an efficient way of determining greatest common denominator. I brute forced it most of the time, meaning I just kept trying numbers until it seemed like I got the right denominator. My method was very similar to what you see here at Kahn Academy. As part of an algorithms course, I needed to write a function to determine the Greatest Common Denominator. Any time you start talking about writing code

Any time you start talking about writing code, and you consider performing a function that “brute forces” an answer, your code will not run very fast. Sometimes, you have no choice but to brute force a solution. Sometimes there is a better way. In this case, brute force is not the best way. Here is how a brute force method would look:

import java.util.Scanner;

/**
 * Created by James Shinevar on 6/10/17.
 * james.shinevar@gmail.com
 * http://jamesshinevar.com
 */
public class GCDMain {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Please enter your first number:");
        long FirstNumber = input.nextLong();
        input.nextLine();
        System.out.println("Please enter your second number:");
        long SecondNumber = input.nextLong();
        input.nextLine();
        System.out.println("SlowGCD is: " + SlowGCD(FirstNumber,SecondNumber));
    }

    private static long SlowGCD(long FirstNumber, long SecondNumber) {
        long GCD = 0;

        for (long counter = 1; counter < (FirstNumber + SecondNumber); counter++) {
            if (FirstNumber % counter == 0) {
                if (SecondNumber % counter == 0) {
                    GCD = counter;
                }
            }
        }
        return GCD;
    }
}

This program gets two numbers from the user on lines 12 and 15. I used the “long” type in Java so you can put in huge numbers and see that this function will run very slowly. In fact, depending on how large the number is, you might never be able to see it stop running. Line 17 calls the function SlowGCD and gives it the two numbers.

SlowGCD runs a loop from 1 to the summation of both numbers. For every single number, it tries a modulus of the first number and the counter. If the modulus is 0, then it will do the same check with the second number. If that is also 0, then it sets the highest found GCD to the number of times the loop has been run. This sounds fancy when I’m typing it, so let me simplify that. For every number from 1 to the summation of both, it divides the first number by the number of times the loop has been run. If the remainder of that division problem is 0

This sounds fancy when I’m typing it, so let me simplify that. For every number from 1 to the summation of both, it divides the first number by the number of times the loop has been run. If the remainder of that division problem is 0, it will do the same check for the second number. If the second number also has a remainder of 0, then that is the largest GCD found… so far. The loop will continue until it has tried all numbers.

That is the brute force method. Go ahead, try some huge numbers, it will probably seem like the program is locked up. That is because this loop will take a long time to run.

Luckily for me, someone way smarter than I am, found a shortcut. On top that, this shortcut was discovered over 2200 years ago. His name is Euclid, and strangely enough, his algorithm is called the Euclidean Algorithm. Now, I’m not going to dive into the deep proofs to show why this works. If you want to, there are plenty of resources out there. You can check out Wikipedia’s entry on it here. I am just going to discuss how it works. What we want to do is take the largest number and divide it by the smaller number. If the remainder is 0, then the lower number is the GCD. If not, take the lower number and divide it by the remainder and check again. This will continue until the GCD is found.

In code, I accomplished it like this:

import java.util.Scanner;
/**
 * Created by James Shinevar on 6/10/17.
 * james.shinevar@gmail.com
 * http://jamesshinevar.com
 */
public class GCDMain {

    public static long FinalGCD;

    {
        FinalGCD = 0;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Please enter your first number:");
        long FirstNumber = input.nextLong();
        input.nextLine();
        System.out.println("Please enter your second number:");
        long SecondNumber = input.nextLong();
        input.nextLine();
        FastGCD(FirstNumber, SecondNumber);
        System.out.println("FastGCD is: " + FinalGCD);
    }
  
    private static void FastGCD(long FirstNumber, long SecondNumber) {
        if (SecondNumber > FirstNumber) {
            long largerNumber = SecondNumber;
            SecondNumber = FirstNumber;
            FirstNumber = largerNumber;
        }
        if (FirstNumber == 0) {
            FinalGCD = SecondNumber;
        } else if (SecondNumber == 0) {
            FinalGCD = FirstNumber;
        } else {
            long ModulusResult = FirstNumber % SecondNumber;
            FirstNumber = SecondNumber;
            SecondNumber = ModulusResult;
            FastGCD(FirstNumber, SecondNumber);
        }
    }
}

In this code, I want to point out that I used a global variable. That just means a variable that can be accessed from anywhere, and there might be a better way to do this without a global variable, but I did it to be simple. That global variable is FinalGCD. This code gets the input the same way as above and then runs FastGCD. First, I make sure I know what the largest number is by making sure that “FirstNumber” is greater than “SecondNumber” in lines 28–32. Then… just in case, I check both numbers for a 0. If either of them is 0, the other result is the GCD. Then I perform the division and make the first number the smaller number and the remainder the second number and run the same function again.

This function is called a “recursive” function meaning that it will run itself until it finds the GCD. Give this one a try, even huge numbers will be returned almost instantly. This makes the Euclidean Algorithm much faster, and this is how I implemented it.

Please feel free to check out the whole set of code on my GitHub at https://github.com/jshinevar/Greatest-Common-Divisor/ If you have any comments or critiques, please feel free to give me those as well.

References

Euclidean algorithm. (2017). Sites.math.rutgers.edu. Retrieved 10 June 2017, from http://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html

Euclidean algorithm. (2017). En.wikipedia.org. Retrieved 10 June 2017, from https://en.wikipedia.org/wiki/Euclidean_algorithm

Greatest common factor explained. (2017). Khan Academy. Retrieved 10 June 2017, from https://www.khanacademy.org/math/pre-algebra/pre-algebra-factors-multiples/pre-algebra-greatest-common-divisor/v/greatest-common-divisor

Originally published at http://jamesshinevar.com on June 10, 2017.