4

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

在获取任何数据类型的 gcd 时int，哪个long答案在精度、速度、cpu 使用率等方面更好？IntegerLong

A：

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

乙：

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

2 回答 2

3 
    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

gcd事物：124

于 2014-02-05T07:23:35.030 回答
1

迹象：

我注意到的一个区别（除了性能之外）是符号的处理方式不同，您手工实现的欧几里得算法GCD和我的gcdLongIterative行为相同，但两者都不同于BigInteger倾向于“保持”符号原样的方法。似乎本质上GCDandgcdLongIterative 可以返回负数，而 BigInteger 只会返回正数。

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

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

表现：

如果您想使用GCDas 更快，那么您应该考虑对其进行迭代实现：

  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();
  }
  
}
于 2021-08-31T11:40:02.997 回答