Home | History | Annotate | Download | only in calculator2
      1 /*
      2  * Copyright (C) 2015 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *   http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package com.android.calculator2;
     18 
     19 
     20 import java.math.BigInteger;
     21 import com.hp.creals.CR;
     22 
     23 /**
     24  * Rational numbers that may turn to null if they get too big.
     25  * For many operations, if the length of the nuumerator plus the length of the denominator exceeds
     26  * a maximum size, we simply return null, and rely on our caller do something else.
     27  * We currently never return null for a pure integer or for a BoundedRational that has just been
     28  * constructed.
     29  *
     30  * We also implement a number of irrational functions.  These return a non-null result only when
     31  * the result is known to be rational.
     32  */
     33 public class BoundedRational {
     34     // TODO: Consider returning null for integers.  With some care, large factorials might become
     35     // much faster.
     36     // TODO: Maybe eventually make this extend Number?
     37 
     38     private static final int MAX_SIZE = 800; // total, in bits
     39 
     40     private final BigInteger mNum;
     41     private final BigInteger mDen;
     42 
     43     public BoundedRational(BigInteger n, BigInteger d) {
     44         mNum = n;
     45         mDen = d;
     46     }
     47 
     48     public BoundedRational(BigInteger n) {
     49         mNum = n;
     50         mDen = BigInteger.ONE;
     51     }
     52 
     53     public BoundedRational(long n, long d) {
     54         mNum = BigInteger.valueOf(n);
     55         mDen = BigInteger.valueOf(d);
     56     }
     57 
     58     public BoundedRational(long n) {
     59         mNum = BigInteger.valueOf(n);
     60         mDen = BigInteger.valueOf(1);
     61     }
     62 
     63     /**
     64      * Convert to String reflecting raw representation.
     65      * Debug or log messages only, not pretty.
     66      */
     67     public String toString() {
     68         return mNum.toString() + "/" + mDen.toString();
     69     }
     70 
     71     /**
     72      * Convert to readable String.
     73      * Intended for output output to user.  More expensive, less useful for debugging than
     74      * toString().  Not internationalized.
     75      */
     76     public String toNiceString() {
     77         BoundedRational nicer = reduce().positiveDen();
     78         String result = nicer.mNum.toString();
     79         if (!nicer.mDen.equals(BigInteger.ONE)) {
     80             result += "/" + nicer.mDen;
     81         }
     82         return result;
     83     }
     84 
     85     public static String toString(BoundedRational r) {
     86         if (r == null) {
     87             return "not a small rational";
     88         }
     89         return r.toString();
     90     }
     91 
     92     /**
     93      * Return a double approximation.
     94      * Primarily for debugging.
     95      */
     96     public double doubleValue() {
     97         return mNum.doubleValue() / mDen.doubleValue();
     98     }
     99 
    100     public CR CRValue() {
    101         return CR.valueOf(mNum).divide(CR.valueOf(mDen));
    102     }
    103 
    104     // Approximate number of bits to left of binary point.
    105     public int wholeNumberBits() {
    106         return mNum.bitLength() - mDen.bitLength();
    107     }
    108 
    109     private boolean tooBig() {
    110         if (mDen.equals(BigInteger.ONE)) {
    111             return false;
    112         }
    113         return (mNum.bitLength() + mDen.bitLength() > MAX_SIZE);
    114     }
    115 
    116     /**
    117      * Return an equivalent fraction with a positive denominator.
    118      */
    119     private BoundedRational positiveDen() {
    120         if (mDen.signum() > 0) {
    121             return this;
    122         }
    123         return new BoundedRational(mNum.negate(), mDen.negate());
    124     }
    125 
    126     /**
    127      * Return an equivalent fraction in lowest terms.
    128      * Denominator sign may remain negative.
    129      */
    130     private BoundedRational reduce() {
    131         if (mDen.equals(BigInteger.ONE)) {
    132             return this;  // Optimization only
    133         }
    134         final BigInteger divisor = mNum.gcd(mDen);
    135         return new BoundedRational(mNum.divide(divisor), mDen.divide(divisor));
    136     }
    137 
    138     /**
    139      * Return a possibly reduced version of this that's not tooBig().
    140      * Return null if none exists.
    141      */
    142     private BoundedRational maybeReduce() {
    143         if (!tooBig()) {
    144             return this;
    145         }
    146         BoundedRational result = positiveDen();
    147         result = result.reduce();
    148         if (!result.tooBig()) {
    149             return this;
    150         }
    151         return null;
    152     }
    153 
    154     public int compareTo(BoundedRational r) {
    155         // Compare by multiplying both sides by denominators, invert result if denominator product
    156         // was negative.
    157         return mNum.multiply(r.mDen).compareTo(r.mNum.multiply(mDen)) * mDen.signum()
    158                 * r.mDen.signum();
    159     }
    160 
    161     public int signum() {
    162         return mNum.signum() * mDen.signum();
    163     }
    164 
    165     public boolean equals(BoundedRational r) {
    166         return compareTo(r) == 0;
    167     }
    168 
    169     // We use static methods for arithmetic, so that we can easily handle the null case.  We try
    170     // to catch domain errors whenever possible, sometimes even when one of the arguments is null,
    171     // but not relevant.
    172 
    173     /**
    174      * Returns equivalent BigInteger result if it exists, null if not.
    175      */
    176     public static BigInteger asBigInteger(BoundedRational r) {
    177         if (r == null) {
    178             return null;
    179         }
    180         final BigInteger[] quotAndRem = r.mNum.divideAndRemainder(r.mDen);
    181         if (quotAndRem[1].signum() == 0) {
    182             return quotAndRem[0];
    183         } else {
    184             return null;
    185         }
    186     }
    187     public static BoundedRational add(BoundedRational r1, BoundedRational r2) {
    188         if (r1 == null || r2 == null) {
    189             return null;
    190         }
    191         final BigInteger den = r1.mDen.multiply(r2.mDen);
    192         final BigInteger num = r1.mNum.multiply(r2.mDen).add(r2.mNum.multiply(r1.mDen));
    193         return new BoundedRational(num,den).maybeReduce();
    194     }
    195 
    196     public static BoundedRational negate(BoundedRational r) {
    197         if (r == null) {
    198             return null;
    199         }
    200         return new BoundedRational(r.mNum.negate(), r.mDen);
    201     }
    202 
    203     static BoundedRational subtract(BoundedRational r1, BoundedRational r2) {
    204         return add(r1, negate(r2));
    205     }
    206 
    207     static BoundedRational multiply(BoundedRational r1, BoundedRational r2) {
    208         // It's tempting but marginally unsound to reduce 0 * null to 0.  The null could represent
    209         // an infinite value, for which we failed to throw an exception because it was too big.
    210         if (r1 == null || r2 == null) {
    211             return null;
    212         }
    213         final BigInteger num = r1.mNum.multiply(r2.mNum);
    214         final BigInteger den = r1.mDen.multiply(r2.mDen);
    215         return new BoundedRational(num,den).maybeReduce();
    216     }
    217 
    218     public static class ZeroDivisionException extends ArithmeticException {
    219         public ZeroDivisionException() {
    220             super("Division by zero");
    221         }
    222     }
    223 
    224     /**
    225      * Return the reciprocal of r (or null).
    226      */
    227     static BoundedRational inverse(BoundedRational r) {
    228         if (r == null) {
    229             return null;
    230         }
    231         if (r.mNum.signum() == 0) {
    232             throw new ZeroDivisionException();
    233         }
    234         return new BoundedRational(r.mDen, r.mNum);
    235     }
    236 
    237     static BoundedRational divide(BoundedRational r1, BoundedRational r2) {
    238         return multiply(r1, inverse(r2));
    239     }
    240 
    241     static BoundedRational sqrt(BoundedRational r) {
    242         // Return non-null if numerator and denominator are small perfect squares.
    243         if (r == null) {
    244             return null;
    245         }
    246         r = r.positiveDen().reduce();
    247         if (r.mNum.signum() < 0) {
    248             throw new ArithmeticException("sqrt(negative)");
    249         }
    250         final BigInteger num_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mNum.doubleValue())));
    251         if (!num_sqrt.multiply(num_sqrt).equals(r.mNum)) {
    252             return null;
    253         }
    254         final BigInteger den_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mDen.doubleValue())));
    255         if (!den_sqrt.multiply(den_sqrt).equals(r.mDen)) {
    256             return null;
    257         }
    258         return new BoundedRational(num_sqrt, den_sqrt);
    259     }
    260 
    261     public final static BoundedRational ZERO = new BoundedRational(0);
    262     public final static BoundedRational HALF = new BoundedRational(1,2);
    263     public final static BoundedRational MINUS_HALF = new BoundedRational(-1,2);
    264     public final static BoundedRational ONE = new BoundedRational(1);
    265     public final static BoundedRational MINUS_ONE = new BoundedRational(-1);
    266     public final static BoundedRational TWO = new BoundedRational(2);
    267     public final static BoundedRational MINUS_TWO = new BoundedRational(-2);
    268     public final static BoundedRational THIRTY = new BoundedRational(30);
    269     public final static BoundedRational MINUS_THIRTY = new BoundedRational(-30);
    270     public final static BoundedRational FORTY_FIVE = new BoundedRational(45);
    271     public final static BoundedRational MINUS_FORTY_FIVE = new BoundedRational(-45);
    272     public final static BoundedRational NINETY = new BoundedRational(90);
    273     public final static BoundedRational MINUS_NINETY = new BoundedRational(-90);
    274 
    275     private static BoundedRational map0to0(BoundedRational r) {
    276         if (r == null) {
    277             return null;
    278         }
    279         if (r.mNum.signum() == 0) {
    280             return ZERO;
    281         }
    282         return null;
    283     }
    284 
    285     private static BoundedRational map0to1(BoundedRational r) {
    286         if (r == null) {
    287             return null;
    288         }
    289         if (r.mNum.signum() == 0) {
    290             return ONE;
    291         }
    292         return null;
    293     }
    294 
    295     private static BoundedRational map1to0(BoundedRational r) {
    296         if (r == null) {
    297             return null;
    298         }
    299         if (r.mNum.equals(r.mDen)) {
    300             return ZERO;
    301         }
    302         return null;
    303     }
    304 
    305     // Throw an exception if the argument is definitely out of bounds for asin or acos.
    306     private static void checkAsinDomain(BoundedRational r) {
    307         if (r == null) {
    308             return;
    309         }
    310         if (r.mNum.abs().compareTo(r.mDen.abs()) > 0) {
    311             throw new ArithmeticException("inverse trig argument out of range");
    312         }
    313     }
    314 
    315     public static BoundedRational sin(BoundedRational r) {
    316         return map0to0(r);
    317     }
    318 
    319     private final static BigInteger BIG360 = BigInteger.valueOf(360);
    320 
    321     public static BoundedRational degreeSin(BoundedRational r) {
    322         final BigInteger r_BI = asBigInteger(r);
    323         if (r_BI == null) {
    324             return null;
    325         }
    326         final int r_int = r_BI.mod(BIG360).intValue();
    327         if (r_int % 30 != 0) {
    328             return null;
    329         }
    330         switch (r_int / 10) {
    331         case 0:
    332             return ZERO;
    333         case 3: // 30 degrees
    334             return HALF;
    335         case 9:
    336             return ONE;
    337         case 15:
    338             return HALF;
    339         case 18: // 180 degrees
    340             return ZERO;
    341         case 21:
    342             return MINUS_HALF;
    343         case 27:
    344             return MINUS_ONE;
    345         case 33:
    346             return MINUS_HALF;
    347         default:
    348             return null;
    349         }
    350     }
    351 
    352     public static BoundedRational asin(BoundedRational r) {
    353         checkAsinDomain(r);
    354         return map0to0(r);
    355     }
    356 
    357     public static BoundedRational degreeAsin(BoundedRational r) {
    358         checkAsinDomain(r);
    359         final BigInteger r2_BI = asBigInteger(multiply(r, TWO));
    360         if (r2_BI == null) {
    361             return null;
    362         }
    363         final int r2_int = r2_BI.intValue();
    364         // Somewhat surprisingly, it seems to be the case that the following covers all rational
    365         // cases:
    366         switch (r2_int) {
    367         case -2: // Corresponding to -1 argument
    368             return MINUS_NINETY;
    369         case -1: // Corresponding to -1/2 argument
    370             return MINUS_THIRTY;
    371         case 0:
    372             return ZERO;
    373         case 1:
    374             return THIRTY;
    375         case 2:
    376             return NINETY;
    377         default:
    378             throw new AssertionError("Impossible asin arg");
    379         }
    380     }
    381 
    382     public static BoundedRational tan(BoundedRational r) {
    383         // Unlike the degree case, we cannot check for the singularity, since it occurs at an
    384         // irrational argument.
    385         return map0to0(r);
    386     }
    387 
    388     public static BoundedRational degreeTan(BoundedRational r) {
    389         final BoundedRational degSin = degreeSin(r);
    390         final BoundedRational degCos = degreeCos(r);
    391         if (degCos != null && degCos.mNum.signum() == 0) {
    392             throw new ArithmeticException("Tangent undefined");
    393         }
    394         return divide(degSin, degCos);
    395     }
    396 
    397     public static BoundedRational atan(BoundedRational r) {
    398         return map0to0(r);
    399     }
    400 
    401     public static BoundedRational degreeAtan(BoundedRational r) {
    402         final BigInteger r_BI = asBigInteger(r);
    403         if (r_BI == null) {
    404             return null;
    405         }
    406         if (r_BI.abs().compareTo(BigInteger.ONE) > 0) {
    407             return null;
    408         }
    409         final int r_int = r_BI.intValue();
    410         // Again, these seem to be all rational cases:
    411         switch (r_int) {
    412         case -1:
    413             return MINUS_FORTY_FIVE;
    414         case 0:
    415             return ZERO;
    416         case 1:
    417             return FORTY_FIVE;
    418         default:
    419             throw new AssertionError("Impossible atan arg");
    420         }
    421     }
    422 
    423     public static BoundedRational cos(BoundedRational r) {
    424         return map0to1(r);
    425     }
    426 
    427     public static BoundedRational degreeCos(BoundedRational r) {
    428         return degreeSin(add(r, NINETY));
    429     }
    430 
    431     public static BoundedRational acos(BoundedRational r) {
    432         checkAsinDomain(r);
    433         return map1to0(r);
    434     }
    435 
    436     public static BoundedRational degreeAcos(BoundedRational r) {
    437         final BoundedRational asin_r = degreeAsin(r);
    438         return subtract(NINETY, asin_r);
    439     }
    440 
    441     private static final BigInteger BIG_TWO = BigInteger.valueOf(2);
    442 
    443     /**
    444      * Compute an integral power of this.
    445      */
    446     private BoundedRational pow(BigInteger exp) {
    447         if (exp.signum() < 0) {
    448             return inverse(pow(exp.negate()));
    449         }
    450         if (exp.equals(BigInteger.ONE)) {
    451             return this;
    452         }
    453         if (exp.and(BigInteger.ONE).intValue() == 1) {
    454             return multiply(pow(exp.subtract(BigInteger.ONE)), this);
    455         }
    456         if (exp.signum() == 0) {
    457             return ONE;
    458         }
    459         BoundedRational tmp = pow(exp.shiftRight(1));
    460         if (Thread.interrupted()) {
    461             throw new CR.AbortedException();
    462         }
    463         return multiply(tmp, tmp);
    464     }
    465 
    466     public static BoundedRational pow(BoundedRational base, BoundedRational exp) {
    467         if (exp == null) {
    468             return null;
    469         }
    470         if (exp.mNum.signum() == 0) {
    471             // Questionable if base has undefined value.  Java.lang.Math.pow() returns 1 anyway,
    472             // so we do the same.
    473             return new BoundedRational(1);
    474         }
    475         if (base == null) {
    476             return null;
    477         }
    478         exp = exp.reduce().positiveDen();
    479         if (!exp.mDen.equals(BigInteger.ONE)) {
    480             return null;
    481         }
    482         return base.pow(exp.mNum);
    483     }
    484 
    485     public static BoundedRational ln(BoundedRational r) {
    486         if (r != null && r.signum() <= 0) {
    487             throw new ArithmeticException("log(non-positive)");
    488         }
    489         return map1to0(r);
    490     }
    491 
    492     public static BoundedRational exp(BoundedRational r) {
    493         return map0to1(r);
    494     }
    495 
    496     /**
    497      * Return the base 10 log of n, if n is a power of 10, -1 otherwise.
    498      * n must be positive.
    499      */
    500     private static long b10Log(BigInteger n) {
    501         // This algorithm is very naive, but we doubt it matters.
    502         long count = 0;
    503         while (n.mod(BigInteger.TEN).signum() == 0) {
    504             if (Thread.interrupted()) {
    505                 throw new CR.AbortedException();
    506             }
    507             n = n.divide(BigInteger.TEN);
    508             ++count;
    509         }
    510         if (n.equals(BigInteger.ONE)) {
    511             return count;
    512         }
    513         return -1;
    514     }
    515 
    516     public static BoundedRational log(BoundedRational r) {
    517         if (r == null) {
    518             return null;
    519         }
    520         if (r.signum() <= 0) {
    521             throw new ArithmeticException("log(non-positive)");
    522         }
    523         r = r.reduce().positiveDen();
    524         if (r == null) {
    525             return null;
    526         }
    527         if (r.mDen.equals(BigInteger.ONE)) {
    528             long log = b10Log(r.mNum);
    529             if (log != -1) {
    530                 return new BoundedRational(log);
    531             }
    532         } else if (r.mNum.equals(BigInteger.ONE)) {
    533             long log = b10Log(r.mDen);
    534             if (log != -1) {
    535                 return new BoundedRational(-log);
    536             }
    537         }
    538         return null;
    539     }
    540 
    541     /**
    542      * Generalized factorial.
    543      * Compute n * (n - step) * (n - 2 * step) * etc.  This can be used to compute factorial a bit
    544      * faster, especially if BigInteger uses sub-quadratic multiplication.
    545      */
    546     private static BigInteger genFactorial(long n, long step) {
    547         if (n > 4 * step) {
    548             BigInteger prod1 = genFactorial(n, 2 * step);
    549             if (Thread.interrupted()) {
    550                 throw new CR.AbortedException();
    551             }
    552             BigInteger prod2 = genFactorial(n - step, 2 * step);
    553             if (Thread.interrupted()) {
    554                 throw new CR.AbortedException();
    555             }
    556             return prod1.multiply(prod2);
    557         } else {
    558             if (n == 0) {
    559                 return BigInteger.ONE;
    560             }
    561             BigInteger res = BigInteger.valueOf(n);
    562             for (long i = n - step; i > 1; i -= step) {
    563                 res = res.multiply(BigInteger.valueOf(i));
    564             }
    565             return res;
    566         }
    567     }
    568 
    569     /**
    570      * Factorial function.
    571      * Always produces non-null (or exception) when called on non-null r.
    572      */
    573     public static BoundedRational fact(BoundedRational r) {
    574         if (r == null) {
    575             return null;
    576         }
    577         final BigInteger rAsInt = asBigInteger(r);
    578         if (rAsInt == null) {
    579             throw new ArithmeticException("Non-integral factorial argument");
    580         }
    581         if (rAsInt.signum() < 0) {
    582             throw new ArithmeticException("Negative factorial argument");
    583         }
    584         if (rAsInt.bitLength() > 30) {
    585             // Will fail.  LongValue() may not work. Punt now.
    586             throw new ArithmeticException("Factorial argument too big");
    587         }
    588         return new BoundedRational(genFactorial(rAsInt.longValue(), 1));
    589     }
    590 
    591     private static final BigInteger BIG_FIVE = BigInteger.valueOf(5);
    592     private static final BigInteger BIG_MINUS_ONE = BigInteger.valueOf(-1);
    593 
    594     /**
    595      * Return the number of decimal digits to the right of the decimal point required to represent
    596      * the argument exactly.
    597      * Return Integer.MAX_VALUE if that's not possible.  Never returns a value less than zero, even
    598      * if r is a power of ten.
    599      */
    600     static int digitsRequired(BoundedRational r) {
    601         if (r == null) {
    602             return Integer.MAX_VALUE;
    603         }
    604         int powersOfTwo = 0;  // Max power of 2 that divides denominator
    605         int powersOfFive = 0;  // Max power of 5 that divides denominator
    606         // Try the easy case first to speed things up.
    607         if (r.mDen.equals(BigInteger.ONE)) {
    608             return 0;
    609         }
    610         r = r.reduce();
    611         BigInteger den = r.mDen;
    612         if (den.bitLength() > MAX_SIZE) {
    613             return Integer.MAX_VALUE;
    614         }
    615         while (!den.testBit(0)) {
    616             ++powersOfTwo;
    617             den = den.shiftRight(1);
    618         }
    619         while (den.mod(BIG_FIVE).signum() == 0) {
    620             ++powersOfFive;
    621             den = den.divide(BIG_FIVE);
    622         }
    623         // If the denominator has a factor of other than 2 or 5 (the divisors of 10), the decimal
    624         // expansion does not terminate.  Multiplying the fraction by any number of powers of 10
    625         // will not cancel the demoniator.  (Recall the fraction was in lowest terms to start
    626         // with.) Otherwise the powers of 10 we need to cancel the denominator is the larger of
    627         // powersOfTwo and powersOfFive.
    628         if (!den.equals(BigInteger.ONE) && !den.equals(BIG_MINUS_ONE)) {
    629             return Integer.MAX_VALUE;
    630         }
    631         return Math.max(powersOfTwo, powersOfFive);
    632     }
    633 }
    634