Rational.prejava

#include "macros.h"

public class Rational
{
    public int n, d;

    // gets reduced to lowest terms, with non-negative denominator.
    public Rational(int n, int d)
    {
        this.set(n, d);
    }
    public Rational(Rational that)
    {
        this.set(that.n, that.d);
    }
    public Rational set(Rational that)
    {
        return this.set(that.n, that.d);
    }



    // Basic utilities, that take all args in n,d form
    // (not necessarily reduced)
    // and put the result in an existing Rational,
    // reducing it,
    // and return that Rational (for chaining).

    // XXX I haven't gotten clear on whether inputs are required to be reduced or not.
    // for a while I thought they should, but then I ran into something like
    //      a.plusEquals(b,2);  // a += b/2
    // which is a pain in the ass to express if inputs are required to be reduced...
    // it would be something horrific like:
    //      a.plusEquals(new Rational(b1).div(new Rationional(2,1)));
    // however if we *don't* require inputs to be reduced,
    // we have to reduce stuff every step of the way in the basic utilities...
    // and when utilities are used internally, they are certainly reduced.
    // so... hmm.
    // maybe should various groups of utils?
    //     - inputs allowed to be non-reduced, outputs may be non-reduced
    //     - inputs allowed to be non-reduced, outputs automaticlly reduced
    //     - inputs must be reduced, outputs automatically reduced -- used internally, can avoid reduction in some cases when they are guaranteed by inputs being reduced, hmm
    //     - inputs must be reduced, outputs not necessarily reduced -- used internally for intermediate results, maybe... however this is overflow-prone

    public Rational set(int n, int d)
    {
        this.n = n;
        this.d = d;
        reduce();
        return this;
    }
    public Rational equalsPlus(int n0, int d0, int n1, int d1)
    {
        // pre-reduce to guard against overflow...
        // note that this doesn't prevent the need to reduce at end too
        int g00 = gcd(n0,d0);
        n0 /= g00;
        d0 /= g00;
        int g11 = gcd(n1,d1);
        n1 /= g11;
        d1 /= g11;

        // overflows given 5228001/1000 - 1/1000 !
        //this.n = n0*d1 + n1*d0;
        //this.d = d0*d1;

        // so pre-reduce some more.
        // (*still* doesn't prevent need to reduce at end, e.g. -4/3 + 4/3
        int g = gcd(d0,d1);
        this.n = d1/g*n0 + d0/g*n1;
        this.d = d0/g*d1;

        reduce();
        return this;
    }
    public Rational equalsMinus(int n0, int d0, int n1, int d1)
    {
        return equalsPlus(n0,d0, -n1,d1);
    }
    public Rational equalsTimes(int n0, int d0, int n1, int d1)
    {
        // need to be careful, e.g. (2149/1000000) * (1000000/1)
        // will overflow if we naively wait til end to reduce.
        int g00 = gcd(n0,d0);
        n0 /= g00;
        d0 /= g00;
        int g11 = gcd(n1,d1);
        n1 /= g11;
        d1 /= g11;
        int g01 = gcd(n0,d1);
        n0 /= g01;
        d1 /= g01;
        int g10 = gcd(n1,d0);
        n1 /= g10;
        d0 /= g10;

        this.n = n0*n1;
        this.d = d0*d1;
        if (this.d < 0)
        {
            this.n = -this.n;
            this.d = -this.d;
        }
        CHECK(isReduced(this.n,this.d));
        return this;
    }
    public Rational equalsDiv(int n0, int d0, int n1, int d1)
    {
        // so that isReduced(d1,n1) doesn't get violated in equalsTimes...
        if (n1 < 0)
        {
            n1 = -n1;
            d1 = -d1;
        }
        return this.equalsTimes(n0,d0, d1,n1);
    }
    public Rational equalsMod(int n0, int d0, int n1, int d1)
    {
        // note, the assertions inside divEquals and timesEquals
        // guarantee that n1>0 and d1>0,
        // however failure isn't exactly obvious...
        // so assert that explicitly here too.
        CHECK_GT(n1, 0);
        CHECK_GT(d1, 0);


        // a%b = frac(a/b)*b
        // where frac(a/b) = a/b - floor(a/b)
        return this.set(n0,d0).divEquals(n1,d1).fracEquals().timesEquals(n1,d1);
    }
    // lerp(x0,x1,t) = x0 + (x1-x0)*t
    public Rational equalsLerp(int n0, int d0, int n1, int d1, int nt, int dt)
    {
        return this.equalsMinus(n1,d1,n0,d0).times(nt,dt).plus(n0,d0);
    }
    public Rational equalsNeg(int n, int d)
    {
        return this.set(-n,d);
    }
    public Rational equalsAbs(int n, int d)
    {
        return this.set(ABS(n),ABS(d));
    }
    // frac(x) = x - floor(x)
    public Rational equalsFrac(int n, int d)
    {
        this.set(n,d).minusEquals(floor(n,d),1);
        CHECK_GE(this.n, 0);
        return this;
    }


    // Accumulation functions with RHS in n/d form.
    // Answer goes back into this, with no memory allocations.
    public Rational plusEquals(int n, int d)
    {
        return this.equalsPlus(this.n,this.d, n,d);
    }
    public Rational minusEquals(int n, int d)
    {
        return this.equalsMinus(this.n,this.d, n,d);
    }
    public Rational timesEquals(int n, int d)
    {
        return this.equalsTimes(this.n,this.d, n,d);
    }
    public Rational divEquals(int n, int d)
    {
        return this.equalsDiv(this.n,this.d, n,d);
    }
    public Rational modEquals(int n, int d)
    {
        return this.equalsMod(this.n,this.d, n,d);
    }
    public Rational lerpEquals(int n1, int d1, int nt, int dt)
    {
        return this.equalsLerp(this.n,this.d, n1,d1, nt,dt);
    }
    public Rational negEquals()
    {
        return this.equalsNeg(this.n,this.d);
    }
    public Rational absEquals()
    {
        return this.equalsAbs(this.n,this.d);
    }
    public Rational fracEquals()
    {
        return this.equalsFrac(this.n,this.d);
    }


    // Accumulation functions with RHS in Rational form.
    // Answer goes back into this, with no memory allocations.
    public Rational plusEquals(Rational that)
    {
        return this.plusEquals(that.n, that.d);
    }
    public Rational minusEquals(Rational that)
    {
        return this.minusEquals(that.n, that.d);
    }
    public Rational timesEquals(Rational that)
    {
        return this.timesEquals(that.n, that.d);
    }
    public Rational divEquals(Rational that)
    {
        return this.divEquals(that.n, that.d);
    }
    public Rational modEquals(Rational that)
    {
        return this.modEquals(that.n, that.d);
    }
    public Rational lerpEquals(Rational that, Rational t)
    {
        return this.equalsLerp(this.n,this.d, that.n,that.d, t.n,t.d);
    }

    // Accumulation functions with one RHS in n/d form and the other in Rational form.
    public Rational lerpEquals(int n1, int d1, Rational t)
    {
        return this.equalsLerp(this.n,this.d, n1,d1, t.n,t.d);
    }
    public Rational lerpEquals(Rational that, int nt, int dt)
    {
        return this.equalsLerp(this.n,this.d, that.n,that.d, nt,dt);
    }




    // Static functions allocating answer, with LHS and RHS in n/d form.
    public static Rational plus(int n0, int d0, int n1, int d1)
    {
        return new Rational(n0,d0).plusEquals(n1,d1);
    }
    public static Rational minus(int n0, int d0, int n1, int d1)
    {
        return new Rational(n0,d0).minusEquals(n1,d1);
    }
    public static Rational times(int n0, int d0, int n1, int d1)
    {
        return new Rational(n0,d0).timesEquals(n1,d1);
    }
    public static Rational div(int n0, int d0, int n1, int d1)
    {
        return new Rational(n0,d0).divEquals(n1,d1);
    }
    public static Rational mod(int n0, int d0, int n1, int d1)
    {
        return new Rational(n0,d0).modEquals(n1,d1);
    }
    public static Rational neg(int n0, int d0)
    {
        return new Rational(n0,d0).negEquals();
    }
    public static Rational abs(int n0, int d0)
    {
        return new Rational(n0,d0).absEquals();
    }
    public static Rational frac(int n0, int d0)
    {
        return new Rational(n0,d0).fracEquals();
    }



    // Functions allocating answer, with RHS in n/d form.
    public Rational plus(int n, int d)
    {
        return plus(this.n,this.d, n,d);
    }
    public Rational minus(int n, int d)
    {
        return minus(this.n,this.d, n,d);
    }
    public Rational times(int n, int d)
    {
        return times(this.n,this.d, n,d);
    }
    public Rational div(int n, int d)
    {
        return div(this.n,this.d, n,d);
    }
    public Rational mod(int n, int d)
    {
        return mod(this.n,this.d, n,d);
    }
    public Rational neg()
    {
        return neg(this.n,this.d);
    }
    public Rational abs()
    {
        return abs(this.n,this.d);
    }
    public Rational frac()
    {
        return frac(this.n,this.d);
    }


    // Functions allocating answer, with RHS in Rational form.
    public Rational plus(Rational that)
    {
        return this.plus(that.n, that.d);
    }
    public Rational minus(Rational that)
    {
        return this.minus(that.n, that.d);
    }
    public Rational times(Rational that)
    {
        return this.times(that.n, that.d);
    }
    public Rational div(Rational that)
    {
        return this.div(that.n, that.d);
    }
    public Rational mod(Rational that)
    {
        return this.mod(that.n, that.d);
    }
    // neg,abs,frac have no RHS so already handled by RHS-in-n/d form




    // round a down to c mod b.
    // floor(a) = generalFloor(a,1,0)
    public Rational equalsGeneralFloor(int an, int ad, int bn, int bd, int cn, int cd)
    {
        return this.equalsMinus(an,ad,cn,cd).divEquals(bn,bd).floorEquals().timesEquals(bn,bd).plusEquals(cn,cd);
    }
    // round a up to c mod b
    // ceil(a) = generalCeil(a,1,0)
    public Rational equalsGeneralCeil(int an, int ad, int bn, int bd, int cn, int cd)
    {
        // generalCeil(a,b,c) = ceil((a-c)/b)*b+c
        return this.equalsMinus(an,ad,cn,cd).divEquals(bn,bd).ceilEquals().timesEquals(bn,bd).plusEquals(cn,cd);
    }
    // round a to c mod b
    // i.e. find the number equal to c mod b that's as close as possible to a.
    public Rational equalsGeneralRound(int an, int ad, int bn, int bd, int cn, int cd)
    {
        // generalRound(a,b,c) = round((a-c)/b)*b+c
        return this.equalsMinus(an,ad,cn,cd).divEquals(bn,bd).roundEquals().timesEquals(bn,bd).plusEquals(cn,cd);
    }
    // a - generalFloor(a,b,c)
    // frac(a) = generalFrac(a,1,0)
    public Rational equalsGeneralFrac(int an, int ad, int bn, int bd, int cn, int cd)
    {
        return equalsGeneralFloor(an,ad, bn,bd, cn,cd).minusEquals(an,ad).negEquals();

    }

    // 6 groups of functions, e.g.
    //     equalsPlus(int,int,int,int)
    //         plusEquals(int,int)
    //             plusEquals(Rational)
    //             static plus(int,int,int,int)  (allocates new)
    //                 plus(int,int)
    //                     plus(Rational) // could also implement by allocating new and calling plusEquals(Rational)

    public Rational generalFloorEquals(int bn, int bd, int cn, int cd)
    {
        return this.equalsGeneralFloor(this.n,this.d, bn,bd, cn,cd);
    }
    public Rational generalCeilEquals(int bn, int bd, int cn, int cd)
    {
        return this.equalsGeneralCeil(this.n,this.d, bn,bd, cn,cd);
    }
    public Rational generalRoundEquals(int bn, int bd, int cn, int cd)
    {
        return this.equalsGeneralRound(this.n,this.d, bn,bd, cn,cd);
    }
    public Rational generalFracEquals(int bn, int bd, int cn, int cd)
    {
        return this.equalsGeneralFrac(this.n,this.d, bn,bd, cn,cd);
    }

    public Rational generalFloorEquals(Rational b, Rational c)
    {
        return this.generalFloorEquals(b.n,b.d, c.n,c.d);
    }
    public Rational generalCeilEquals(Rational b, Rational c)
    {
        return this.generalCeilEquals(b.n,b.d, c.n,c.d);
    }
    public Rational generalRoundEquals(Rational b, Rational c)
    {
        return this.generalRoundEquals(b.n,b.d, c.n,c.d);
    }
    public Rational generalFracEquals(Rational b, Rational c)
    {
        return this.generalFracEquals(b.n,b.d, c.n,c.d);
    }

    // XXX somewhat hacky-- add more with default c=0.
    // this made it easier for a caller, but I'm not sure I like this--
    // it makes the "c" parameter less discoverable,
    // and if we do it here, shouldn't we do it everyhwere?
    public Rational generalFloorEquals(Rational b)
    {
        return this.generalFloorEquals(b.n,b.d, 0,1);
    }
    public Rational generalCeilEquals(Rational b)
    {
        return this.generalCeilEquals(b.n,b.d, 0,1);
    }
    public Rational generalRoundEquals(Rational b)
    {
        return this.generalRoundEquals(b.n,b.d, 0,1);
    }
    public Rational generalFracEquals(Rational b)
    {
        return this.generalFracEquals(b.n,b.d, 0,1);
    }



    public static Rational generalFloor(int an, int ad, int bn, int bd, int cn, int cd)
    {
        return new Rational(an,ad).generalFloorEquals(bn,bd, cn,cd);
    }
    public static Rational generalCeil(int an, int ad, int bn, int bd, int cn, int cd)
    {
        return new Rational(an,ad).generalCeilEquals(bn,bd, cn,cd);
    }
    public static Rational generalRound(int an, int ad, int bn, int bd, int cn, int cd)
    {
        return new Rational(an,ad).generalRoundEquals(bn,bd, cn,cd);
    }
    public static Rational generalFrac(int an, int ad, int bn, int bd, int cn, int cd)
    {
        return new Rational(an,ad).generalFracEquals(bn,bd, cn,cd);
    }

    public Rational generalFloor(int bn, int bd, int cn, int cd)
    {
        return generalFloor(this.n,this.d, bn,bd, cn,cd);
    }
    public Rational generalCeil(int bn, int bd, int cn, int cd)
    {
        return generalCeil(this.n,this.d, bn,bd, cn,cd);
    }
    public Rational generalRound(int bn, int bd, int cn, int cd)
    {
        return generalRound(this.n,this.d, bn,bd, cn,cd);
    }
    public Rational generalFrac(int bn, int bd, int cn, int cd)
    {
        return generalFrac(this.n,this.d, bn,bd, cn,cd);
    }

    public Rational generalFloor(Rational b, Rational c)
    {
        return generalFloor(b.n,b.d, c.n,c.d);
    }
    public Rational generalCeil(Rational b, Rational c)
    {
        return generalCeil(b.n,b.d, c.n,c.d);
    }
    public Rational generalRound(Rational b, Rational c)
    {
        return generalRound(b.n,b.d, c.n,c.d);
    }
    public Rational generalFrac(Rational b, Rational c)
    {
        return generalFrac(b.n,b.d, c.n,c.d);
    }


    private static int intmod(int a, int b)
    {
        CHECK_GT(b, 0);
        int answer = a % b;
        // work around stupid semantics for when a<0
        if (! (answer >= 0))
        {
            answer += b;
            CHECK_GE(answer, 0);
        }
        return answer;
    }

    // Static functions returning int, taking arg in n/d form.
    public static int floor(int n, int d)
    {
        return (n-intmod(n,d))/d;
    }
    public static int ceil(int n, int d)
    {
        return floor(n+d-1, d);
    }
    public static int round(int n, int d)
    {
        return floor(2*n+d,2*d); // floor(x + 1/2)
    }

    // Member functions returning int.
    public int floor()
    {
        return floor(this.n,this.d);
    }
    public int ceil()
    {
        return ceil(this.n,this.d);
    }
    public int round()
    {
        return round(this.n,this.d);
    }

    public Rational floorEquals()
    {
        this.n = floor();
        this.d = 1; // so no need for reduce()
        return this;
    }
    public Rational ceilEquals()
    {
        this.n = ceil();
        this.d = 1; // so no need for reduce()
        return this;
    }
    public Rational roundEquals()
    {
        this.n = round();
        this.d = 1; // so no need for reduce()
        return this;
    }



    public double toDouble()
    {
        CHECK(isReduced(this.n,this.d));
        return (double)n/(double)d;
    }
    public String toString()
    {
        CHECK(isReduced(this.n,this.d));
        if (false)
        {
            if (d == 1)
                return ""+n;
            return n+"/"+d;
        }
        else
        {
            int n = this.n;
            if (d == 1)
                return ""+n;
            CHECK_NE(n, 0);
            String answer;
            if (n < 0)
            {
                answer = "-";
                n = -n;
            }
            else
            {
                answer = "";
            }
            if (n/d != 0)
                answer += n/d + " ";
            answer += n%d + "/" + d;
            return answer;
        }
    }


    // reduce to lowest terms, with non-negative denominator.
    // the only place this is used is at the end of equalsPlus() and equalsMinus();
    // in all other places, Rationals are kept in reduced form throughout.
    private void reduce()
    {
        CHECK_NE(this.d, 0);
        if (this.d < 0)
        {
            this.n = -this.n;
            this.d = -this.d;
        }
        int g = gcd(this.n,this.d);
        this.n /= g;
        this.d /= g;
    }
    private static boolean isReduced(int n, int d)
    {
        return d > 0 && gcd(n,d) == 1;
    }

    // private restricted implementation of greatest-common-divisor.
    private static int gcd(int a, int b)
    {
        if (a < 0)
            a = -a;
        if (b < 0)
            b = -b;
        while (true)
        {
            if (a == 0)
                return b;
            b %= a;
            if (b == 0)
                return a;
            a %= b;
        }
    }


    // XXX does this belong in MyMath or something?
    // only used in confidence test
    public static double fmod(double a, double b)
    {
        /*  this doesn't work-- roundoff error!
        double temp = a / b;
        return (temp - Math.floor(temp)) * b;
        */
        a %= b;
        if (a < 0.) // retarded
            a += b;
        return a;
    }


    public static void confidenceTest()
    {
        System.out.println("in Rational.confidenceTest");

        if (true)
        {
            // the following is prone to overflowing an int if done naively
            CHECK_EQ(new Rational(2149,1).mod(new Rational(1000*1000,1)).toDouble(), 2149.);

            // the following was failing
            CHECK_EQ(new Rational(52228,1).plus(1,100).minus(1,100).toDouble(), 52228.);
            CHECK_EQ(new Rational(52228,1).plus(1,1000).minus(1,1000).toDouble(), 52228.);
            CHECK_EQ(new Rational(52228,1).minus(1,1000).plus(1,1000).toDouble(), 52228.);
            CHECK_EQ(new Rational(52228,1).plus(1,1000).plus(1,1000).minus(1,1000).minus(1,1000).toDouble(), 52228.);
        }

        int nMin = -4;
        int nMax = 4;
        int dMin = 1;
        int dMax = 4;
        for (int n0 = nMin; n0 <= nMax; ++n0)
        for (int d0 = dMin; d0 <= dMax; ++d0)
        {
            Rational a = new Rational(n0,d0);
            CHECK_ALMOST_EQ(a.toDouble(), 1.*n0/d0, 1e-6);

            CHECK_EQ(a.floor(), (int)Math.floor(a.toDouble()));
            CHECK_EQ(a.ceil(), (int)Math.ceil(a.toDouble()));
            CHECK_EQ(a.round(), (int)Math.round(a.toDouble()));
            CHECK_EQ(a.abs().toDouble(), ABS(a.toDouble()));
            CHECK_EQ(a.neg().toDouble(), -a.toDouble());

            for (int n1 = nMin; n1 <= nMax; ++n1)
            for (int d1 = dMin; d1 <= dMax; ++d1)
            {
                Rational b = new Rational(n1,d1);

                CHECK_ALMOST_EQ(b.toDouble(), 1.*n1/d1, 1e-6);

                CHECK_ALMOST_EQ(a.plus(b).toDouble(), (1.*n0/d0) + (1.*n1/d1), 1e-6);

                CHECK_ALMOST_EQ(a.minus(b).toDouble(), (1.*n0/d0) - (1.*n1/d1), 1e-6);

                CHECK_ALMOST_EQ(a.times(b).toDouble(), (1.*n0/d0) * (1.*n1/d1), 1e-6);

                if (n1 != 0)
                {
                    CHECK_ALMOST_EQ(a.div(b).toDouble(), (1.*n0/d0) / (1.*n1/d1), 1e-6);
                }

                if (n1 > 0
                 && d0 != 3 && d0 != -3 && d1 != 3 && d1 != -3) // if nonexact, can run into trouble where floating point results in slightly negative numbers, resulting in wildly different answer from exact one... this is expected
                {
                    CHECK_ALMOST_EQ(a.mod(b).toDouble(), fmod((1.*n0/d0) , (1.*n1/d1)), 1e-6);
                }
            }

        }
        System.out.println("out Rational.confidenceTest");
    }

    public static void main(String args[])
    {
        confidenceTest();
    }
} // Rational