3
\$\begingroup\$

Enough with imprecise floating point datatypes called float anddouble. I present to you Rational. Of course, Rational number arithmetic is easy, so I took up a much more interesting challenge: Rational Number Approximation. This is what I have implemented in my code. I have employed a technique similar to binary search, the only difference being that I am the mediant in place of the middle element.

Rational.java

/**
 * This class encapsulates a <em>Rational</em> number. Any rational number
 * {@code R} can be represented as a quotient of two whole numbers,
 * {@code p}, and {@code q}. Provided a decimal number,
 * this class can approximate the numerator and denominator to precision of
 * 1E-11 (the default). It is also a handy implementation for approximating
 * irrational values like that of {@link java.lang.Math#PI Math.PI},
 * or {@link java.lang.Math#E Math.E}, or the golden ratio: &phi;.
 *
 * @author Subhomoy Haldar (ambigram_maker)
 * @version 1.1
 */
public class Rational {

    /**
     * A public constant that defines the rational value of 0.
     */
    public static final Rational ZERO = new Rational(0, 1);
    /**
     * A public constant that defines the rational value of 1.
     */
    public static final Rational ONE = new Rational(1, 1);
    /**
     * A public constant that defines the rational value of 0.5.
     */
    public static final Rational HALF = new Rational(1, 2);

    /*
     * The Lowest and the Highest levels of precision allowed.
     */
    private static final double LWST_PREC = 1E-3;
    private static final double HIST_PREC = 1E-16;

    private static double precision = 1E-10;

    private final long num;
    private final long den;
    private final double result;

    /**
     * Creates a new {@code Rational} with the given numerator and
     * denominator. It has special cases for Positive Infinity
     * ({@link java.lang.Double#POSITIVE_INFINITY Double.POSITIVE_INFINITY}),
     * Negative Infinity ({@link java.lang.Double#NEGATIVE_INFINITY
     * Double.NEGATIVE_INFINITY}) and Not A Number
     * ({@link java.lang.Double#NaN Double.NaN}.
     *
     * @param numerator   The numerator.
     * @param denominator The denominator.
     */
    public Rational(long numerator, long denominator) {
        // for dealing with "infinities" and "NaN":
        if (denominator == 0) {
            den = 0;
            if (numerator > 0) {
                num = 1;
                result = Double.POSITIVE_INFINITY;
            } else if (numerator < 0) {
                num = -1;
                result = Double.NEGATIVE_INFINITY;
            } else {
                num = 0;
                result = Double.NaN;
            }
            return;
        }
        if (denominator < 0) {
            numerator = 0L - numerator;
            denominator = 0L - denominator;
        }
        num = numerator;
        den = denominator;
        result = (double) numerator / denominator;
    }

    /**
     * Creates a new {@code Rational} object that approximates the value of
     * the decimal to the set level of {@link #getPrecision() precision}. It
     * is also capable of approximating irrational values like
     * {@link java.lang.Math#PI Math.PI}, {@link java.lang.Math#E Math.E} or
     * the golden ratio, &phi;.
     *
     * @param decimal The value to approximate.
     */
    public Rational(double decimal) {
        // Exit clauses:
        if (decimal == Double.NaN) {
            num = 0;
            den = 0;
            result = Double.NaN;
            return;
        }
        if (decimal == Double.POSITIVE_INFINITY) {
            num = 1;
            den = 0;
            result = Double.POSITIVE_INFINITY;
            return;
        }
        if (decimal == Double.NEGATIVE_INFINITY) {
            num = -1;
            den = 0;
            result = Double.NEGATIVE_INFINITY;
            return;
        }

        long nu, de;
        long whole = 0;     // fail-safe value

        boolean negative = decimal < 0;

        decimal = Math.abs(decimal);

        boolean hasWhole = decimal >= 1;
        if (hasWhole) {     // keep fractional part.
            whole = (long) decimal;
            decimal -= whole;
        }

        if (decimal == 0) { // no fractional part present or 0 input
            num = negative ? 0L - whole : whole;
            den = 1;
            result = negative ? 0D - whole : whole;
            return;
        }
        // initially, the extreme points are 0 and 1.
        // decimal always lies in the interval: (n1/d1, n2/d2)
        long n1 = 0, d1 = 1;
        long n2 = 1, d2 = 1;

        double epsilon;     // the error amount in the approximation.
        while (true) {
            long n = n1 + n2, d = d1 + d2;
            double result = (double) n / d;
            epsilon = Math.abs(result - decimal);
            if (epsilon <= precision) {     // goal reached
                nu = n;
                de = d;
                break;
            } else if (result < decimal) {  // increase lower bound
                n1 = n;
                d1 = d;
            } else {                        // increase upper bound
                n2 = n;
                d2 = d;
            }
        }
        if (hasWhole) {     // add the whole part to the fraction
            nu += de * whole;
        }
        num = negative ? 0L - nu : nu;
        den = de;
        result = (double) num / den;
    }

    /**
     * Returns the set level of precision. The <i>default</i> level of
     * precision is {@code 1.0E-10}, unless changed.
     *
     * @return The level of precision.
     */
    public static double getPrecision() {
        return precision;
    }

    /**
     * Changes the set level of precision. However, the maximum and minimum
     * levels of precision are defined and the value of precision
     * <i>snaps</i> to these values if the parameter is <i>more</i> or
     * <i>less</i> than them, respectively.
     *
     * @param precision The level of precision to set.
     */
    public static void setPrecision(double precision) {
        if (precision < 0) precision = 0D - precision;
        if (precision < HIST_PREC) precision = HIST_PREC;
        else if (precision > LWST_PREC) precision = LWST_PREC;
        Rational.precision = precision;
    }

//    public long getNum() {
//        return num;
//    }

//    public long getDen() {
//        return den;
//    }

    /**
     * Returns the Highest Common Factor of two integers. It employs the
     * Euclidean division method.
     *
     * @param a One of the two numbers.
     * @param b The other number.
     * @return The H.C.F of {@code a} and {@code b}.
     */
    private static long hcf(long a, long b) {
        if (a == 0 || b == 0) {
            return 0;       // ???
        }
        // turn all the negative arguments to positive.
        if (a < 0) a = 0L - a;
        if (b < 0) b = 0L - b;

        if (a < b) {
            long t = a;
            a = b;
            b = t;
        }
        long r;
        do {
            r = a % b;
            a = b;
            b = r;
        } while (r > 0);
        return a;
    }

    // Demo
    public static void main(String[] args) {
        Rational PI = new Rational(Math.PI);
        System.out.println("Pi = " + PI);
    }

    /**
     * This method returns the {@code Rational} object that is the reduced
     * form of {@code this Rational}. (More specifically,
     * the numerator and denominator have no common factor.)
     *
     * @return The reduced form of {@code this Rational}.
     */
    public Rational reduce() {
        long hcf = hcf(num, den);
        if (hcf == 0) { // infinities and NaN
            return this;
        } else {
            long n = num / hcf;
            long d = den / hcf;
            return new Rational(n, d);
        }
    }

    /**
     * Returns the <i>sum</i> of {@code rational} with {@code this}.
     *
     * @param rational The {@code Rational} to add.
     * @return Their sum.
     */
    public Rational add(Rational rational) {
        if (this.result == Double.NaN) {
            return this;
        } else //noinspection ConstantConditions
            if (rational.result == Double.NaN) {
                return rational;
            }
        Rational o = reduce();
        long n1 = o.num, d1 = o.den;
        o = rational.reduce();
        long n2 = o.num, d2 = o.den;
        return new Rational(n1 * d2 + n2 * d1, d1 * d2).reduce();
    }

    /**
     * Returns the <i>difference</i> of {@code rational} with {@code this}.
     *
     * @param rational The {@code Rational} to subtract.
     * @return Their difference.
     */
    public Rational subtract(Rational rational) {
        return add(new Rational(0L - rational.num, rational.den));
    }

    /**
     * Returns the <i>product</i> of {@code rational} and {@code this}.
     *
     * @param rational The {@code Rational} to multiply with.
     * @return Their product.
     */
    public Rational multiply(Rational rational) {
        return new Rational(
                this.num * rational.num,
                this.den * rational.den)
                .reduce();
    }

    /**
     * <i>Divides</i> {@code this} with {@code rational}.
     *
     * @param rational The divisor.
     * @return The required quotient.
     */
    public Rational divide(Rational rational) {
        return multiply(rational.reciprocate());
    }

    /**
     * Returns the reciprocal of {@code this}.
     *
     * @return the reciprocal of {@code this}.
     */
    public Rational reciprocate() {
        return new Rational(den, num);
    }

    /**
     * Returns the {@code double} representation of tis {@code Rational}.
     *
     * @return the {@code double} representation of tis {@code Rational}.
     */
    public double toDouble() {
        return result;
    }

    /**
     * Returns the {@code String} representation of tis {@code Rational}.
     *
     * @return the {@code String} representation of tis {@code Rational}.
     */
    @Override
    public String toString() {
        return Long.toString(num).concat("/").concat(Long.toString(den));
    }

    /**
     * Compares {@code this} object with another with respect to class and
     * then the values of the numerator and denominator.
     *
     * @param another The {@code Object} to compare with.
     * @return {@code true} if the objects are equal, {@code false} otherwise.
     */
    @Override
    public boolean equals(Object another) {
        if (another instanceof Rational) {
            Rational oldF = reduce();
            Rational newF = ((Rational) another).reduce();
            return (oldF.num == newF.num) &&
                    (oldF.den == newF.den);
        }
        return false;
    }

    /**
     * Returns {@code this} to the power {@code p}.
     *
     * @param p The power to be raised to.
     * @return {@code this} to the power {@code p}.
     */
    public Rational pow(int p) {
        Rational result = ONE;
        Rational n = new Rational(num, den);
        boolean neg = p < 0;
        if (neg) p = 0 - p;
        while (p > 0) {
            if ((p & 1) == 1) {
                result = result.multiply(n);
                p--;
            }
            n = n.multiply(n);
            p >>>= 1;
        }
        return neg ? result.reciprocate() : result;
    }

    /**
     * Returns {@code this} to the <i>fractional</i> power {@code p}.
     *
     * @param p The power to be raised to.
     * @return {@code this} to the power {@code p}.
     */
    public Rational pow(Rational p) {
        return new Rational(Math.pow(this.result, p.result));
    }
}

RationalTest.java

import junit.framework.TestCase;

public class RationalTest extends TestCase {

    public void testAdd() {
        Rational r1, r2;
        r1 = new Rational(10, 20);
        r2 = new Rational(20, 30);
        assertEquals(new Rational(7, 6), r1.add(r2));
    }

    public void testSubtract() {
        Rational r1, r2;
        r1 = new Rational(20, 30);
        r2 = new Rational(10, 20);
        assertEquals(new Rational(1, 6), r1.subtract(r2));
    }

    public void testMultiply() {
        Rational r1, r2;
        r1 = new Rational(0.5);
        r2 = new Rational(2);
        assertEquals(Rational.ONE, r1.multiply(r2));
    }

    public void testDivide() {
        Rational r1, r2;
        r1 = new Rational(0.5);
        r2 = new Rational(0.0625);
        assertEquals(new Rational(8), r1.divide(r2));
    }

    public void testPow() {
        assertEquals(Rational.ONE, new Rational(2).pow(Rational.ZERO));
        assertEquals(new Rational(1, 64), new Rational(1, 4).pow(3));
    }
}

This is the first version and more tests are needed (this is where I would really appreciate suggestions and illustrations). Inspite of that, my code works really well. Using the default settings, the following result is obtained:

Pi = 312689/99532

This evaluates to 3.1415926536189366233975003014106. Now, the real π is 3.1415926535897932384626433832795 and is only 2.9143384934856918131098731363655e-11 away from the result. I would request everyone to go on and experiment with my code, find out any flaws in my code and suggest ways for improvement.

Improve this question
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Suggestion : have this class extend java.lang.Number \$\endgroup\$
    – bowmore
    Dec 6, 2014 at 14:08
  • \$\begingroup\$ You'd need some randomized tests. Generate a random double a few thousand time and look when overflow happens. If the conversion never overflows, then it's fine, but the operations with the numbers surely will. \$\endgroup\$
    – maaartinus
    Dec 6, 2014 at 18:02

2 Answers 2

Reset to default
2
\$\begingroup\$

Creating a Rational from a double

Does it really make sense for a Rational class to have a constructor that takes a double? It seems to me that a factory method would be more interesting for this purpose, for example:

public static Rational fromDouble(double decimal) {
    if (decimal == Double.NaN) {
        return new Rational(0, 0);
    }
    if (decimal == Double.POSITIVE_INFINITY) {
        return new Rational(1, 0);
    }
    if (decimal == Double.NEGATIVE_INFINITY) {
        return new Rational(-1, 0);
    }
    // ...

Notice the added advantage that this technique can reuse logic in the canonical constructor.

Single responsibility principle

The Rational class does these things:

  • Represent a rational number composed of numerator and denominator
  • Normalize the sign of numerator and denominator to canonical form (keep sign in numerator)
  • Perform operations on rational numbers: add, subtract and others
  • Calculate an approximation to a double
  • Calculate highest common factor
  • ...

Some of these operations fit nicely in the Rational class. Some sound like they could be elsewhere.

I suggest moving the calculations outside to a different class. They are not essential for the functioning of Rational, and weaken the cohesion of the other methods of the class.

Unit testing

It's great that you have unit tests. But I recommend using JUnit4 instead of JUnit3. Changing is as simple as adding @Test annotation for the test cases, and changing the imports.

Naming

The constructor takes numerator and denominator, but inside the class you're using num and den. I suggest to spell out properly numerator and denominator inside the class too.

Similarly:

    long nu, de;

Although this looks comic ("nude", chuckles), I suggest to find better names.

Finally, result is not a great name for what it represents. What sense does it make for a Rational to have a "result"? doubleValue or value would be better.

Negating numbers

You're doing 0L - something or 0D - something a lot. Why not simply -something? For example instead of this:

        numerator = 0L - numerator;
        denominator = 0L - denominator;

Simply:

        numerator = -numerator;
        denominator = -denominator;
Improve this answer
\$\endgroup\$
2
\$\begingroup\$ 
private static final double LWST_PREC = 1E-3;
private static final double HIST_PREC = 1E-16;

WAT? "lust precedence" and "historical precession"? Please don't. "prec" may be fine, but use "max" and "min" if you want to save letters.

private static double precision = 1E-10;

And if you write "prec" once, then stick with it. But given how rarely this word occurs in the long text, you save close to nothing.

public Rational(double decimal)

This is a misnomer. double is not a "decimal", it's much more "binary" than "decimal" as it can't represent \$\frac1{10}\$ exactly but it can represent \$\frac1{2}\$ and many its powers.

It should be a factory method rather than a constructor. A constructor usually does about nothing but sanity checks and field assingments. And that's a good thing, as anything else constructors can hardly be reused.

Creating a Rational from a double is surely not the most straightforward way. I can imagine it to accept additional arguments as precission and RoundingMode.

if (decimal == Double.NaN) {

can't work, as NaN != NaN (strange but true!).

long nu, de;

Nude? Anyway, they should be final.

num = negative ? 0L - whole : whole;

Why not unary minus:

num = negative ? -whole : whole;

The conversion is not obvious (and I'm too lazy). Anyway, I guess that overflow may happen and then you get pure non-sense out of it.

public static void setPrecision(double precision) {

A setter for a static is practically always wrong. Imagine a multithreaded program using different precisions in different places. But you need no multithreading to get burned by global state. There should be a RationalFactory, which would allow you to set such parameters and produce Rationals with them.

"Highest Common Factor" - never heard of it. "gcd" is the common term.

if (a == 0 || b == 0) {
    return 0;       // ???
}

Why not

checkArgument(a != 0 || b != 0);

using Preconditions when you encounter a case you deem impossible? However, it's wrong. The proper answer is

if (a == 0) return b;
if (b == 0) return a;

Actually, you'd better call Guava's gcd.

public Rational reduce() {

You should most probably reduce the numbers immediately when created. For your equals they're are the same, so why not do it ASAP? This would lower the chance of overflow in all your operations.

All your operations should probably check for overflow. Integer arithmetic doesn't do it, as it has to be damn fast, overflows are rare, and the check isn't free. Rational arithmetic is way slower, so the check doesn't matter much, and overflows may get pretty common.

Long.toString(num).concat("/").concat(Long.toString(den));

That's obfuscated and probably slower way to say

num + "/" + den

...to be continued...

Improve this answer
\$\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.