summaryrefslogtreecommitdiffstats
path: root/src/com/android/calculator2/BoundedRational.java
blob: 2b3d1ed40fa550ebd387ea84e2426ef0e14bb418 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
/*
 * 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.
 */

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 = 800; // 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 String toString() {
        return mNum.toString() + "/" + mDen.toString();
    }

    // Output to user, more expensive, less useful for debugging
    // Not internationalized.
    public String toNiceString() {
        BoundedRational nicer = reduce().positiveDen();
        String result = nicer.mNum.toString();
        if (!nicer.mDen.equals(BigInteger.ONE)) {
            result += "/" + nicer.mDen;
        }
        return result;
    }

    public static String toString(BoundedRational r) {
        if (r == null) return "not a small rational";
        return r.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));
    }

    // Approximate number of bits to left of binary point.
    public int wholeNumberBits() {
        return mNum.bitLength() - mDen.bitLength();
    }

    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 positiveDen() {
        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 = positiveDen();
        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 mNum.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();
    }

    public static class ZeroDivisionException extends ArithmeticException {
        public ZeroDivisionException() {
            super("Division by zero");
        }
    }

    static BoundedRational inverse(BoundedRational r) {
        if (r == null) return null;
        if (r.mNum.equals(BigInteger.ZERO)) {
            throw new ZeroDivisionException();
        }
        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.positiveDen().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 (!den_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 map0to1(BoundedRational r) {
        if (r == null) return null;
        if (r.mNum.equals(BigInteger.ZERO)) {
            return ONE;
        }
        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) {
        return map0to1(r);
    }

    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));
        if (Thread.interrupted()) {
            throw new CR.AbortedException();
        }
        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().positiveDen();
        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(non-positive)");
        }
        return map1to0(r);
    }

    public static BoundedRational exp(BoundedRational r) {
        return map0to1(r);
    }

    // Return the base 10 log of n, if n is a power of 10, -1 otherwise.
    // n must be positive.
    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)) {
            if (Thread.interrupted()) {
                throw new CR.AbortedException();
            }
            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(non-positive)");
        }
        r = r.reduce().positiveDen();
        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);
            if (Thread.interrupted()) {
                throw new CR.AbortedException();
            }
            BigInteger prod2 = genFactorial(n - step, 2 * step);
            if (Thread.interrupted()) {
                throw new CR.AbortedException();
            }
            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);
    private static final BigInteger BIG_MINUS_ONE = BigInteger.valueOf(-1);

    // 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;
        if (den.bitLength() > MAX_SIZE) {
            return Integer.MAX_VALUE;
        }
        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) && !den.equals(BIG_MINUS_ONE)) {
            return Integer.MAX_VALUE;
        }
        return Math.max(powers_of_two, powers_of_five);
    }
}