java - Java中更快的GCD(n，m)？

我正在研究一些需要使用gcd算法的东西，我希望它能尽快使用。我试过普通的方法，二进制的方法，还有一种记忆方法，我认为比它更好用我从here中复制了二进制方法，并做了一些小调整。
我一直在使用一个名为TestGCD的类进行测试，下面是整个过程：

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;
  }

那么有没有一种方法可以让这个算法更快呢，还是说原始版本是我得到的最快的呢没有使用另一种语言的建议，我正在寻找算法的改进。很明显，我的回忆录尝试完全失败了，但也许这里有人能看到它的缺陷/改进。

最佳答案

你可以用欧几里得算法。它的实现非常简单，而且效率更高这里有一个代码：

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

时间复杂度为O(log(A + B))，而使用的算法为O(A + B)。它的伸缩性更好，对小的a和b也是有效的。