Java：求最大公约数，哪种方法更好？

Question

从这个问题Java：获得最大公约数

在获取任何数据类型的gcd时，无论是int，long，整数，Long，哪个答案在精度，速度，cpu使用等方面更好？

A:

private static int gcdThing(int a, int b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf((b))).intValue();
}

B：

public int GCD(int a, int b) { return b==0 ? a : GCD(b, a%b); }

Answer 1

标志：

我注意到的一个区别（除了性能）是标志处理不同，你的手实现了欧几里得算法GCD和我的gcdLongIterative表现相同，但两者都不同于大整数，后者倾向于“保持”标志因为他们是。似乎本质上，GCD和gcdLongIterative可以返回负数，而Bigintger将只返回正数。

GCD and gcdLongIterative implementations:
 -4/-2   => 2/1
-10/200  => 1/-20
 10/-200 => 1/-20

BigInteger implementation tends to 'keep' the signs:
 -4/-2   => -2/-1
-10/200  => -1/20
 10/-200 => 1/-20

当用于分数时，所有结果都是有效的，但如果您希望数字具有特定的“风格”，则值得考虑后处理标准化。

性能：

如果你想使用<代码> GCD < /代码>，因为那是比较快的，那么你应该考虑它的迭代实现：

  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return a;
  }  

受@Xabster benchmark的启发，我对其进行了扩展，以测试所有3种实现，在某些情况下，递归和迭代都执行相同的操作，但在大多数情况下，迭代的速度稍快一些：

(100 000 000 iterations)
gcd recursive:  3113ms
gcd iterative:  3079ms
gcd BigInteger: 13672ms

基准代码如下：

import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class Test {
  
  private static final int BENCHMARK_ITERATIONS = 100000000; 
  

  public static long gcdLong(long a, long b) {
    return b == 0 ? a : gcdLong(b, a % b);
  }

  
  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return a;
  }  
  
  
  public static long gcdLongBigInteger(long a, long b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf((b))).longValue();
  }

  
  public static String asFractionGcdLong(long a, long b) {
    long gcd = gcdLong(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }

  
  public static String asFractionGcdLongIterative(long a, long b) {
    long gcd = gcdLongIterative(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }
  
  
  public static String asFractionGcdLongBI(long a, long b) {
    long gcd = gcdLongBigInteger(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }
  
  
  public static void test(String actual, String expected) {
    boolean match = expected.equals(actual);
    
    if (match) {
      System.out.println("Actual and expected match=" + expected);      
    } else {
      System.out.println("NO match expected=" + expected + " actual=" + actual);            
    }
  }
  
  
  public static class Values {
    public long   a;
    public long   b;
    public String expected;

    public Values(long a, long b, String expected) {
      this.a = a;
      this.b = b;
      this.expected = expected;
    }
  }
  
  
  public static void validityTest() {
    List<Values> vals = new LinkedList<Values>(Arrays.asList(
        new Values(500, 1000, "1/2"),
        new Values(17,  3,    "17/3"),
        new Values(462, 1071, "22/51"),
        new Values(-4,  -2,   "2/1"),
        new Values(-10, 200,  "1/-20"),
        new Values(10,  -200, "1/-20")
    ));
    
    System.out.println("------  Recursive implementation -------");
    vals.forEach(v -> test(asFractionGcdLong(v.a, v.b), v.expected));
    System.out.println();    
    
    System.out.println("------  Iterative implementation -------");    
    vals.forEach(v -> test(asFractionGcdLongIterative(v.a, v.b), v.expected));
    System.out.println();    

    System.out.println("------  BigInteger implementation -------");    
    vals.forEach(v -> test(asFractionGcdLongBI(v.a, v.b), v.expected));
    System.out.println();    
  }

  
  public static void benchMark() {
    Random r = new Random();
    
    long[] nums = new long[BENCHMARK_ITERATIONS];
    for (int i = 0 ; i < nums.length ; i++) nums[i] = r.nextLong();

    System.out.println("Waming up for benchmark...");
    for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
    for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
    for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);

    System.out.println("Started benchmark...");
    long s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
    System.out.println("recursive:  " + (System.currentTimeMillis() - s) + "ms");

    s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
    System.out.println("iterative:  " + (System.currentTimeMillis() - s) + "ms");    
    
    s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);
    System.out.println("BigInteger: " + (System.currentTimeMillis() - s) + "ms");    
  }
  
  
  public static void main(String[] args) {
    validityTest();
    benchMark();
  }
  
}

Answer 2

    Random r = new Random();
    int[] ints = new int[500000];
    for (int i = 0 ; i < ints.length ; i++)
        ints[i] = r.nextInt();

    for (int i = 0 ; i < ints.length-1; i++)
        GCD(i,i+1);
    for (int i = 0 ; i < ints.length-1; i++)
        gcdThing(i, i + 1);

    long start = System.currentTimeMillis();
    for (int i = 0 ; i < ints.length-1; i++)
        GCD(i,i+1);
    System.out.println("GCD: " + (System.currentTimeMillis() - start));

    start = System.currentTimeMillis();
    for (int i = 0 ; i < ints.length-1; i++)
        gcdThing(i, i + 1);
    System.out.println("gcdThing: " + (System.currentTimeMillis() - start));

打印：

GCD： 13

gcdThing： 124