title: Faster GCD(n, m) in Java?
body: <p>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 <a href="https://en.wikipedia.org/wiki/Binary_GCD_algorithm" rel="nofollow">here</a>, with minor tweaks.</p>
  
  <p>I've been using a class called TestGCD for testing, here's the whole thing:</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  public class TestGCD
  {
    private static class Pair&lt;A&gt;
    {
      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&lt;Pair&lt;Integer&gt;, Integer&gt; STORAGE = new HashMap&lt;&gt;();
  
    private static void addNewPairs(List&lt;Pair&lt;Integer&gt;&gt; newPairs, int result)
    {
      for (final Pair&lt;Integer&gt; 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 &gt; 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) &amp; 1) == 0; ++shift)
      {
        gcdX &gt;&gt;= 1;
        gcdY &gt;&gt;= 1;
      }
  
      while ((gcdX &amp; 1) == 0)
        gcdX &gt;&gt;= 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 &amp; 1) == 0)
          /* Loop X */
          gcdY &gt;&gt;= 1;
  
        /*
         * Now gcdX and gcdY are both odd. Swap if necessary so gcdX &lt;= 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 &gt; gcdY)
        {
          final int t = gcdY;
          gcdY = gcdX;
          gcdX = t;
        }  // Swap gcdX and gcdY.
        gcdY = gcdY - gcdX;                       // Here gcdY &gt;= gcdX.
      }while (gcdY != 0);
  
      /* Restore common factors of 2 */
      return gcdX &lt;&lt; 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&lt;Pair&lt;Integer&gt;&gt; newPairs = new ArrayList&lt;&gt;();
      while (gcdX != gcdY)
      {
        final Pair&lt;Integer&gt; pair = new Pair&lt;&gt;(gcdX, gcdY);
        final Integer result = STORAGE.get(pair);
        if (result != null)
        {
          addNewPairs(newPairs, result);
          return result;
        }
        else
          newPairs.add(pair);
  
        if (gcdX &gt; gcdY)
          gcdX -= gcdY;
        else
          gcdY -= gcdX;
      }
  
      addNewPairs(newPairs, gcdX);
  
      return gcdX;
    }
  </code></pre>
  
  <p>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.</p>