Search code examples
javagreatest-common-divisor

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


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

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