3
\$\begingroup\$

For Project Euler I've implemented a BigRational. The functionality is rather limited, just things I needed or will probably need soon. The style departs a bit from the standard.

I found out that using the fancy names "numerator" and "denominator" made the code very hard to read with tons of long and broken lines full with "...ator", so I resolved to p and q in the hope that everyone can remember the only two fields.

I intentionally left out Javadoc for everything obvious (e.g., compareTo says only "Returns +1, 0, or -1 according to the specification." as these exact values are not prescribed). Also things which may change soon (e.g. toString) are left undocumented. I may have forgotten something.

The naming intentionally differs from BigInteger as "plus" and "times" are much better names for immutables. Names like "add" are to be used for methods changing the instance (cf. Collection, *Builder). There may be a MutableBigRational one day...

import static com.google.common.base.Preconditions.checkNotNull;

import java.math.BigInteger;

import lombok.AccessLevel;
import lombok.EqualsAndHashCode;
import lombok.Getter;
import lombok.NonNull;
import lombok.RequiredArgsConstructor;

import com.google.common.math.LongMath;

/**
 * This class exactly represents an arbitrary big fraction {@code p/q}.
 *
 * <p>It uses a normalized {@link BigInteger} representation assuring that {@code gdc(p, q) == 1} and {@code q > 0}.
 */
@RequiredArgsConstructor(access=AccessLevel.PRIVATE) @EqualsAndHashCode
public final class BigRational implements Comparable<BigRational> {
    public static BigRational fraction(BigInteger p, BigInteger q) {
        {
            final int signumQ = q.signum();
            checkDivisionByZero(signumQ);
            final int signumP = p.signum();
            if (signumP == 0) return ZERO;
            if (signumQ < 0) {
                p = p.negate();
                q = q.negate();
            }
        }
        {
            final BigInteger gcd = p.gcd(q);
            if (!gcd.equals(BigInteger.ONE)) {
                p = p.divide(gcd);
                q = q.divide(gcd);
            }
        }
        return new BigRational(p, q);
    }

    public static BigRational fraction(BigInteger p, long q) {
        return fraction(p, BigInteger.valueOf(q));
    }

    public static BigRational fraction(long p, BigInteger q) {
        return fraction(BigInteger.valueOf(p), q);
    }

    // Optimized version avoiding BigInteger operations.
    public static BigRational fraction(long p, long q) {
        if (q <= 0) {
            checkDivisionByZero(q);
            p = -p;
            q = -q;
        }
        final long gcd = LongMath.gcd(Math.abs(p), q);
        if (gcd != 1) {
            p /= gcd;
            q /= gcd;
        }
        return new BigRational(BigInteger.valueOf(p), BigInteger.valueOf(q));
    }

    public static BigRational valueOf(BigInteger a) {
        return new BigRational(a, BigInteger.ONE);
    }

    public static BigRational valueOf(long a) {
        return new BigRational(BigInteger.valueOf(a), BigInteger.ONE);
    }

    /**
     * Create an instance from a string. Accepted formats are<ul>
     * <li>an decimal representation of an integer number (example: {@code 123})
     * <li>two such strings separated by a slash (example: {@code 3/4))
     * <li>two such strings separated by a dot (example: {@code 3.142})
     * </ul>optionally preceded by an optional minus sign (example: {@code -3.14})
     *
     * <p>Spaces and leading plus sign are forbidden, exponential floating point notation is not supported.
     */
    // Border cases like "-1/-2", "1.", "-.3" are left undocumented as this may change.
    public static BigRational valueOf(String s) {
        final int dotIndex = s.indexOf(".");
        if (dotIndex != -1) {
            final BigInteger p = new BigInteger(s.substring(0, dotIndex) + s.substring(dotIndex+1));
            final BigInteger q = BigInteger.TEN.pow(s.length() - dotIndex - 1);
            return fraction(p, q);
        }
        final int slashIndex = s.indexOf("/");
        if (slashIndex == -1) return valueOf(new BigInteger(s));
        return fraction(new BigInteger(s.substring(0, slashIndex)), new BigInteger(s.substring(slashIndex+1)));
    }

    @Override public String toString() {
        return p + "/" + q;
    }

    /** Returns +1, 0, or -1 according to the specification. */
    @Override public int compareTo(BigRational a) {
        if (this == a) return 0; // improbable but very fast
        checkNotNull(a);

        // All obtained signum and compareTo values are guaranteed to be +1, 0, or -1.

        if (signum() == 0) return -a.signum();
        if (signum() != a.signum()) return signum();

        final int comparePP = p.compareTo(a.p);
        final int compareQQ = q.compareTo(a.q);

        // Equal numerators or denominators.
        if (compareQQ == 0) return comparePP;
        if (comparePP == 0) return -signum() * compareQQ;

        // Bigger numerator and smaller denominator or vice versa.
        // This expression is hacky, but exhaustively tested.
        if ((signum() < 0) ^ (comparePP != compareQQ)) return comparePP;

        return compareToSlowPath(a);
    }

    private int compareToSlowPath(BigRational a) {
        // Estimate the size of pq and qp (see below).
        final int pqEstimatedLength = p.bitLength() + a.q.bitLength();
        final int qpEstimatedLength = q.bitLength() + a.p.bitLength();

        // As the estimation is imprecise, require one bit more.
        if (pqEstimatedLength > qpEstimatedLength + 1) return signum();
        if (pqEstimatedLength < qpEstimatedLength - 1) return -signum();

        final BigInteger pq = p.multiply(a.q);
        final BigInteger qp = q.multiply(a.p);
        return pq.compareTo(qp);
    }

    public BigRational plus(BigRational a) {
        if (q.equals(a.q)) return fraction(p.add(a.p), q); // improbable but very fast
        return fraction(p.multiply(a.q).add(q.multiply(a.p)), q.multiply(a.q));
    }

    public BigRational times(BigRational a) {
        if (this == a) return square(); // improbable but very fast
        return fraction(p.multiply(a.p), q.multiply(a.q));
    }

    public BigRational square() {
        return new BigRational(p.multiply(p), q.multiply(q)); // No normalization needed.
    }

    public BigRational parallel(BigRational a) {
        return reciprocal().plus(a.reciprocal()).reciprocal();
    }

    public BigRational negative() {
        return new BigRational(p.negate(), q);
    }

    public BigRational reciprocal() {
        checkDivisionByZero(q.signum());
        return new BigRational(q, p);
    }

    /** Returns +1, 0, or -1 according to the sign. */
    public int signum() {
        return p.signum();
    }

    private static void checkDivisionByZero(long a) {
        if (a == 0) throw new ArithmeticException("division by 0");
    }

    public static final BigRational ZERO = new BigRational(BigInteger.ZERO, BigInteger.ONE);
    public static final BigRational ONE = new BigRational(BigInteger.ONE, BigInteger.ONE);

    // Field names are intentionally kept short to make expression more readable.
    /** The numerator. */
    @Getter @NonNull private final BigInteger p;
    /** The denominator. */
    @Getter @NonNull private final BigInteger q;
}

There are only tests for the more complicated methods. I personally find the usual wisdom "one test per method" rather stupid (especially for numerical tests) as it leads to tons of methods which altogether cover only a small part of possible problem (even when full line coverage is given!) and take ages. They may also quickly become insufficient when the implementation changes (and then an error goes undetected). Still, I tried to keep tests simple and cover mostly one method per test (though I don't mind to do a trivial side test). That said, improvements are welcome.

import static maaartin.euler.BigRational.ONE;
import static maaartin.euler.BigRational.ZERO;
import static maaartin.euler.BigRational.fraction;
import static maaartin.euler.BigRational.valueOf;

import java.math.BigInteger;
import java.util.List;

import com.google.common.collect.ImmutableList;

import junit.framework.TestCase;

public class BigRationalTest extends TestCase {
    public void testValueOf() {
        assertEquals(ONE, valueOf("2/2"));
        assertEquals(ONE, valueOf("-3/-3")); // This may go away.
        assertEquals(ZERO, valueOf(0));
        assertEquals(ZERO, valueOf("0/4"));
        assertEquals(valueOf("1/2"), valueOf("0.5"));
        assertEquals(valueOf("1/2"), valueOf(".5"));
        assertEquals(valueOf("3"), valueOf("3."));
        assertEquals(valueOf("-4/10"), valueOf("-.4"));
        assertEquals(valueOf("-5"), valueOf("-5."));
    }

    public void testFraction() {
        for (int p=1; p<=3; ++p) {
            assertEquals(ZERO, fraction(0, p));
            assertEquals(ZERO, fraction(0, -p));
            for (int q=1; q<=3; ++q) {
                final BigRational expected = fraction(BigInteger.valueOf(p), BigInteger.valueOf(q));
                assertEquals(expected, fraction(p, q));
                assertEquals(expected, fraction(BigInteger.valueOf(-p), -q));
                assertEquals(expected, fraction(-p, -q));
                assertEquals(expected, fraction(2*p, BigInteger.valueOf(2*q)));
                assertEquals(expected, fraction(2*p, 2*q));
            }
        }
    }

    public void testToString() {
        final List<BigRational> list = ordereredList();
        for (final BigRational r : list) assertEquals(r, valueOf(r.toString()));
    }

    public void testCompareTo() {
        final List<BigRational> list = ordereredList();

        for (int i=0; i<list.size(); ++i) {
            final BigRational a = clone(list.get(i)); // Avoid the fast path by cloning.
            for (int j=0; j<list.size(); ++j) {
                final BigRational b = list.get(j);
                assertEquals(Integer.compare(i, j), a.compareTo(b));
            }
        }
    }

    public void testSquare() {
        final List<BigRational> list = ordereredList();
        for (int i=0; i<list.size(); ++i) {
            final BigRational a = list.get(i);
            final BigRational expected = a.times(clone(a)); // Avoid the fast path by cloning.
            assertEquals(expected, a.square());
            assertEquals(a.equals(ZERO) ? 0 : 1, expected.signum());
        }
    }

    private BigRational clone(BigRational a) {
        final BigRational result = fraction(a.p(), a.q());
        assertEquals(a, result); // a trivial test for fraction
        return result;
    }

    private ImmutableList<BigRational> ordereredList() {
        // Mix notations in order to exercise various factory methods.
        final ImmutableList<BigRational> positiveList = ImmutableList.of(
                valueOf("1/1000"), valueOf(100).reciprocal(), valueOf("0.1"),
                valueOf("1/4"), valueOf("1/3"), valueOf("10/20"), valueOf("2/3"), valueOf("0.75"),
                ONE, valueOf("4/3"), valueOf("6/4"), valueOf("5/3"),
                valueOf(2), fraction(2001, 1000), valueOf("5/2"), fraction(3, 1), valueOf(4),
                valueOf("4.9"), valueOf(5), valueOf("51/10"), valueOf("5.5"), valueOf("50/9"), valueOf("56/10"),
                valueOf(10), valueOf(100), valueOf(1000));
        final ImmutableList.Builder<BigRational> result = ImmutableList.builder();
        for (final BigRational r : positiveList.reverse()) result.add(r.negative());
        result.add(ZERO);
        result.addAll(positiveList);
        return result.build();
    }
}

Especially welcome are simplifications, optimizations and pointing to mistakes.

\$\endgroup\$
3
\$\begingroup\$

fraction

    if (q <= 0) {
        checkDivisionByZero(q);
        p = -p;
        q = -q;
    }

This seems unnecessarily complex. First, you check if the denominator is non-positive (negative or zero). Then you check if it is zero, throwing an exception if it is. If it isn't, you return and do the things for the case that it is negative. The problem that I have with this is that it is not evident that you won't do the negative case if the number is zero. One has to determine that checkDivisionByZero throws an exception on zero and aborts the fraction(long, long) function in order to make sense of this.

    if (q < 0) {
        p = -p;
        q = -q;
    } else {
        checkDivisionByZero(q);
    }

This logic seems more straightforward. Check if q is negative and handle that. Else check if q is 0 and presumably handle that.

This may make the q is positive case run slightly slower (assuming the compiler doesn't do something clever like run both paths simultaneously), but it speeds up the q is negative case. Since the q is negative case does two assignments, it is already slower. This version balances things. But my main reason remains that I find that this way reads more naturally.

valueOf

In the valueOf(String) comments, "an decimal" should be "a decimal".

    // As the estimation is imprecise, require one bit more.
    if (pqEstimatedLength > qpEstimatedLength + 1) return signum();
    if (pqEstimatedLength < qpEstimatedLength - 1) return -signum();

I might have written this

    // As the estimation is imprecise, require one bit more.
    if (pqEstimatedLength > qpEstimatedLength + 1) return signum();
    if (qpEstimatedLength > pqEstimatedLength + 1) return -signum();

As this makes the last line match the comment.

times

    if (this == a) return square(); // improbable but very fast

The this == a check is very fast, but the square() is less so. It may be accurate to say that square is faster than the more general case, but it's not a huge improvement. It basically saves the greatest common denominator check. You could have said "improbable but very fast to check" which wouldn't have implied anything about square().

You also might want to consider profiling this. How improbable is it? How much slower is the normal case when they are not the same object? It might be better to accept the slower method in the rare case in exchange for even a tiny improvement in the common case.

reciprocal

public BigRational reciprocal() {
    checkDivisionByZero(q.signum());
    return new BigRational(q, p);
}

It's interesting that you check for division by zero of q here. Zero is not a valid value for q, so that should never happen. However, if it did, you'd just end up with a valid number as the reciprocal. Did you perhaps mean to check if p is 0? That would be a problem.

signum

Technically speaking, you are taking a shortcut with signum. The correct implementation would do something like return p.signum() * q.signum(). You are relying on never having a negative q so that you can check just p. This will generally work and may make your code a tiny bit faster. It does increase the possibility of error though and should get unit test coverage.

Tests

You should probably write a test for BigRational.ZERO.reciprocal() to verify that it throws an exception. While you're there, you may want to write other reciprocal tests.

Along with reciprocal, you should test valueOf("1/0") and all the fraction methods to verify that they too throw exceptions when q is 0. Note: it may seem like you only have to check two methods since the other two just call the first one. However, that's an implementation detail that may change in the future. It's much easier to write two extra tests now than to rely on someone writing those two tests when they create the need for them.

You should consider beginning with a few tests that verify value by using the getters on p and q rather than matching valueOf arguments. Under the current methodology it would be possible to write code such that the bug was on both sides and cancelled out. Or to have two different bugs cancel. Try to have at least a few tests at the beginning that check that simple creation works as expected.

assertEquals(BigInteger.ONE, valueOf("1/3").p());
assertEquals(BigInteger(-2), valueOf("-.4").p());
assertEquals(BigInteger(3), valueOf("1/3").q());


assertEquals(BigInteger.ONE, fraction(1, 3).p());
assertEquals(BigInteger(-2), fraction(2, -1).p());
assertEquals(BigInteger(3), fraction(1, 3).q());

It's easy to view a unit test as a way to test that your code works. But in my opinion the real value of a unit test is its ability to make code continue to work the same way over time. Some people read the unit tests in order to understand what your code does. They view them as compilable comments. Where comments can become disconnected from their associated code without notice, unit tests can't. If a unit test's assertion no longer holds, you'll get an error.

Go through your code and look for different paths. For example, there should be a unit test that checks that when you call fraction(BigInteger p, BigInteger q) and q is negative, that q becomes positive and p is negated. Why? Because you have code that handles that case. You should check with both positive and negative values for p (you currently only check a positive p).

    // Bigger numerator and smaller denominator or vice versa.
    // This expression is hacky, but exhaustively tested.
    if ((signum() < 0) ^ (comparePP != compareQQ)) return comparePP;

You say that this was exhaustively tested. Which unit tests test it? If I change that code to

    if ((signum() >= 0) ^ (comparePP == compareQQ)) return comparePP;

Does it still work? If you had saved the tests that you did, then you could at least verify that it still covered all the cases that you tested. We could also look at the coverage for this and suggest other potential tests that you may have missed.

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

My comments on the fantastic review by Brythan need quite some place, so I'm writing them here. I've been improving the class in the meantime and continued during writing this.

fraction

if (q <= 0) {
    checkDivisionByZero(q);

I moved it out of the condition. You're right that it's confusing and IMHO it's a very premature optimization: A predicted branch is very cheap and BigInteger operation are very expensive, so let's do it the simple way.

valueOf

Done.

times

It may be accurate to say that square is faster than the more general case, but it's not a huge improvement. It basically saves the greatest common denominator check.

I guess that gdc can be very slow, way slower than the multiplication as it may include multiple divisions. But I haven't measure it, so for now I just fixed the comment.

You also might want to consider profiling this. How improbable is it?

That's the problem... it all depends on the application. If I were to multiply 2x2 BigRational matrices, then may occur all the time or never, depending on how they were obtained.

How much slower is the normal case when they are not the same object?

I'd bet the the branch overhead is close to nothing and I guess that the gcd double the time. But that's just a guess.

It might be better to accept the slower method in the rare case in exchange for even a tiny improvement in the common case.

Yes, but here the speed ratio between the check and the improvement is surely huge.

reciprocal

It's interesting that you check for division by zero of q here.

This was a bug you've found.

signum

Technically speaking, you are taking a shortcut with signum.

I wanted to guarantee that it works, but failed to do so. Now it's really guaranteed by the now manually written constructor.

This will generally work and may make your code a tiny bit faster. It does increase the possibility of error though and should get unit test coverage.

There are much more things relying on q being positive, including @EqualsAndHashCode (as it needs a normalized representation). So it's better to really rely on it everywhere, so that a possible error would manifest much often. Now the constructor takes care of it.

Tests

You should probably write a test for BigRational.ZERO.reciprocal() to verify that it throws an exception. While you're there, you may want to write other reciprocal tests.

Done.

Along with reciprocal, you should test valueOf("1/0") and all the fraction methods to verify that they too throw exceptions when q is 0.

Done.

Note: it may seem like you only have to check two methods since the other two just call the first one. However, that's an implementation detail that may change in the future. It's much easier to write two extra tests now than to rely on someone writing those two tests when they create the need for them.

Agreed.

You should consider beginning with a few tests that verify value by using the getters on p and q rather than matching valueOf arguments.

Agreed and done.

the real value of a unit test is its ability to make code continue to work the same way over time. Some people read the unit tests in order to understand what your code does. They view them as compilable comments.

And so do I (the problem is that I'm lazy).

// This expression is hacky, but exhaustively tested.
if ((signum() < 0) ^ (comparePP != compareQQ)) return comparePP;

You say that this was exhaustively tested. Which unit tests test it?

The one I used to find out the condition, namely testCompareTo. By comparing those many test fractions, it assures that it works for all cases I could think of. Especially, I assured that all of signum, comparePP and compareQQ can be both positive and negative at this place (zeros get handled above). All it takes is a set like

1/1, 2/3, 3/2, and their negatives

which is included. But I might have erred, that's why I included maybe 20 positive fractions (and zero and the same amount of negative fractions). This means some \$41^2\$ tests.

If I change that code to... Does it still work?

Sure. Even > would do. And if you change the returned value to e.g., compareQQ, the test will tell you.

If you had saved the tests that you did

But I have! I really can't tell which combination covers what exact case, but I'm claiming they're all there.

Instead of writing specialized tests to cover all paths, I added examples to my set of fractions. Figuring out what two fractions cover a given code path could take me minutes and there are tons of paths. Proving that I haven't forgotten any is easier.

Ideally, I should have added such a comment to my example fractions stating what gets tested by which pair. But this is hard as each fraction gets used multiple times and they have to be listed in order (and I can't simply call sort since it needs the method under test). Doing a classical one-test-per-method style would mean maybe tens of tests for the single method and I'd be never sure I have them all.

then you could at least verify that it still covered all the cases that you tested. We could also look at the coverage for this and suggest other potential tests that you may have missed.

Concerning compareTo, I'd bet that nothing is missing. Concerning other methods, there's surely a lot to do.

\$\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.