Java: Get Greatest Common Divisor, which method is better?
greatest-common-divisor, java
Solution
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));
Prints:
GCD: 13
gcdThing: 124
Problem
From this question Java: get greatest common divisor In getting the gcd of any data type whether `int`, `long`, `Integer`, `Long`, which answer is better in terms of precision, speed, cpu usage, etc.? 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); } ```