Java: Get Greatest Common Divisor, which method is better?

Question

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

Tesler

Test it. Create a list or array of a lot of numbers and test the time each takes to run. Edit: It's probably not the BigInteger using one, because that tends to be slow even with tweaks. – Sandstone

If you'll change the second method from recursive to iterative it'll probably provide the best results. – Gallagher

Oh well, I haven't tried benchmarking codes yet. I guess I'll just test it myself. – Tesler

If the last thing you do before returning is to recurse, that's tail-recursion and is almost always better converted to a loop. (Recursion is generally NOT the best answer if the problem can be solved equally easily with a loop, and often isn't the best answer even if it can't.) – Bartz

B is an interesting algorithm. Seems to work but I'm having a bit of trouble at this late hour explaining to myself why it should work. – Bartz

Why wasn't https://mcmap.net/q/194745/-java-get-greatest-common-divisor considered ... I would expect subtraction to be much faster than division. – Plemmons

Answer 1

    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

Sandstone

This isn't really enough warm-up to give a serious answer for post-JIT speed... but it's the result I would expect. On the other hand, I'd bet an iterative solution would be still faster, especially after JITting. – Bartz

@Bartz I guess I'll try the iteration too, to check the best performance. – Tesler

@Bartz 50 million gives: GCD: 1246 gcdThing: 14114 and the warmup is quite a bit longer than the sum of those numbers but I don't time the warm up. – Sandstone

Also, @keshlam, can you provide some reference to that you need to call a method more than 50000 times for warmup? Because I can't. – Sandstone

Depends on the complexity of the code and exactly which JVM you're using (and what criteria it uses to kick off which stages of optimization). Rule of thumb I've been working with is five minutes of warmup, but I've also been working with much more complex systems. Unfortunately the best references I can think of aren't public. – Bartz

(And with more complicated systems you can also run into the fact that JIT behavior may not be fully deterministic. Serious Java benchmarking can get messy.) – Bartz

Surely, a measure in real time seconds is not a proper way to do it. This is JRE 8 latest early access build compiled with javac from same. I think you're vastly overcomplicating this thing. It's not a 1000k LOC enterprise server. – Sandstone

Answer 2

Signs:

One difference I noticed (besides the performance) that the signs are handled differently, your hand implemented Euclidean algorithm GCD and my gcdLongIterative behave the same, but both are different from BigInteger which tends to 'keep' the signs as they are. It seems that in essence the GCD and gcdLongIterative can return a negative number, while BigInteger will return positive only.

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

All results when used for fractions are valid, but it's worth considering post-process normalization if you expect the numbers in a specific 'style'.

Performance:

If you want to use the GCD as that is faster then you should consider an iterative implementation of it:

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

Inspired by @Xabster benchmark I extended it to test all 3 implementations, in some cases both recursive and iterative were performing the same, however the iterative is slightly faster in most of the cases:

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

The benchmark code is here:

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

Conscription