8
\$\begingroup\$

I previously discussed the performance concerns about different GCD algorithms. I wrote a simple Java class that implements the Binary GCD algorithm. It is a really tiny class that has only two easy-to-use methods. See for yourself:

GCD.java

package math;

/**
 * This is a utility class that provides the functionality of calculating the
 * GCD or Greatest Common Divisor (also known as HCF or Highest Common
 * Factor) of two or more integers.
 * <p>
 * It has only two methods:
 * <ol>
 * <li>{@link #of(long, long)}</li>
 * <li>{@link #of(long, long, long...)}</li>
 * </ol>
 * Usage is very simple:
 * <pre><code>
 * ...
 * // assuming a, b, c, d and e are integers (long, int, etc.)
 * long gcd1 = GCD.of(a, b);
 * long gcd2 = GCD.of(a, b, c);
 * long gcd3 = GCD.of(a, b, c, d);
 * long gcd4 = GCD.of(a, b, c, e);
 * ...
 * </code></pre>
 *
 * @author Subhomoy Haldar
 * @version 1.0
 */
public class GCD {

    /**
     * Private constructor to prevent instantiation.
     */
    private GCD() {
        throw new Error("Instantiation not allowed.");
    }

    /**
     * This method computes the GCD of two positive integers using the Binary
     * GCD algorithm.
     * <p>
     * This method does not complain if the integers provided are negative.
     * In such a case, it simply the absolute value and performs the
     * computation. If one of the arguments is zero, the other argument is
     * returned. If both are zero, then zero is returned.
     *
     * @param a The first positive integer.
     * @param b The second positive integer.
     * @return The GCD of two positive integers.
     */
    public static long of(long a, long b) {
        // corner cases
        if (a == 0) return b;
        if (b == 0) return a;
        if (a < 0) a = -a;
        if (b < 0) b = -b;
        // number of tailing zeroes = power of 2 present
        int a0 = Long.numberOfTrailingZeros(a);
        int b0 = Long.numberOfTrailingZeros(b);
        // extract the the number of trailing zeroes common to them
        int commonPower = a0 < b0 ? a0 : b0;
        // make them odd
        a >>>= a0;
        b >>>= b0;
        while (a != b) {
            if (a > b) {
                a -= b;
                a >>>= Long.numberOfTrailingZeros(a);
            } else {
                b -= a;
                b >>>= Long.numberOfTrailingZeros(b);
            }
        }
        return a << commonPower; // multiply back the common power of 2
    }

    /**
     * This method returns the GCD of all the integers provided.
     * <p>
     * This method makes use of the {@link #of(long, long) of(long, long)}
     * method.
     *
     * @param a      The first positive integer.
     * @param b      The second positive integer.
     * @param others The other positive integers.
     * @return The GCD of all the integers provided.
     * @see #of(long, long) Internally used by this method.
     */
    public static long of(long a, long b, long... others) {
        long gcd = of(a, b);
        for (long number : others) {
            gcd = of(gcd, number);
        }
        return gcd;
    }
}

I welcome comments on any aspect of the code. This class will be reused in future questions.

\$\endgroup\$
6
\$\begingroup\$

Instead of throwing an Error, an AssertionError would be better. An Error is too broad. An AssertionError conveys better that instantiating is an error by the programmer, violating a precondition. (The only way this error will be triggered is if you try to create an instance within this class.)

private GCD() {
    throw new AssertionError("Instantiation not allowed.");
}

As this class has only private constructors, it cannot be extended: derived classes would need to call a constructor in the super-class, but none are available. To make the intention perfectly clear that this class is not designed to be extended, it's good to make it final.

\$\endgroup\$
5
\$\begingroup\$
  1. Mark the class final to make it obvious there are no and never will be any derived classes.

  2. While your comments insist that the domain of gcd is non-negative integers, that doesn't conform to your code (which takes the absolute values), which gets it mostly right:

  3. You could simplify the second function by only asking for a single fixed argument (or even no fixed arguments, with a result of 0).

    What is \$gcd(0,a)\$, where a is a positive integer?
    What is \$gcd(0,0)\$?

    That probably doesn't improve performance though:

    public static long of(long a, long... others) {
        for (long number : others)
            a = of(a, number);
        return a;
    }
    

    Or:

    // The added iteration probably adds a really small penalty
    public static long of(long... others) {
        long a = 0;
        for(long number : others)
            a = of(a, number);
    }
    
\$\endgroup\$
  • \$\begingroup\$ Do you mean Long.MIN_VALUE? \$\endgroup\$ – Hungry Blue Dev Oct 16 '15 at 20:05
  • 1
    \$\begingroup\$ I said 2 or more arguments. Your code allows the user to provide only 1 argument. \$\endgroup\$ – Hungry Blue Dev Oct 16 '15 at 20:08
  • \$\begingroup\$ Linked to some SO question mentioning the problem. Yes, Long.MIN_VALUE is the one. Yes, my code does allow a single argument. But that simplifies the code, and where's the harm to that generalization? \$\endgroup\$ – Deduplicator Oct 16 '15 at 20:10
  • \$\begingroup\$ What is the Greatest Common Divisor of 42? \$\endgroup\$ – Hungry Blue Dev Oct 16 '15 at 20:11
  • \$\begingroup\$ Of 42 and nothing else? 42 naturally. \$\endgroup\$ – Deduplicator Oct 16 '15 at 20:12
4
\$\begingroup\$

I think there's a bug in your method. If I call GCD.of(0,0); You'd return b, which equals 0. But 0 isn't the GCD of 0. Zero can't ever be a greatest common divisor. Because, you can't divide by zero. You should consider throwing a DivideByZeroException, because once you're there there's nothing else you can do! Edit : Thanks to @Deduplicator's comment which pointed at a question on Math.SE You should return 0 if one of the parameter is 0!

To push on Deduplicator's idea, I think you should only receive one argument.

public static long of(long... numbers)
//See the rest of the review
  • Now, what if the user passes zero arguments? Throw an exception, the user decided, by him(her)self, to pass zero arguments to a GCD function, it's dumb and the user will have to deal with the consequences of his(her) acts.
  • What if the user passes only one argument. Well that's an easy job for you, you return the same number. The user decided to ask for the GCD of one number, give it to him.
  • The user passes more than 1 long, good, now the real work begins!
public static long of(long... numbers) {
    if(numbers.length == 0) {
        throw new InvalidArgumentException("Input is too small to compute GCD");
    }

    if(numbers.length == 1) {
        return numbers[0];
    }

    long gcd = numbers[0];
    //Note that the index starts at one because we use [0] for the first variable.
    for(int index = 1; index < numbers.length;index++){

        long number = numbers[index];
        if(number == 0) {
            return 0;
        }

        gcd = of(gcd, number);
    }

    return gcd;
}
\$\endgroup\$
3
\$\begingroup\$

This is only a mild improvement, and whether or not you call it an improvement is subjective.

Your second function:

public static long of(long a, long b, long... others) {
    long gcd = of(a, b);
    for (long number : others) {
        gcd = of(gcd, number);
    }
    return gcd;
}

Can be rewritten using Java 8's stream operators:

public static long of(long a, long... others) {
    return LongStream.concat(
               LongStream.of(a),
               LongStream.of(others)
           ).reduce(0, GCD::of);
}

And if you are fine with the user being able to call GCD.of(), you could do:

public static long of(long... values) {
    return LongStream.of(values)
                     .reduce(0, GCD::of);
}

This has the advantage of being easily parallelizable (which is actually only beneficial if you anticipate having a very large amount of values to find the gcd of):

public static long of(long... values) {
    return LongStream.of(values).parallel()
                     .reduce(0, GCD::of);
}
\$\endgroup\$
  • \$\begingroup\$ Ingenious! I was looking for a way to use Functional Programming. \$\endgroup\$ – Hungry Blue Dev Oct 17 '15 at 3:47
  • \$\begingroup\$ Didn't know about Java8 stream-operators yet. That makes the generalization look even better! \$\endgroup\$ – Deduplicator Oct 17 '15 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.