10
\$\begingroup\$

(See the next iteration.)

I have this class for representing exact fractions. See what I have:

Fraction.java:

package net.coderodde.math;

import java.util.ArrayList;
import java.util.List;

/**
 * This class implements a fraction consisting of a numerator and a denominator.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 29, 2016)
 */
public class Fraction extends Number {

    private final long numerator;
    private final long denominator;

    public Fraction(final long numerator, final long denominator) {
        if (denominator == 0) {
            throw new IllegalArgumentException("The denominator is zero.");

        }

        if (numerator == 0) {
            this.numerator = 0;
            this.denominator = 1;
        } else {
            final boolean isPositive = isPositive(numerator, denominator);
            final long[] data = eliminateCommonFactors(numerator, denominator);

            this.numerator   = isPositive ? data[0] : -data[0];
            this.denominator = data[1];
        }
    }

    public Fraction plus(final Fraction other) {
        return new Fraction(this.numerator * other.denominator + 
                            this.denominator * other.numerator,
                            this.denominator * other.denominator);
    }

    public Fraction minus(final Fraction other) {
        return new Fraction(this.numerator * other.denominator - 
                            this.denominator * other.numerator,
                            this.denominator * other.denominator);
    }

    public Fraction multiply(final Fraction other) {
        return new Fraction(this.numerator * other.numerator,
                            this.denominator * other.denominator);
    }

    public Fraction divide(final Fraction other) {
        return new Fraction(this.numerator * other.denominator,
                            this.denominator * other.numerator);
    }

    public Fraction abs() {
        return new Fraction(Math.abs(numerator), Math.abs(denominator));
    }

    public long getNumerator() {
        return numerator;
    }

    public long getDenominator() {
        return denominator;
    }

    public Fraction neg() {
        return new Fraction(-numerator, denominator);
    }

    @Override
    public String toString() {
        return "" + numerator + "/" + denominator;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }

        if (!getClass().equals(o.getClass())) {
            return false;
        }

        final Fraction other = (Fraction) o;
        return getNumerator() == other.getNumerator() 
                && getDenominator() == other.getDenominator();
    }

    @Override
    public int intValue() {
        return (int)(numerator / denominator);
    }

    @Override
    public long longValue() {
        return numerator / denominator;
    }

    @Override
    public float floatValue() {
        return ((float) numerator) / denominator;
    }

    @Override
    public double doubleValue() {
        return ((double) numerator) / denominator;
    }

    private boolean isPositive(final long numerator, final long denominator) {
        final boolean numeratorIsPositive   = numerator > 0L;
        final boolean denominatorIsPositive = denominator > 0L;

        return (numeratorIsPositive && denominatorIsPositive) ||
               (!numeratorIsPositive && !denominatorIsPositive);
    }

    private long[] eliminateCommonFactors(long numerator,
                                          long denominator) {
        numerator   = Math.abs(numerator);
        denominator = Math.abs(denominator);

        if (numerator < denominator) {
            final List<Long> numeratorPrimeFactorList = factorize(numerator);

            for (final long primeFactor : numeratorPrimeFactorList) {
                if (denominator % primeFactor == 0) {
                    denominator /= primeFactor;
                    numerator   /= primeFactor;
                }
            }
        } else {
            final List<Long> denominatorPrimeFactorList = 
                    factorize(denominator);

            for (final long primeFactor : denominatorPrimeFactorList) {
                if (numerator % primeFactor == 0) {
                    numerator   /= primeFactor;
                    denominator /= primeFactor;
                }
            }
        }

        return new long[]{ numerator, denominator };
    }

    private static List<Long> factorize(long value) {
        final List<Long> factorList = new ArrayList();

        while (value % 2L == 0) {
            factorList.add(2L);
            value /= 2L;
        }

        for (long prime = 3L; 
                prime <= (long) Math.sqrt(value);
                prime = nextPrime(prime)) {
            if (prime * prime > value) {
                break;
            }

            while (value % prime == 0L) {
                factorList.add(prime);
                value /= prime;
            }
        }

        if (value > 1) {
            factorList.add(value);
        }

        return factorList;
    }

    private static long nextPrime(final long prime) {
        long nextPrimeCandidate = prime + 2L;

        while (!isPrime(nextPrimeCandidate)) {
            nextPrimeCandidate += 2L;
        }

        return nextPrimeCandidate;
    }

    private static boolean isPrime(final long primeNumberCandidate) {
        final long upperBound = (long) Math.sqrt(primeNumberCandidate);

        for (long i = 3L; i < upperBound; i += 2) {
            if (primeNumberCandidate % i == 0L) {
                return false;
            }
        }

        return true;
    }
}

FractionTest.java:

package net.coderodde.math;

import org.junit.Test;
import static org.junit.Assert.*;

public class FractionTest {

    private static float DELTA = 0.001f;

    @Test 
    public void testConstruct() {
        assertEquals(new Fraction(5, 3) , new Fraction(35, 21));
        assertEquals(new Fraction(5, 3) , new Fraction(-35, -21));
        assertEquals(new Fraction(-5, 3), new Fraction(-35, 21));
        assertEquals(new Fraction(-5, 3), new Fraction(35, -21));
        assertEquals(new Fraction(0, 1) , new Fraction(0, 100));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testThrowsOnZeroDenominator() {
        new Fraction(1, 0);
    }

    @Test
    public void testPlus() {
        // (7 / 3) + (6 / 5) = (35 / 15) + (18 / 15) = 53 / 15
        Fraction a = new Fraction(7, 3);
        Fraction b = new Fraction(6, 5);

        assertEquals(new Fraction(53, 15), a.plus(b));
        assertEquals(new Fraction(53, 15), b.plus(a));

        a = new Fraction(-7, 3);
        b = new Fraction(6, -5);

        assertEquals(new Fraction(-53, 15), a.plus(b));

        a = new Fraction(7, 3);
        b = new Fraction(6, -5);

        // (7 / 3) - (6 / 5) = (35 / 15) - (18 / 15) = 17 / 15
        assertEquals(new Fraction(17, 15), a.plus(b));
    }

    @Test
    public void testMinus() {
        // (7 / 3) - (6 / 5) = (35 / 15) - (18 / 15) = 17 / 15
        Fraction a = new Fraction(7, 3);
        Fraction b = new Fraction(6, 5);

        assertEquals(new Fraction(17, 15), a.minus(b));
        assertEquals(new Fraction(17, -15), b.minus(a));
        assertEquals(new Fraction(-17, 15), b.minus(a));
    }

    @Test
    public void testMultiply() {
        Fraction a = new Fraction(3, 7);
        Fraction b = new Fraction(5, 3);

        assertEquals(new Fraction(5, 7), a.multiply(b));

        b = new Fraction(-5, 3);

        assertEquals(new Fraction(-5, 7), a.multiply(b));
        assertEquals(new Fraction(5, -7), a.multiply(b));
    }

    @Test
    public void testDivide() {
        // (2/9) / (6/4) = (2/9) * (2/3) = 4 / 27
        Fraction a = new Fraction(2, 9);
        Fraction b = new Fraction(6, 4);

        assertEquals(new Fraction(4, 27), a.divide(b));
        assertEquals(new Fraction(-4, -27), a.divide(b));
    }

    @Test
    public void testAbs() {
        assertEquals(new Fraction(2, 4), new Fraction( 1,  2).abs());
        assertEquals(new Fraction(2, 4), new Fraction(-1,  2).abs());
        assertEquals(new Fraction(2, 4), new Fraction( 1, -2).abs());
        assertEquals(new Fraction(2, 4), new Fraction(-1, -2).abs());
    }

    @Test
    public void testGetNumerator() {
        assertEquals(3,  new Fraction(6, 4)  .getNumerator());
        assertEquals(3,  new Fraction(3, 2)  .getNumerator());
        assertEquals(3,  new Fraction(9, 6)  .getNumerator());
        assertEquals(15, new Fraction(15, 11).getNumerator());
    }

    @Test
    public void testGetDenominator() {
        assertEquals(2,  new Fraction(6, 4)  .getDenominator());
        assertEquals(2,  new Fraction(3, 2)  .getDenominator());
        assertEquals(2,  new Fraction(9, 6)  .getDenominator());
        assertEquals(11, new Fraction(15, 11).getDenominator());
    }

    @Test
    public void testToString() {
        assertEquals("3/2"   , new Fraction(6  , 4)  .toString());
        assertEquals("3/2"   , new Fraction(3  , 2)  .toString());
        assertEquals("3/2"   , new Fraction(9  , 6)  .toString());
        assertEquals("15/11" , new Fraction(15 , 11) .toString());
        assertEquals("-15/11", new Fraction(-15, 11) .toString());
        assertEquals("-15/11", new Fraction(15 , -11).toString());
        assertEquals("15/11" , new Fraction(-15, -11).toString());
        assertEquals("0/1"   , new Fraction(0, -123) .toString());
    }

    @Test
    public void testIntValue() {
        assertEquals(0, new Fraction(0, 4).intValue());
        assertEquals(0, new Fraction(1, 4).intValue());
        assertEquals(0, new Fraction(2, 4).intValue());
        assertEquals(0, new Fraction(3, 4).intValue());

        assertEquals(1, new Fraction(4, 4).intValue());
        assertEquals(1, new Fraction(5, 4).intValue());
        assertEquals(1, new Fraction(6, 4).intValue());
        assertEquals(1, new Fraction(7, 4).intValue());

        assertEquals(0, new Fraction(-0, 4).intValue());
        assertEquals(0, new Fraction(-1, 4).intValue());
        assertEquals(0, new Fraction(-2, 4).intValue());
        assertEquals(0, new Fraction(-3, 4).intValue());

        assertEquals(-1, new Fraction(-4, 4).intValue());
        assertEquals(-1, new Fraction(-5, 4).intValue());
        assertEquals(-1, new Fraction(-6, 4).intValue());
        assertEquals(-1, new Fraction(-7, 4).intValue());

        assertEquals(4, new Fraction(-17, -4).intValue());
    }

    @Test
    public void testLongValue() {
        assertEquals(0L, new Fraction(0, 4).longValue());
        assertEquals(0L, new Fraction(1, 4).longValue());
        assertEquals(0L, new Fraction(2, 4).longValue());
        assertEquals(0L, new Fraction(3, 4).longValue());

        assertEquals(1L, new Fraction(4, 4).longValue());
        assertEquals(1L, new Fraction(5, 4).longValue());
        assertEquals(1L, new Fraction(6, 4).longValue());
        assertEquals(1L, new Fraction(7, 4).longValue());

        assertEquals(0L, new Fraction(-0, 4).longValue());
        assertEquals(0L, new Fraction(-1, 4).longValue());
        assertEquals(0L, new Fraction(-2, 4).longValue());
        assertEquals(0L, new Fraction(-3, 4).longValue());

        assertEquals(-1L, new Fraction(-4, 4).longValue());
        assertEquals(-1L, new Fraction(-5, 4).longValue());
        assertEquals(-1L, new Fraction(-6, 4).longValue());
        assertEquals(-1L, new Fraction(-7, 4).longValue());

        assertEquals(4L, new Fraction(-17, -4).longValue());
    }

    @Test
    public void testFloatValue() {
        assertEquals(0.0f , new Fraction(0, 4).floatValue(), DELTA);
        assertEquals(0.25f, new Fraction(1, 4).floatValue(), DELTA);
        assertEquals(0.5f , new Fraction(2, 4).floatValue(), DELTA);
        assertEquals(0.75f, new Fraction(3, 4).floatValue(), DELTA);

        assertEquals(1.0f , new Fraction(4, 4).floatValue(), DELTA);
        assertEquals(1.25f, new Fraction(5, 4).floatValue(), DELTA);
        assertEquals(1.5f , new Fraction(6, 4).floatValue(), DELTA);
        assertEquals(1.75f, new Fraction(7, 4).floatValue(), DELTA);

        assertEquals(0.0f  , new Fraction(-0, 4).floatValue(), DELTA);
        assertEquals(-0.25f, new Fraction(-1, 4).floatValue(), DELTA);
        assertEquals(-0.5f , new Fraction(-2, 4).floatValue(), DELTA);
        assertEquals(-0.75f, new Fraction(-3, 4).floatValue(), DELTA);

        assertEquals(-1.0f , new Fraction(-4, 4).floatValue(), DELTA);
        assertEquals(-1.25f, new Fraction(-5, 4).floatValue(), DELTA);
        assertEquals(-1.5f , new Fraction(-6, 4).floatValue(), DELTA);
        assertEquals(-1.75f, new Fraction(-7, 4).floatValue(), DELTA);

        assertEquals(4.25f, new Fraction(-17, -4).floatValue(), DELTA);
    }

    @Test
    public void testDoubleValue() {
        assertEquals(0.0 , new Fraction(0, 4).doubleValue(), DELTA);
        assertEquals(0.25, new Fraction(1, 4).doubleValue(), DELTA);
        assertEquals(0.5 , new Fraction(2, 4).doubleValue(), DELTA);
        assertEquals(0.75, new Fraction(3, 4).doubleValue(), DELTA);

        assertEquals(1.0 , new Fraction(4, 4).doubleValue(), DELTA);
        assertEquals(1.25, new Fraction(5, 4).doubleValue(), DELTA);
        assertEquals(1.5 , new Fraction(6, 4).doubleValue(), DELTA);
        assertEquals(1.75, new Fraction(7, 4).doubleValue(), DELTA);

        assertEquals(0.0  , new Fraction(-0, 4).doubleValue(), DELTA);
        assertEquals(-0.25, new Fraction(-1, 4).doubleValue(), DELTA);
        assertEquals(-0.5 , new Fraction(-2, 4).doubleValue(), DELTA);
        assertEquals(-0.75, new Fraction(-3, 4).doubleValue(), DELTA);

        assertEquals(-1.0 , new Fraction(-4, 4).doubleValue(), DELTA);
        assertEquals(-1.25, new Fraction(-5, 4).doubleValue(), DELTA);
        assertEquals(-1.5 , new Fraction(-6, 4).doubleValue(), DELTA);
        assertEquals(-1.75, new Fraction(-7, 4).doubleValue(), DELTA);

        assertEquals(4.25, new Fraction(-17, -4).doubleValue(), DELTA);
    }
}

Any critique is much appreciated.

\$\endgroup\$
  • 1
    \$\begingroup\$ Consider using big integers. Fractions tend to grow quickly, leading to integer overflows. \$\endgroup\$ – CodesInChaos Apr 29 '16 at 13:50
  • \$\begingroup\$ out of pure curiosity: why do you declare all of your parameters in public methods as final? I'm not saying it's bad (it certainly doesn't have to be), but I'm unsure why/what are you trying to convey with that... seems awfully like a code smell to me in this case. In C const parameters are actually useful - in Java you're only locking yourself from re-using them inside of the method (which almost nobody does anyway), while conveying virtually nothing about the const-ness of the passed argument itself (since, while the reference isfinal, the object it's still completely mutable). \$\endgroup\$ – vaxquis Apr 29 '16 at 17:43
  • \$\begingroup\$ tl;dr see programmers.stackexchange.com/questions/48413/… - that's why I strongly advocate for final classes (extremely useful and helpful) and against final arguments in methods (mostly useless and redundant). \$\endgroup\$ – vaxquis Apr 29 '16 at 17:46
  • \$\begingroup\$ Some people preach for final, others against it, so this is rather subjective argument. \$\endgroup\$ – coderodde Apr 29 '16 at 17:54
15
\$\begingroup\$

You can make a lot of simplifications.

Non zero numbers with the same sign

Currently, you have a method that tests whether two given non-zero long values have the same sign with the following:

private boolean isPositive(final long numerator, final long denominator) {
    final boolean numeratorIsPositive = numerator > 0L;
    final boolean denominatorIsPositive = denominator > 0L;

    return (numeratorIsPositive && denominatorIsPositive) || (!numeratorIsPositive && !denominatorIsPositive);
}

This can be written more concisely with:

private boolean isPositive(final long numerator, final long denominator) {
    return numerator > 0 == denominator > 0;
}
  • You don't need to have L suffix. It is guaranteed that the check will be done on long values due to binary numeric promotion . JLS section 15.20.1 Numerical Comparison Operators <, <=, >, and >=:

    Binary numeric promotion is performed on the operands (§5.6.2).

    and JLS section 5.6.2:

    Otherwise, if either operand is of type long, the other is converted to long.

    So, rest assured.

  • You can simply check whether the fact that both numbers are greater than 0 is the same: if they are both greater or lower than 0 then the result will be true. Note that both numbers can't be equal to 0 since that case was already handled.

As such, you may not even need that method and directly have:

final boolean isPositive = numerator > 0 == denominator > 0;

Simplifying a fraction

The biggest complication is your method to simplify a fraction. You currently have a complicated way with determining the prime factor when you can do it in a much simpler way. Just calculate the greatest common divisor of both the numerator and the denominator.

private static long gcm(long a, long b) {
    return b == 0 ? a : gcm(b, a % b);
}

Then your code in the constructor simply becomes:

final boolean isPositive = numerator > 0 == denominator > 0;
final long gcm = gcm(numerator, denominator);

this.numerator   = isPositive ? Math.abs(numerator / gcm) : -Math.abs(numerator / gcm);
this.denominator = Math.abs(denominator / gcm);

All of your tests still pass with this change.

toString()

Small nitpick, in the following:

@Override
public String toString() {
    return "" + numerator + "/" + denominator;
}

you don't need the empty string. Just have:

@Override
public String toString() {
    return numerator + "/" + denominator;
}

No serialVersionUID

You are extending from Number which is serializable; this makes your class serializable also. As such, you should defined a serial version UID for your class.

Final and immutable classes

Do you intend to override that class in the future? It doesn't look like a good idea to do it. I would make that class final to make it impossible, just like the built-in Integer or Long.

The fact that the class is immutable is a very good idea.

Static factories

Consider creating a pool of common fractions, like ONE or ZERO. Then you can create static factories to return Fraction instances instead of using the constructor directly.

Typically, this is done by introducing a method valueOf(...) that will return the instance of Fraction. You can take inspiration from Integer.valueOf or BigDecimal.valueOf. The constructor is then made private so that the caller needs to go through that method.

As an example you could create two public constants for zero and one:

public static final Fraction ZERO = new Fraction(0, 1);
public static final Fraction ONE = new Fraction(1, 1);

Then, you can reuse them in the static factory:

public static Fraction valueOf(final long numerator, final long denominator) {
    if (denominator == 0) {
        throw new IllegalArgumentException("The denominator is zero.");
    }
    if (numerator == 0) {
        return ZERO;
    } else if (numerator == denominator) {
        return ONE;
    }
    return new Fraction(numerator, denominator);
}

This avoids to instantiate new fractions and reuse existing ones.

\$\endgroup\$
  • \$\begingroup\$ I need more elaboration of the Static factories -point. \$\endgroup\$ – coderodde Apr 29 '16 at 12:55
  • \$\begingroup\$ @coderodde I edited with a link to Stack Overflow question and an example. I hope it is clear enough :). \$\endgroup\$ – Tunaki Apr 29 '16 at 13:07
  • \$\begingroup\$ Still not clear. I have a private constructor and create the Fractions in it. OK, I can do it. Another point, factory pattern in SO question reuses the objects: is that what you implied? \$\endgroup\$ – coderodde Apr 29 '16 at 13:12
  • \$\begingroup\$ @coderodde Yes, that's one of the advantage of the static factory: you can reuse existing objects without creating new ones. It makes sense here since your class is immutable. \$\endgroup\$ – Tunaki Apr 29 '16 at 13:13
3
\$\begingroup\$

Do you plan to extend this class? If not, I would mark it as final. Given its nature, inheritance can open a Pandora box.


In your constructor:

final long[] data = eliminateCommonFactors(numerator, denominator);

numerator and denominator are long. Did you test what happens for very large numbers? All your tests use trivially small values, certainly not the ones that would warrant the use of long. Lagging constructors are a big no-no.

I would aim for lazy evaluation here, or at least replace the constructor with a static method, with a name indicating it's triggering a process (create, evaluate, convert?). Constructors should be fast as lightning.


Indeed, did you test how it behaves for very large (or very small) values, nevermind the performance? What will happen if I multiply new Fraction(Long.MAX_VALUE, Long.MIN_VALUE) by another one? What is supposed to happen?


/**
 * This class implements a fraction consisting of a numerator and a denominator.

I would shorten this to:

/**
 * Fraction consisting of a numerator and a denominator

It's obvious that it's a class - which implements/represents this, that or the other... and it's obvious that the comment refers to this class, not some other one a mile away. This is just fluff. (I know there are APIs in Java that do the same thing - in my opinion it's not something worth mimicking).

 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 29, 2016)

And again this is subjective, but I see these as a (common) anti-pattern. It's code, not a painting or a poem ;) We've got version control systems for that.


return (numeratorIsPositive && denominatorIsPositive) ||
       (!numeratorIsPositive && !denominatorIsPositive);

This could be expressed much simpler:

return numeratorIsPositive == denominatorIsPositive;

Prefixing a string with an empty string makes no sense. (I know what trick you're employing, but "/" does that for you already).

@Override
public String toString() {
    return "" + numerator + "/" + denominator;
}

@Test 
public void testConstruct() {

Some test frameworks require all test methods to be prefixed with "test", but when it's not required (and the presence of @Test attributes clearly shows that it's not handled by reflection), there's no point in doing this. It restates the obvious, serving no other purpose than to add noise.

\$\endgroup\$
  • 1
    \$\begingroup\$ While I agree with most of your points, I strongly disagree with the lazy evaluation comment. It's far more important that this class be immutable, then worrying about a few micro seconds (if that) to reduce the fraction. That code is not expensive. Lazy evaluation adds extra complexity and mutable state that will inevitably cause problems in some concurrent usage. \$\endgroup\$ – wolfcastle Apr 29 '16 at 21:38
  • \$\begingroup\$ @wolfcastle this is a legitimate concern, but since numerator and denominator are immutable already, the worst thing that could happen due to botched thread safety is that the value would be evaluated twice. but it would always get evaluated to the same result anyway. it doesn't sound too dangerous to me. \$\endgroup\$ – Konrad Morawski Apr 30 '16 at 9:58
  • \$\begingroup\$ @wolfcastle maximum value for long is 9223372036854775807, hence my thoughts that factorizing a fraction such as 376746102469562110 / 9223372036854775807 could lag a bit. hard to say without a benchmark. treat it as food for thought \$\endgroup\$ – Konrad Morawski Apr 30 '16 at 10:00
3
\$\begingroup\$

You have overlooked one common, yet very important thing. You have overridden equals, but not hashCode. Your object will not work as expected when used as keys in maps.

Also, assuming you do make the class final, you can simplify the equals method a bit by using instanceof instead of comparing classes.

import java.util.Objects;
@Override
public boolean equals(Object o) {
    if( o instanceof Fraction ) {
        final Fraction other = (Fraction) o;
        return getNumerator() == other.getNumerator()
                && getDenominator() == other.getDenominator();            
    }
    return false;
}

@Override
public int hashCode() {
    return Objects.hash( numerator, denominator );
}
\$\endgroup\$
  • \$\begingroup\$ Yes, that's a very good point about the missing hashCode. And welcome to Code Review! \$\endgroup\$ – Tunaki Apr 29 '16 at 22:22
2
\$\begingroup\$

Simplify your sign management: Add code in the constructor to check the sign of the denominator, and if negative negate both numerator and denominator. Then the sign of the fraction is simply the sign of the numerator. Note that both addition and multiplication will preserve this feature.

\$\endgroup\$
1
\$\begingroup\$

Performance

As Tunaki points out you can simplify fractions by eliminating the Greatest Common Divisor.

This can be done with a simple recursive function:

public static int recursiveGCD( final int a, final int b ){
    return b == 0 ? Math.abs(a):recursiveGCD(b,a%b);
}

or with the gcd function in the BigInteger class:

public static int bigIntegerGCD( final int a, final int b ){
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
}

However, there is a Binary GCD function that is much more performant (although more complicated):

public class IntUtils {
  /**
   * Computes the greatest common divisor of the absolute value of two
   * numbers, using a modified version of the "binary GCD" method.
   * 
   * See:
   * <ul>
   *   <li>Knuth, D. (1998), "The Art of Computer Programming",
   *    (Section 4.5.2 Algorithm B)</li>
   *   <li>Stein, J. (1967),
   *    "Computational problems associated with Racah algebra",
   *    Journal of Computational Physics 1 (3): 397–405</li>
   * </ul>
   * 
   * @param a Number
   * @param b Number
   * @return The greatest common divisor (never negative).
   * @throws ArithmeticException
   *     When one input is Integer.MIN_VALUE and the other is either zero
   *     or Integer.MIN_VALUE (then the output would be greater than
   *     Integer.MAX_VALUE).
   */
  public static final int gcd( int a, int b ) throws ArithmeticException {
    if ( a == Integer.MIN_VALUE )
    {
      if ( b == Integer.MIN_VALUE || b == 0 )
        throw new ArithmeticException( "gcd() is greater than Integer.MAX_VALUE" );
      else
        return 1 << Integer.numberOfTrailingZeros( Math.abs(b) );
    }
    if ( b == Integer.MIN_VALUE ){
      if ( a == 0 )
        throw new ArithmeticException( "gcd() is greater than Integer.MAX_VALUE" );
      else
        return 1 << Integer.numberOfTrailingZeros( Math.abs(a) );
    }

    a = Math.abs(a);
    b = Math.abs(b);
    if ( a == 0 ) return b;
    if ( b == 0 ) return a;
    int za = Integer.numberOfTrailingZeros(a),
      zb = Integer.numberOfTrailingZeros(b),
      zc = Math.min(za,zb);
    a >>= za;
    b >>= zb;
    while(a != b){
      if ( a > b ) {
        a = (a - b);
        a >>= Integer.numberOfTrailingZeros( a );
      } else {
        b = (b - a);
        b >>= Integer.numberOfTrailingZeros( b );
      }
    }
    return a << zc;
  }
}

This is trivially easy to convert from handling ints to longs by just doing a find on int / integer replacing them with long (maintaining case).

Testing

The testing below is overkill but I was trying to find a fast algorithm for some Project Euler questions:

public static double mean( final long sum, final long repeats ){
  return ((double) sum)/repeats;
}
public static double variance( final long sum, final long squaredSum, final long repeats ){
  return (squaredSum + ((double) (sum*sum)) / repeats ) / ( repeats - 1 );
}
public static void main( final String[] args ){
  final int SIZE = 10000;
  final int[] x = new int[SIZE];
  final int[] y = new int[SIZE];
  final int[] a = new int[SIZE];
  final Random rand = new Random();
  int v;
  for ( int i = 0; i < SIZE; i++ ){
    x[i] = rand.nextInt();
    y[i] = rand.nextInt();
    a[i] = bigIntegerGCD(x[i], y[i]);
    if ( (v= recursiveGCD(x[i],y[i])) != a[i] )
      System.out.println( String.format( "recursiveGCD(%d,%d) = %d != %d", x[i],y[i], v,a[i]));
    if ( (v= IntUtils.gcd(x[i],y[i])) != a[i] )
      System.out.println( String.format( "Utils.GCD(%d,%d) = %d != %d", x[i],y[i], v,a[i]));
  }

  System.out.println( "Code warm-up" );
  for ( int r = 0; r < 1000; r++ ){
    for ( int i = 0; i< SIZE; i++ ){
      bigIntegerGCD(x[i],y[i]);
      recursiveGCD(x[i],y[i]);
      IntUtils.gcd(x[i], y[i]);
    }
  }

  final long REPEATS = 400000;
  long  rTime = 0,
      bTime = 0,
      uTime = 0,
      rTimeSq = 0,
      bTimeSq = 0,
      uTimeSq = 0,
      start,
      end;
  System.out.println( "Testing" );
  for ( int r = 0; r < REPEATS; r++ ){
    for ( int i = 0; i< SIZE; i++ ){
      start = System.nanoTime();
      bigIntegerGCD(x[i],y[i]);
      end = System.nanoTime();
      bTime += end - start;
      bTimeSq += (end-start)*(end-start);

      start = System.nanoTime();
      recursiveGCD(x[i],y[i]);
      end = System.nanoTime();
      rTime += end - start;
      rTimeSq += (end-start)*(end-start);

      start = System.nanoTime();
      IntUtils.gcd(x[i], y[i]);
      end = System.nanoTime();
      uTime += end - start;
      uTimeSq += (end-start)*(end-start);
    }
  }

  System.out.println( String.format( "%20s - Mean: %,9.3f, Var: %,15.3f", "BigInteger", mean( bTime, REPEATS*SIZE ), variance( bTime, bTimeSq, REPEATS*SIZE ) ) );
  System.out.println( String.format( "%20s - Mean: %,9.3f, Var: %,15.3f", "Utils",    mean( uTime, REPEATS*SIZE ), variance( uTime, uTimeSq, REPEATS*SIZE ) ) );
  System.out.println( String.format( "%20s - Mean: %,9.3f, Var: %,15.3f", "Recursive",  mean( rTime, REPEATS*SIZE ), variance( rTime, rTimeSq, REPEATS*SIZE ) ) );
}

Output:

Code warm-up
Testing
          BigInteger - Mean:   267.982, Var:  12,653,016.893
               Utils - Mean:   165.728, Var:     725,353.384
           Recursive - Mean:   194.008, Var:     659,516.007
BUILD SUCCESSFUL (total time: 48 minutes 7 seconds)

Demonstrates that the Binary GCD algorithm takes about 85% of the time of the recursive GCD algorithm (and using BigInteger is the slowest).

\$\endgroup\$

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.