logo标签列表

在Java中如何更快地计算GCD（n，m）？

javaalgorithmgreatest-common-divisor
3
我正在处理一些需要频繁使用GCD算法的内容，希望它能够尽可能快。我尝试了常规方法、二进制方法和我认为会比二进制方法更好的备忘录方法。我从这里复制了二进制方法，并进行了微调。
我一直在使用名为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;
  }

那么有没有办法使这个算法更快，或者原始版本就是我能得到的最快的版本？请不要建议使用其他语言，请提供算法改进的建议。显然，我的记忆化尝试是彻底失败了，但也许在这里有人可以看到缺陷/改进它。

2
请使用Caliper来对您的代码进行基准测试。这些数字毫无意义。 - undefined
1
您正在寻找如何创建一个微基准测试，但是存在一些问题，主要是在main方法中，比如没有预热阶段等等。 - undefined
1
还有jmh，我尚未使用过。 - undefined
1
不要使用连续的减法 gcdY = gcdY - gcdX，而是使用取余操作 gcdY = gcdY % gcdX。在每次迭代中比较这两个数也是不必要的，因为你总是得到 gcdY < gcdX。 - user1196549
1
有人能帮我编辑一下我的帖子，把那些无用的基准测试信息和主方法删除掉吗？显然那是个坏主意。谢谢。 - undefined
显示剩余5条评论
4个回答
9
你可以使用欧几里得算法。它非常简单易懂，且效率更高。以下是实现该算法的代码:
```html

你可以使用欧几里得算法。它非常简单易懂，且效率更高。以下是实现该算法的代码:

```
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也很有效。

这正是我在寻找的东西。不幸的是，通过发布二进制版本和其他东西，我让它看起来像是在寻找微观优化，但实际上我真正想要的是改进大O表示法。谢谢 :) - undefined
@Jxek 我猜复杂度是 O(log(min(a,b))) :/ - undefined
1

欧几里德算法，问题的提问者使用的是减法版本，接受的答案使用的是模数版本，两者看起来都不如二进制最大公约数算法高效，这里是它的Java代码（来自维基百科）

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

然而，二进制算法并不是最快的最大公约数算法。更多信息请点击这里。
0

这是我想出来的，与@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.
    }

}

编辑：测试用例！

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));
0

使用欧几里得算法求最大公约数

该算法基于以下事实。

  1. 如果我们从较大的数中减去较小的数（减少较大的数），最大公约数不会改变。因此，如果我们反复减去两个数中较大的那个，最终得到的就是最大公约数。
  2. 现在，不再使用减法，而是将较小的数除以较大的数，当余数为0时，算法停止。

代码：

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

    } 
}

时间复杂度：O(Log min(a, b))
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接