Faster GCD(n, m) in Java?

Question

I'm working on something that's going to need to use the GCD algorithm quite a bit, and I'd like it to be as fast as possible. I've tried the normal method, binary method, and a memoisation method I thought would work better than it did. I copied the binary method from here, with minor tweaks.

I've been using a class called TestGCD for testing, here's the whole thing:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestGCD
{
  private static class Pair<A>
  {
    private final A a_one;
    private final A a_two;

    public Pair(A a_one, A a_two)
    {
      this.a_one = a_one;
      this.a_two = a_two;
    }

    @Override
    public boolean equals(Object object)
    {
      if (this == object)
        return true;
      if (object == null)
        return false;
      if (!(object instanceof Pair))
        return false;

      final Pair other = (Pair) object;

      if (a_one == null)
        if (other.a_one != null)
          return false;
      if (a_two == null)
        if (other.a_two != null)
          return false;
      if (a_one.equals(other.a_one))
        if (a_two.equals(other.a_two))
          return true;
      if (a_one.equals(other.a_two))
        if (a_two.equals(other.a_one))
          return true;

      return false;
    }

    public A getFirst()
    {
      return a_one;
    }

    public A getSecond()
    {
      return a_two;
    }

    @Override
    public int hashCode()
    {
      final int prime = 31;
      int result = 1;

      final int aOneHash = a_one == null ? 0 : a_one.hashCode();
      final int aTwoHash = a_two == null ? 0 : a_two.hashCode();

      int resultOneWay = prime * result + aOneHash;
      resultOneWay += prime * result + aTwoHash;

      int resultOtherWay = prime * result + aTwoHash;
      resultOtherWay += prime * result + aOneHash;

      result += resultOneWay + resultOtherWay;
      return result;
    }

    @Override
    public String toString()
    {
      return String.format("%s, %s", a_one, a_two);
    }
  }

  private final static Map<Pair<Integer>, Integer> STORAGE = new HashMap<>();

  private static void addNewPairs(List<Pair<Integer>> newPairs, int result)
  {
    for (final Pair<Integer> pair : newPairs)
      STORAGE.put(pair, result);
  }

  private static int gcd(int x, int y)
  {
    if (x == 0)
      return y;
    if (y == 0)
      return x;

    int gcdX = Math.abs(x);
    int gcdY = Math.abs(y);

    if (gcdX == 1 || gcdY == 1)
      return 1;

    while (gcdX != gcdY)
      if (gcdX > gcdY)
        gcdX -= gcdY;
      else
        gcdY -= gcdX;

    return gcdX;
  }

  private static int gcdBinary(int x, int y)
  {
    int shift;

    /* GCD(0, y) == y; GCD(x, 0) == x, GCD(0, 0) == 0 */
    if (x == 0)
      return y;
    if (y == 0)
      return x;

    int gcdX = Math.abs(x);
    int gcdY = Math.abs(y);

    if (gcdX == 1 || gcdY == 1)
      return 1;

    /* Let shift := lg K, where K is the greatest power of 2 dividing both x and y. */
    for (shift = 0; ((gcdX | gcdY) & 1) == 0; ++shift)
    {
      gcdX >>= 1;
      gcdY >>= 1;
    }

    while ((gcdX & 1) == 0)
      gcdX >>= 1;

    /* From here on, gcdX is always odd. */
    do
    {
      /* Remove all factors of 2 in gcdY -- they are not common */
      /* Note: gcdY is not zero, so while will terminate */
      while ((gcdY & 1) == 0)
        /* Loop X */
        gcdY >>= 1;

      /*
       * Now gcdX and gcdY are both odd. Swap if necessary so gcdX <= gcdY,
       * then set gcdY = gcdY - gcdX (which is even). For bignums, the
       * swapping is just pointer movement, and the subtraction
       * can be done in-place.
       */
      if (gcdX > gcdY)
      {
        final int t = gcdY;
        gcdY = gcdX;
        gcdX = t;
      }  // Swap gcdX and gcdY.
      gcdY = gcdY - gcdX;                       // Here gcdY >= gcdX.
    }while (gcdY != 0);

    /* Restore common factors of 2 */
    return gcdX << shift;
  }

  private static int gcdMemoised(int x, int y)
  {
    if (x == 0)
      return y;
    if (y == 0)
      return x;

    int gcdX = Math.abs(x);
    int gcdY = Math.abs(y);

    if (gcdX == 1 || gcdY == 1)
      return 1;

    final List<Pair<Integer>> newPairs = new ArrayList<>();
    while (gcdX != gcdY)
    {
      final Pair<Integer> pair = new Pair<>(gcdX, gcdY);
      final Integer result = STORAGE.get(pair);
      if (result != null)
      {
        addNewPairs(newPairs, result);
        return result;
      }
      else
        newPairs.add(pair);

      if (gcdX > gcdY)
        gcdX -= gcdY;
      else
        gcdY -= gcdX;
    }

    addNewPairs(newPairs, gcdX);

    return gcdX;
  }

So is there a way of making this algorithm faster or is the original version the fastest I'm going to get? No suggestions of using another language please, I'm looking for an algorithm improvement. Clearly my memoisation attempt was an utter failure, but maybe someone here can see a flaw/improve on it.

Answer 1

Use Euclidean Algorithm for GCD

The algorithm is based on below facts.

1. If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
2. Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

Code:

        import java.util.*; 
        import java.lang.*; 
        class GFG 
        { 
            public static int gcd(int a, int b) 
            { 
                if (a == 0) 
                    return b; 

                return gcd(b%a, a); 
            } 

     public static void main(String[] args) 
    { 
        int a = 10, b = 15, g; 
        g = gcd(a, b); 
        System.out.println("GCD(" + a +  " , " + b+ ") = " + g); 

    } 
} 

Time Complexity: O(Log min(a, b))

Answer 2

Euclidean Algorithm used by author of the question (subtraction-based version) and accepted answer (mod-based) both seems to be quite not as efficient as Binary GCD Algorithm, so here it's code in java (taken from wikipidea)

static long gcd(long u, long v) {
    int shift;

    if (u == 0) return v;
    if (v == 0) return u;

    for (shift = 0; ((u | v) & 1) == 0; ++shift) {
        u >>= 1;
        v >>= 1;
    }

    while ((u & 1) == 0) {
        u >>= 1;
    }

    do {
        while ((v & 1) == 0) {
            v >>= 1;
        }

        if (u > v) {
            long t = v;
            v = u;
            u = t;
        }

        v = v - u;
    } while (v != 0);

    return u << shift;
}

However, Binary algorithm is not the fastest gcd algorithm. More here.

Answer 3

Here is what I came up with, on the same lines as @ILoveCoding

public static long gcd(long first, long second) {

    long big = 0;
    long small = 0;

    if(first > second) {
        big=first;
        small=second;
    }
    else {
        big=second;
        small=first;
    }

    long temp = big % small;
    while( (temp) > 1 ) {
        big = small;
        small = temp;
        temp = big % small;
    }

    if( temp == 0 ) {
        return small ;
    }
    else if( temp == 1) {
        return 1;
    }
    else {
        return -1; // will never occur. hack for compilation error.
    }

}

Edit: Test cases !

System.out.println( gcd(10L, 5L));
System.out.println( gcd(11L, 7L));
System.out.println( gcd(15L, 21L));
System.out.println( gcd(-2L, -5L));
System.out.println( gcd(-2L, 2L));

Answer 4

You can use Euclid's algorithm. It is very simple to implement and it is more efficient. Here is a code for it:

static int gcd(int a, int b) {
    while (b != 0) {
        int t = a;
        a = b;
        b = t % b;
    }
    return a;
}

The time complexity is O(log(A + B)), while the algorithms you are using are O(A + B). It scales better and is efficient for small a and b, too.