GCD Algorithm: Greatest Common Divisor in Java

Here are three different implementations of the classic GCD (Greatest Common Divisor) problem.

Iterative (Linear)

It wouldn’t make sense to ever implement the iterative linear approach due to its time complexity, but I’ve included it anyway.

    /**
     * Linear GCD method.
     *
     * @param a
     * @param b
     * @param b
     * @param i The number of iterations performed.
     *
     * @return GCD between a and b.
     */
    public static int gcd_linear(int a, int b, int i)
    {
        // Store the initial divisor check.
        int divisor = b;

        // Iterate through the divisor, decrementing downwards.
        while(divisor >= 1){
            // Check if a and b are divisible by the divisor.
            if(a % divisor == 0 && b % divisor == 0){

                // We have the GCD.
                return divisor;

            }
            // Decrement the divisor.
            divisor--;
            // Increment iterations.
            i++;
        }

        // We should never reach this point, but we put this
        // to satisfy the compiler. Either way, it would logically make
        // sense to return 1.
        return 1;
    }

Recursive

The recursive algorithm is the simplest in it’s form, but the recursive calls on a large input will clog up the stack.

    /**
     * Recursive method to finding the GCD.
     *
     * @param a
     * @param b
     * @param i The number of iterations performed.
     *
     * @return GCD between a and b.
     */
    public static int gcd_rec(int a, int b, int i)
    {
        // If b = 0, return a.
        if(b == 0){

            // Return the gcd.
            return a;
        }

        // Recursively call, and increment iterations.
        return gcd_rec(b, a % b, ++i);
    }

Iterative (Euclid’s Algorithm)

Therefore, the iterative approach using Euclid’s algorithm is probably the best way to go in terms of real-world implementation.

    /**
     * Iterative method to finding the GCD, using Euclid's algorithm.
     *
     * @param a
     * @param b
     * @param i The number of iterations performed.
     *
     * @return GCD between a and b.
     */
    public static int gcd_iter(int a, int b, int i)
    {
        // Store remainder.
        int remainder;

        // Check for gcd.
        do {
            remainder = a % b;
            a = b;
            b = remainder;
            // Increment iterations.
            i++;
        } while (remainder > 0);

        // Return the gcd.
        return a;
    }

If you want to test the performance of these algorithms, print the i parameter in each of the functions to see how many iterations were performed in calculating the GCD.