4
\$\begingroup\$

(See the previous iteration.)

I have improved my Fraction implementation taking the answers in the previous iteration into account.

Differences

  1. Both numerator and denominator are now instances of BigInteger.
  2. The class also caches a BigDecimal representing the value of the ratio with no more than scale decimals.
  3. When constructing a Fraction, both the numerator and denominator are divided by their greatest common divisor. This is much shorter and efficient than in the previous iteration, where I dealt with prime factorization to do the same task.
  4. Fraction is declared final.
  5. toString() is simplified.
  6. The check whether the new Fraction is positive or negative is simplified.
  7. serialVersionUID is added.
  8. Added two public constants for zero and one.

However, I did not like the static factory pattern, so it's not here.

See what I have:

Fraction.java:

package net.coderodde.math;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.Objects;

/**
 * This class implements a fraction consisting of a numerator and a denominator.
 */
public final class Fraction extends Number {

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

    private static final int DEFAULT_SCALE = 5;
    private static final long serialVersionUID = 185726081998L;

    private final BigInteger numerator;
    private final BigInteger denominator;
    private final BigDecimal value;

    private Fraction(BigInteger numerator, 
                     BigInteger denominator,
                     final int scale) {
        Objects.requireNonNull(numerator, "The input numerator is null.");
        Objects.requireNonNull(denominator, "The input denominator is null.");

        if (denominator.equals(BigInteger.ZERO)) {
            throw new IllegalArgumentException("The denominator is zero.");
        }

        if (numerator.equals(BigInteger.ZERO)) {
            this.numerator   = BigInteger.ZERO;
            this.denominator = BigInteger.ONE;
            this.value       = BigDecimal.ZERO;
        } else {
            final boolean isPositive = 
                    numerator  .compareTo(BigInteger.ZERO) > 0 ==
                    denominator.compareTo(BigInteger.ZERO) > 0;

            numerator   = numerator.abs();
            denominator = denominator.abs();

            final BigInteger greatestCommonDivisor = gcd(numerator,
                                                         denominator);

            numerator   = numerator  .divide(greatestCommonDivisor);
            denominator = denominator.divide(greatestCommonDivisor);

            this.numerator   = isPositive ? numerator : numerator.negate();
            this.denominator = denominator;
            this.value =  new BigDecimal(this.numerator)
                  .divide(new BigDecimal(this.denominator), 
                          scale, 
                          RoundingMode.HALF_EVEN);
        }
    }

    public Fraction(final BigInteger numerator, final BigInteger denominator) {
        this(numerator, denominator, DEFAULT_SCALE);
    }

    public Fraction(final long numerator, 
                    final long denominator, 
                    final int scale) {
        this(BigInteger.valueOf(numerator), 
             BigInteger.valueOf(denominator),
             scale);
    }

    public Fraction(final long numerator, final long denominator) {
        this(numerator, denominator, DEFAULT_SCALE);
    }

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

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

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

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

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

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

    public BigInteger getNumerator() {
        return numerator;
    }

    public BigInteger getDenominator() {
        return denominator;
    }

    public BigDecimal getValue() {
        return value;
    }

    @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 numerator.equals(other.numerator) 
                && denominator.equals(other.denominator);
    }

    @Override
    public int hashCode() {
        return Objects.hash(numerator, denominator);
    }

    @Override
    public int intValue() {
        return value.intValue();
    }

    @Override
    public long longValue() {
        return value.longValue();
    }

    @Override
    public float floatValue() {
        return value.floatValue();
    }

    @Override
    public double doubleValue() {
        return value.doubleValue();
    }

    private BigInteger gcd(final BigInteger a, final BigInteger b) {
        return b.equals(BigInteger.ZERO) ? a : gcd(b, a.mod(b));
    }

    public static void main(String[] args) {
        System.out.println(new Fraction(1, 6, 4).getValue());
    }
}

FractionTest.java:

package net.coderodde.math;

import java.math.BigInteger;
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(BigInteger.valueOf(3),  new Fraction(6, 4)  .getNumerator());
        assertEquals(BigInteger.valueOf(3),  new Fraction(3, 2)  .getNumerator());
        assertEquals(BigInteger.valueOf(3),  new Fraction(9, 6)  .getNumerator());
        assertEquals(BigInteger.valueOf(15), new Fraction(15, 11).getNumerator());
    }

    @Test
    public void testGetDenominator() {
        assertEquals(BigInteger.valueOf(2),  new Fraction(6, 4)  .getDenominator());
        assertEquals(BigInteger.valueOf(2),  new Fraction(3, 2)  .getDenominator());
        assertEquals(BigInteger.valueOf(2),  new Fraction(9, 6)  .getDenominator());
        assertEquals(BigInteger.valueOf(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 much appreciated.

\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

Introducing a BigInteger is not a good idea. It does solve the problem of potential overflows during calculations but it comes with a big cost. BigInteger over primitives slows down performance a lot and it complicates the code. I would have had two classes:

  • a Fraction with long numerator and denominator.
  • a BigFraction with BigInteger numerator and denominator.

To test this, I made a JMH benchmark comparing the performance of a Fraction and a BigFraction. Fraction is based on your initial class, i.e. keeping long values as numerator and denominator, and it implements a couple of simplifications (like the greatest common divisor). BigFraction is the class in this post (where I just renamed it). The benchmark creates 10, 100, 1.000 and 10.000 fractions of both classes, with the same numerator and denominator chosen at random, and measures the time it takes to sum them all together.

The results speak for themselves (JDK 1.8.0_74, Windows 10 64 bits, i5, CPU @ 2.90 Ghz):

Benchmark               (length)  Mode  Cnt   Score    Error  Units
StreamTest.bigFraction        10  avgt   30   0,059 ±  0,003  ms/op
StreamTest.bigFraction       100  avgt   30   0,623 ±  0,025  ms/op
StreamTest.bigFraction      1000  avgt   30   6,583 ±  0,340  ms/op
StreamTest.bigFraction     10000  avgt   30  64,364 ±  2,081  ms/op
StreamTest.fraction           10  avgt   30   0,005 ±  0,001  ms/op
StreamTest.fraction          100  avgt   30   0,049 ±  0,001  ms/op
StreamTest.fraction         1000  avgt   30   0,506 ±  0,008  ms/op
StreamTest.fraction        10000  avgt   30   5,025 ±  0,069  ms/op

Using BigFraction is more than 12 times slower than using Fraction, for exactly the same numbers.

For completeness, this is the JMH benchmark:

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class StreamTest {

    @State(Scope.Benchmark)
    public static class FractionContainer {

        @Param({ "10", "100", "1000" })
        private int length;

        private List<BigFraction> bigFractions;
        private List<Fraction> fractions;

        @Setup(Level.Iteration)
        public void setUp() {
            ThreadLocalRandom random = ThreadLocalRandom.current();
            long numerator = random.nextLong(), denominator = random.nextLong();
            fractions = IntStream.range(0, length).mapToObj(i -> new Fraction(numerator, denominator)).collect(Collectors.toList());
            bigFractions = IntStream.range(0, length).mapToObj(i -> new BigFraction(numerator, denominator)).collect(Collectors.toList());
        }

    }

    @Benchmark
    public Fraction fraction(FractionContainer container) {
        return container.fractions.stream().reduce(new Fraction(0, 1), Fraction::plus);
    }

    @Benchmark
    public BigFraction bigFraction(FractionContainer container) {
        return container.bigFractions.stream().reduce(new BigFraction(0, 1), BigFraction::plus);
    }

}
\$\endgroup\$
0
\$\begingroup\$

The class also caches a BigDecimal representing the value of the ratio with no more than scale decimals.

It doesn't cache the scale, it computes it even when not needed. Moreover, it doubles the number of your constructors.

What worse: Do you agree that a.equals(b) should imply that (a.xxx()).equals(b.xxx()) for any method xxx? For your class it doesn't hold, try a = new Fraction(1, 3) and b = new Fraction(1, 3, 0). They have doubleValue of 0.33333 and 0.0, respectively.

For BigDecimal, rounding is essential and expected, for fractions it's damn surprising, especially as I can create them without specifying the scale (and there's no "decimal" in the class name).

IMHO, doubleValue should return 1.0/3.0 (i.e., the double closest to the exact value).

I'd use static factory methods instead of constructors. While constructors can be chained, sometimes it's not flexible enough. Sometimes the work done in the "end constructor" is not needed for a special case. For example, when constructing a fraction from two longs, you need no BigInteger gcd.

I'm missing compareTo.

I wouldn't declare arguments as final. The caller of the method doesn't care, so it's just clutter.

 private static final long serialVersionUID = 185726081998L;

Unless you want to be compatible with previous versions, you can set it to 1.

That all said, the code is nice. Concerning the BigDecimal functionality: If this behavior is what you want, then keep (and document) it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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