src/com/android/calculator2/BoundedRational.java

/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// TODO: This is currently not hooked up to anything.  I started writing
// it to capture my thoughts on heuristics for detecting specific exact
// values.

package com.android.calculator2;

// We implement rational numbers of bounded size.
// If the length of the nuumerator plus the length of the denominator
// exceeds a maximum size, we simply return null, and rely on our caller
// do something else.
// We currently never return null for a pure integer.
// TODO: Reconsider that.  With some care, large factorials might
//       become much faster.
//
// We also implement a number of irrational functions.  These return
// a non-null result only when the result is known to be rational.

import java.math.BigInteger;
import com.hp.creals.CR;

public class BoundedRational {
    // TODO: Maybe eventually make this extend Number?
    private static final int MAX_SIZE = 400; // total, in bits

    private final BigInteger mNum;
    private final BigInteger mDen;

    public BoundedRational(BigInteger n, BigInteger d) {
        mNum = n;
        mDen = d;
    }

    public BoundedRational(BigInteger n) {
        mNum = n;
        mDen = BigInteger.ONE;
    }

    public BoundedRational(long n, long d) {
        mNum = BigInteger.valueOf(n);
        mDen = BigInteger.valueOf(d);
    }

    public BoundedRational(long n) {
        mNum = BigInteger.valueOf(n);
        mDen = BigInteger.valueOf(1);
    }

    // Debug or log messages only, not pretty.
    public static String toString(BoundedRational r) {
        if (r == null) return "not a small rational";
        return r.mNum.toString() + "/" + r.mDen.toString();
    }

    // Primarily for debugging; clearly not exact
    public double doubleValue() {
        return mNum.doubleValue() / mDen.doubleValue();
    }

    public CR CRValue() {
        return CR.valueOf(mNum).divide(CR.valueOf(mDen));
    }

    private boolean tooBig() {
        if (mDen.equals(BigInteger.ONE)) return false;
        return (mNum.bitLength() + mDen.bitLength() > MAX_SIZE);
    }

    // return an equivalent fraction with a positive denominator.
    private BoundedRational positive_den() {
        if (mDen.compareTo(BigInteger.ZERO) > 0) return this;
        return new BoundedRational(mNum.negate(), mDen.negate());
    }

    // Return an equivalent fraction in lowest terms.
    private BoundedRational reduce() {
        if (mDen.equals(BigInteger.ONE)) return this;  // Optimization only
        BigInteger divisor = mNum.gcd(mDen);
        return new BoundedRational(mNum.divide(divisor), mDen.divide(divisor));
    }

    // Return a possibly reduced version of this that's not tooBig.
    // Return null if none exists.
    private BoundedRational maybeReduce() {
        if (!tooBig()) return this;
        BoundedRational result = positive_den();
        if (!result.tooBig()) return this;
        result = result.reduce();
        if (!result.tooBig()) return this;
        return null;
    }

    public int compareTo(BoundedRational r) {
        // Compare by multiplying both sides by denominators,
        // invert result if denominator product was negative.
        return mNum.multiply(r.mDen).compareTo(r.mNum.multiply(mDen))
                * mDen.signum() * r.mDen.signum();
    }

    public int signum() {
        return mDen.signum() * mDen.signum();
    }

    public boolean equals(BoundedRational r) {
        return compareTo(r) == 0;
    }

    // We use static methods for arithmetic, so that we can
    // easily handle the null case.
    // We try to catch domain errors whenever possible, sometimes even when
    // one of the arguments is null, but not relevant.

    // Returns equivalent BigInteger result if it exists, null if not.
    public static BigInteger asBigInteger(BoundedRational r) {
        if (r == null) return null;
        if (!r.mDen.equals(BigInteger.ONE)) r = r.reduce();
        if (!r.mDen.equals(BigInteger.ONE)) return null;
        return r.mNum;
    }
    public static BoundedRational add(BoundedRational r1, BoundedRational r2) {
        if (r1 == null || r2 == null) return null;
        final BigInteger den = r1.mDen.multiply(r2.mDen);
        final BigInteger num = r1.mNum.multiply(r2.mDen)
                                      .add(r2.mNum.multiply(r1.mDen));
        return new BoundedRational(num,den).maybeReduce();
    }

    public static BoundedRational negate(BoundedRational r) {
        if (r == null) return null;
        return new BoundedRational(r.mNum.negate(), r.mDen);
    }

    static BoundedRational subtract(BoundedRational r1, BoundedRational r2) {
        return add(r1, negate(r2));
    }

    static BoundedRational multiply(BoundedRational r1, BoundedRational r2) {
        // It's tempting but marginally unsound to reduce 0 * null to zero.
        // The null could represent an infinite value, for which we
        // failed to throw an exception because it was too big.
        if (r1 == null || r2 == null) return null;
        final BigInteger num = r1.mNum.multiply(r2.mNum);
        final BigInteger den = r1.mDen.multiply(r2.mDen);
        return new BoundedRational(num,den).maybeReduce();
    }

    static BoundedRational inverse(BoundedRational r) {
        if (r == null) return null;
        if (r.mNum.equals(BigInteger.ZERO)) {
            throw new ArithmeticException("Divide by Zero");
        }
        return new BoundedRational(r.mDen, r.mNum);
    }

    static BoundedRational divide(BoundedRational r1, BoundedRational r2) {
        return multiply(r1, inverse(r2));
    }

    static BoundedRational sqrt(BoundedRational r) {
        // Return non-null if numerator and denominator are small perfect
        // squares.
        if (r == null) return null;
        r = r.positive_den().reduce();
        if (r.mNum.compareTo(BigInteger.ZERO) < 0) {
            throw new ArithmeticException("sqrt(negative)");
        }
        final BigInteger num_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(
                                                   r.mNum.doubleValue())));
        if (!num_sqrt.multiply(num_sqrt).equals(r.mNum)) return null;
        final BigInteger den_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(
                                                   r.mDen.doubleValue())));
        if (!num_sqrt.multiply(den_sqrt).equals(r.mDen)) return null;
        return new BoundedRational(num_sqrt, den_sqrt);
    }

    public final static BoundedRational ZERO = new BoundedRational(0);
    public final static BoundedRational HALF = new BoundedRational(1,2);
    public final static BoundedRational MINUS_HALF = new BoundedRational(-1,2);
    public final static BoundedRational ONE = new BoundedRational(1);
    public final static BoundedRational MINUS_ONE = new BoundedRational(-1);
    public final static BoundedRational TWO = new BoundedRational(2);
    public final static BoundedRational MINUS_TWO = new BoundedRational(-2);
    public final static BoundedRational THIRTY = new BoundedRational(30);
    public final static BoundedRational MINUS_THIRTY = new BoundedRational(-30);
    public final static BoundedRational FORTY_FIVE = new BoundedRational(45);
    public final static BoundedRational MINUS_FORTY_FIVE =
                                                new BoundedRational(-45);
    public final static BoundedRational NINETY = new BoundedRational(90);
    public final static BoundedRational MINUS_NINETY = new BoundedRational(-90);

    private static BoundedRational map0to0(BoundedRational r) {
        if (r == null) return null;
        if (r.mNum.equals(BigInteger.ZERO)) {
            return ZERO;
        }
        return null;
    }

    private static BoundedRational map1to0(BoundedRational r) {
        if (r == null) return null;
        if (r.mNum.equals(r.mDen)) {
            return ZERO;
        }
        return null;
    }

    // Throw an exception if the argument is definitely out of bounds for asin
    // or acos.
    private static void checkAsinDomain(BoundedRational r) {
        if (r == null) return;
        if (r.mNum.abs().compareTo(r.mDen.abs()) > 0) {
            throw new ArithmeticException("inverse trig argument out of range");
        }
    }

    public static BoundedRational sin(BoundedRational r) {
        return map0to0(r);
    }

    private final static BigInteger BIG360 = BigInteger.valueOf(360);

    public static BoundedRational degreeSin(BoundedRational r) {
        final BigInteger r_BI = asBigInteger(r);
        if (r_BI == null) return null;
        final int r_int = r_BI.mod(BIG360).intValue();
        if (r_int % 30 != 0) return null;
        switch (r_int / 10) {
        case 0:
            return ZERO;
        case 3: // 30 degrees
            return HALF;
        case 9:
            return ONE;
        case 15:
            return HALF;
        case 18: // 180 degrees
            return ZERO;
        case 21:
            return MINUS_HALF;
        case 27:
            return MINUS_ONE;
        case 33:
            return MINUS_HALF;
        default:
            return null;
        }
    }

    public static BoundedRational asin(BoundedRational r) {
        checkAsinDomain(r);
        return map0to0(r);
    }

    public static BoundedRational degreeAsin(BoundedRational r) {
        checkAsinDomain(r);
        final BigInteger r2_BI = asBigInteger(multiply(r, TWO));
        if (r2_BI == null) return null;
        final int r2_int = r2_BI.intValue();
        // Somewhat surprisingly, it seems to be the case that the following
        // covers all rational cases:
        switch (r2_int) {
        case -2: // Corresponding to -1 argument
            return MINUS_NINETY;
        case -1: // Corresponding to -1/2 argument
            return MINUS_THIRTY;
        case 0:
            return ZERO;
        case 1:
            return THIRTY;
        case 2:
            return NINETY;
        default:
            throw new AssertionError("Impossible asin arg");
        }
    }

    public static BoundedRational tan(BoundedRational r) {
        // Unlike the degree case, we cannot check for the singularity,
        // since it occurs at an irrational argument.
        return map0to0(r);
    }

    public static BoundedRational degreeTan(BoundedRational r) {
        final BoundedRational degree_sin = degreeSin(r);
        final BoundedRational degree_cos = degreeCos(r);
        if (degree_cos != null && degree_cos.mNum.equals(BigInteger.ZERO)) {
            throw new ArithmeticException("Tangent undefined");
        }
        return divide(degree_sin, degree_cos);
    }

    public static BoundedRational atan(BoundedRational r) {
        return map0to0(r);
    }

    public static BoundedRational degreeAtan(BoundedRational r) {
        final BigInteger r_BI = asBigInteger(r);
        if (r_BI == null) return null;
        if (r_BI.abs().compareTo(BigInteger.ONE) > 0) return null;
        final int r_int = r_BI.intValue();
        // Again, these seem to be all rational cases:
        switch (r_int) {
        case -1:
            return MINUS_FORTY_FIVE;
        case 0:
            return ZERO;
        case 1:
            return FORTY_FIVE;
        default:
            throw new AssertionError("Impossible atan arg");
        }
    }

    public static BoundedRational cos(BoundedRational r) {
        // Maps 0 to 1, null otherwise
        if (r == null) return null;
        if (r.mNum.equals(BigInteger.ZERO)) {
            return ONE;
        }
        return null;
    }

    public static BoundedRational degreeCos(BoundedRational r) {
        return degreeSin(add(r, NINETY));
    }

    public static BoundedRational acos(BoundedRational r) {
        checkAsinDomain(r);
        return map1to0(r);
    }

    public static BoundedRational degreeAcos(BoundedRational r) {
        final BoundedRational asin_r = degreeAsin(r);
        return subtract(NINETY, asin_r);
    }

    private static final BigInteger BIG_TWO = BigInteger.valueOf(2);

    // Compute an integral power of this
    private BoundedRational pow(BigInteger exp) {
        if (exp.compareTo(BigInteger.ZERO) < 0) {
            return inverse(pow(exp.negate()));
        }
        if (exp.equals(BigInteger.ONE)) return this;
        if (exp.and(BigInteger.ONE).intValue() == 1) {
            return multiply(pow(exp.subtract(BigInteger.ONE)), this);
        }
        if (exp.equals(BigInteger.ZERO)) {
            return ONE;
        }
        BoundedRational tmp = pow(exp.shiftRight(1));
        return multiply(tmp, tmp);
    }

    public static BoundedRational pow(BoundedRational base, BoundedRational exp) {
        if (exp == null) return null;
        if (exp.mNum.equals(BigInteger.ZERO)) {
            return new BoundedRational(1);
        }
        if (base == null) return null;
        exp = exp.reduce().positive_den();
        if (!exp.mDen.equals(BigInteger.ONE)) return null;
        return base.pow(exp.mNum);
    }

    public static BoundedRational ln(BoundedRational r) {
        if (r != null && r.signum() < 0) {
            throw new ArithmeticException("log(negative)");
        }
        return map1to0(r);
    }

    // Return the base 10 log of n, if n is a power of 10, -1 otherwise.
    private static long b10Log(BigInteger n) {
        // This algorithm is very naive, but we doubt it matters.
        long count = 0;
        while (n.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            n = n.divide(BigInteger.TEN);
            ++count;
        }
        if (n.equals(BigInteger.ONE)) {
            return count;
        }
        return -1;
    }

    public static BoundedRational log(BoundedRational r) {
        if (r == null) return null;
        if (r.signum() < 0) {
            throw new ArithmeticException("log(negative)");
        }
        r = r.reduce();
        if (r == null) return null;
        if (r.mDen.equals(BigInteger.ONE)) {
            long log = b10Log(r.mNum);
            if (log != -1) return new BoundedRational(log);
        } else if (r.mNum.equals(BigInteger.ONE)) {
            long log = b10Log(r.mDen);
            if (log != -1) return new BoundedRational(-log);
        }
        return null;
    }

    // Generalized factorial.
    // Compute n * (n - step) * (n - 2 * step) * ...
    // This can be used to compute factorial a bit faster, especially
    // if BigInteger uses sub-quadratic multiplication.
    private static BigInteger genFactorial(long n, long step) {
        if (n > 4 * step) {
            BigInteger prod1 = genFactorial(n, 2 * step);
            BigInteger prod2 = genFactorial(n - step, 2 * step);
            return prod1.multiply(prod2);
        } else {
            BigInteger res = BigInteger.valueOf(n);
            for (long i = n - step; i > 1; i -= step) {
                res = res.multiply(BigInteger.valueOf(i));
            }
            return res;
        }
    }

    // Factorial;
    // always produces non-null (or exception) when called on non-null r.
    public static BoundedRational fact(BoundedRational r) {
        if (r == null) return null; // Caller should probably preclude this case.
        final BigInteger r_BI = asBigInteger(r);
        if (r_BI == null) {
            throw new ArithmeticException("Non-integral factorial argument");
        }
        if (r_BI.signum() < 0) {
            throw new ArithmeticException("Negative factorial argument");
        }
        if (r_BI.bitLength() > 30) {
            // Will fail.  LongValue() may not work. Punt now.
            throw new ArithmeticException("Factorial argument too big");
        }
        return new BoundedRational(genFactorial(r_BI.longValue(), 1));
    }

    private static final BigInteger BIG_FIVE = BigInteger.valueOf(5);

    // Return the number of decimal digits to the right of the
    // decimal point required to represent the argument exactly,
    // or Integer.MAX_VALUE if it's not possible.
    // Never returns a value les than zero, even if r is
    // a power of ten.
    static int digitsRequired(BoundedRational r) {
        if (r == null) return Integer.MAX_VALUE;
        int powers_of_two = 0;  // Max power of 2 that divides denominator
        int powers_of_five = 0;  // Max power of 5 that divides denominator
        // Try the easy case first to speed things up.
        if (r.mDen.equals(BigInteger.ONE)) return 0;
        r = r.reduce();
        BigInteger den = r.mDen;
        while (!den.testBit(0)) {
            ++powers_of_two;
            den = den.shiftRight(1);
        }
        while (den.mod(BIG_FIVE).equals(BigInteger.ZERO)) {
            ++powers_of_five;
            den = den.divide(BIG_FIVE);
        }
        // If the denominator has a factor of other than 2 or 5
        // (the divisors of 10), the decimal expansion does not
        // terminate.  Multiplying the fraction by any number of
        // powers of 10 will not cancel the demoniator.
        // (Recall the fraction was in lowest terms to start with.)
        // Otherwise the powers of 10 we need to cancel the denominator
        // is the larger of powers_of_two and powers_of_five.
        if (!den.equals(BigInteger.ONE)) return Integer.MAX_VALUE;
        return Math.max(powers_of_two, powers_of_five);
    }
}