blob: e9e6f05a6ca9a1fe5aefb0855c4fbaa3ece71c94 [file] [log] [blame]
Hans Boehm682ff5e2015-03-09 14:40:25 -07001/*
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
Hans Boehm682ff5e2015-03-09 14:40:25 -070017package com.android.calculator2;
18
Hans Boehm995e5eb2016-02-08 11:03:01 -080019import java.util.Random;
Hans Boehm682ff5e2015-03-09 14:40:25 -070020
21import java.math.BigInteger;
22import com.hp.creals.CR;
23
Hans Boehmf599db72015-08-10 16:19:24 -070024/**
25 * Rational numbers that may turn to null if they get too big.
26 * For many operations, if the length of the nuumerator plus the length of the denominator exceeds
27 * a maximum size, we simply return null, and rely on our caller do something else.
28 * We currently never return null for a pure integer or for a BoundedRational that has just been
29 * constructed.
30 *
31 * We also implement a number of irrational functions. These return a non-null result only when
32 * the result is known to be rational.
33 */
Hans Boehm682ff5e2015-03-09 14:40:25 -070034public class BoundedRational {
Hans Boehmf599db72015-08-10 16:19:24 -070035 // TODO: Consider returning null for integers. With some care, large factorials might become
36 // much faster.
Hans Boehm682ff5e2015-03-09 14:40:25 -070037 // TODO: Maybe eventually make this extend Number?
Hans Boehmf599db72015-08-10 16:19:24 -070038
Hans Boehm995e5eb2016-02-08 11:03:01 -080039 private static final int MAX_SIZE = 10000; // total, in bits
Hans Boehm682ff5e2015-03-09 14:40:25 -070040
41 private final BigInteger mNum;
42 private final BigInteger mDen;
43
44 public BoundedRational(BigInteger n, BigInteger d) {
45 mNum = n;
46 mDen = d;
47 }
48
49 public BoundedRational(BigInteger n) {
50 mNum = n;
51 mDen = BigInteger.ONE;
52 }
53
54 public BoundedRational(long n, long d) {
55 mNum = BigInteger.valueOf(n);
56 mDen = BigInteger.valueOf(d);
57 }
58
59 public BoundedRational(long n) {
60 mNum = BigInteger.valueOf(n);
61 mDen = BigInteger.valueOf(1);
62 }
63
Hans Boehmf599db72015-08-10 16:19:24 -070064 /**
65 * Convert to String reflecting raw representation.
66 * Debug or log messages only, not pretty.
67 */
Hans Boehm75ca21c2015-03-11 18:43:24 -070068 public String toString() {
69 return mNum.toString() + "/" + mDen.toString();
70 }
71
Hans Boehmf599db72015-08-10 16:19:24 -070072 /**
73 * Convert to readable String.
Hans Boehm65a99a42016-02-03 18:16:07 -080074 * Intended for output to user. More expensive, less useful for debugging than
Hans Boehmf599db72015-08-10 16:19:24 -070075 * toString(). Not internationalized.
76 */
Hans Boehm4a6b7cb2015-04-03 18:41:52 -070077 public String toNiceString() {
Hans Boehm65a99a42016-02-03 18:16:07 -080078 final BoundedRational nicer = reduce().positiveDen();
Hans Boehm4a6b7cb2015-04-03 18:41:52 -070079 String result = nicer.mNum.toString();
80 if (!nicer.mDen.equals(BigInteger.ONE)) {
81 result += "/" + nicer.mDen;
82 }
83 return result;
84 }
85
Hans Boehm682ff5e2015-03-09 14:40:25 -070086 public static String toString(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -070087 if (r == null) {
88 return "not a small rational";
89 }
Hans Boehm75ca21c2015-03-11 18:43:24 -070090 return r.toString();
Hans Boehm682ff5e2015-03-09 14:40:25 -070091 }
92
Hans Boehmf599db72015-08-10 16:19:24 -070093 /**
Hans Boehm65a99a42016-02-03 18:16:07 -080094 * Returns a truncated (rounded towards 0) representation of the result.
95 * Includes n digits to the right of the decimal point.
96 * @param n result precision, >= 0
97 */
Hans Boehm995e5eb2016-02-08 11:03:01 -080098 public String toStringTruncated(int n) {
Hans Boehm65a99a42016-02-03 18:16:07 -080099 String digits = mNum.abs().multiply(BigInteger.TEN.pow(n)).divide(mDen.abs()).toString();
100 int len = digits.length();
101 if (len < n + 1) {
Hans Boehm24c91ed2016-06-30 18:53:44 -0700102 digits = StringUtils.repeat('0', n + 1 - len) + digits;
Hans Boehm65a99a42016-02-03 18:16:07 -0800103 len = n + 1;
104 }
105 return (signum() < 0 ? "-" : "") + digits.substring(0, len - n) + "."
106 + digits.substring(len - n);
107 }
108
109 /**
Hans Boehmf599db72015-08-10 16:19:24 -0700110 * Return a double approximation.
Hans Boehm995e5eb2016-02-08 11:03:01 -0800111 * The result is correctly rounded if numerator and denominator are
112 * exactly representable as a double.
113 * TODO: This should always be correctly rounded.
Hans Boehmf599db72015-08-10 16:19:24 -0700114 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700115 public double doubleValue() {
116 return mNum.doubleValue() / mDen.doubleValue();
117 }
118
Hans Boehm995e5eb2016-02-08 11:03:01 -0800119 public CR crValue() {
Hans Boehm682ff5e2015-03-09 14:40:25 -0700120 return CR.valueOf(mNum).divide(CR.valueOf(mDen));
121 }
122
Hans Boehm995e5eb2016-02-08 11:03:01 -0800123 public int intValue() {
124 BoundedRational reduced = reduce();
125 if (!reduced.mDen.equals(BigInteger.ONE)) {
126 throw new ArithmeticException("intValue of non-int");
127 }
128 return reduced.mNum.intValue();
129 }
130
Hans Boehm82e5a2f2015-07-20 20:08:14 -0700131 // Approximate number of bits to left of binary point.
Hans Boehm995e5eb2016-02-08 11:03:01 -0800132 // Negative indicates leading zeroes to the right of binary point.
Hans Boehm82e5a2f2015-07-20 20:08:14 -0700133 public int wholeNumberBits() {
Hans Boehm995e5eb2016-02-08 11:03:01 -0800134 if (mNum.signum() == 0) {
135 return Integer.MIN_VALUE;
136 } else {
137 return mNum.bitLength() - mDen.bitLength();
138 }
Hans Boehm82e5a2f2015-07-20 20:08:14 -0700139 }
140
Hans Boehm682ff5e2015-03-09 14:40:25 -0700141 private boolean tooBig() {
Hans Boehmf599db72015-08-10 16:19:24 -0700142 if (mDen.equals(BigInteger.ONE)) {
143 return false;
144 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700145 return (mNum.bitLength() + mDen.bitLength() > MAX_SIZE);
146 }
147
Hans Boehmf599db72015-08-10 16:19:24 -0700148 /**
149 * Return an equivalent fraction with a positive denominator.
150 */
Hans Boehm9e855e82015-04-22 18:03:28 -0700151 private BoundedRational positiveDen() {
Hans Boehmf599db72015-08-10 16:19:24 -0700152 if (mDen.signum() > 0) {
153 return this;
154 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700155 return new BoundedRational(mNum.negate(), mDen.negate());
156 }
157
Hans Boehmf599db72015-08-10 16:19:24 -0700158 /**
159 * Return an equivalent fraction in lowest terms.
160 * Denominator sign may remain negative.
161 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700162 private BoundedRational reduce() {
Hans Boehmf599db72015-08-10 16:19:24 -0700163 if (mDen.equals(BigInteger.ONE)) {
164 return this; // Optimization only
165 }
166 final BigInteger divisor = mNum.gcd(mDen);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700167 return new BoundedRational(mNum.divide(divisor), mDen.divide(divisor));
168 }
169
Hans Boehm995e5eb2016-02-08 11:03:01 -0800170 static Random sReduceRng = new Random();
171
Hans Boehmf599db72015-08-10 16:19:24 -0700172 /**
173 * Return a possibly reduced version of this that's not tooBig().
174 * Return null if none exists.
175 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700176 private BoundedRational maybeReduce() {
Hans Boehm995e5eb2016-02-08 11:03:01 -0800177 // Reduce randomly, with 1/16 probability, or if the result is too big.
178 if (!tooBig() && (sReduceRng.nextInt() & 0xf) != 0) {
Hans Boehmf599db72015-08-10 16:19:24 -0700179 return this;
180 }
Hans Boehm9e855e82015-04-22 18:03:28 -0700181 BoundedRational result = positiveDen();
Hans Boehm682ff5e2015-03-09 14:40:25 -0700182 result = result.reduce();
Hans Boehmf599db72015-08-10 16:19:24 -0700183 if (!result.tooBig()) {
184 return this;
185 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700186 return null;
187 }
188
189 public int compareTo(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -0700190 // Compare by multiplying both sides by denominators, invert result if denominator product
191 // was negative.
192 return mNum.multiply(r.mDen).compareTo(r.mNum.multiply(mDen)) * mDen.signum()
193 * r.mDen.signum();
Hans Boehm682ff5e2015-03-09 14:40:25 -0700194 }
195
196 public int signum() {
Hans Boehm75ca21c2015-03-11 18:43:24 -0700197 return mNum.signum() * mDen.signum();
Hans Boehm682ff5e2015-03-09 14:40:25 -0700198 }
199
200 public boolean equals(BoundedRational r) {
201 return compareTo(r) == 0;
202 }
203
Hans Boehmf599db72015-08-10 16:19:24 -0700204 // We use static methods for arithmetic, so that we can easily handle the null case. We try
205 // to catch domain errors whenever possible, sometimes even when one of the arguments is null,
206 // but not relevant.
Hans Boehm682ff5e2015-03-09 14:40:25 -0700207
Hans Boehmf599db72015-08-10 16:19:24 -0700208 /**
209 * Returns equivalent BigInteger result if it exists, null if not.
210 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700211 public static BigInteger asBigInteger(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -0700212 if (r == null) {
213 return null;
214 }
215 final BigInteger[] quotAndRem = r.mNum.divideAndRemainder(r.mDen);
216 if (quotAndRem[1].signum() == 0) {
217 return quotAndRem[0];
218 } else {
219 return null;
220 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700221 }
222 public static BoundedRational add(BoundedRational r1, BoundedRational r2) {
Hans Boehmf599db72015-08-10 16:19:24 -0700223 if (r1 == null || r2 == null) {
224 return null;
225 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700226 final BigInteger den = r1.mDen.multiply(r2.mDen);
Hans Boehmf599db72015-08-10 16:19:24 -0700227 final BigInteger num = r1.mNum.multiply(r2.mDen).add(r2.mNum.multiply(r1.mDen));
Hans Boehm682ff5e2015-03-09 14:40:25 -0700228 return new BoundedRational(num,den).maybeReduce();
229 }
230
Hans Boehm995e5eb2016-02-08 11:03:01 -0800231 /**
232 * Return the argument, but with the opposite sign.
233 * Returns null only for a null argument.
234 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700235 public static BoundedRational negate(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -0700236 if (r == null) {
237 return null;
238 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700239 return new BoundedRational(r.mNum.negate(), r.mDen);
240 }
241
242 static BoundedRational subtract(BoundedRational r1, BoundedRational r2) {
243 return add(r1, negate(r2));
244 }
245
Hans Boehm995e5eb2016-02-08 11:03:01 -0800246 /**
247 * Return product of r1 and r2 without reducing the result.
248 */
249 private static BoundedRational rawMultiply(BoundedRational r1, BoundedRational r2) {
Hans Boehmf599db72015-08-10 16:19:24 -0700250 // It's tempting but marginally unsound to reduce 0 * null to 0. The null could represent
251 // an infinite value, for which we failed to throw an exception because it was too big.
252 if (r1 == null || r2 == null) {
253 return null;
254 }
Hans Boehm995e5eb2016-02-08 11:03:01 -0800255 // Optimize the case of our special ONE constant, since that's cheap and somewhat frequent.
256 if (r1 == ONE) {
257 return r2;
258 }
259 if (r2 == ONE) {
260 return r1;
261 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700262 final BigInteger num = r1.mNum.multiply(r2.mNum);
263 final BigInteger den = r1.mDen.multiply(r2.mDen);
Hans Boehm995e5eb2016-02-08 11:03:01 -0800264 return new BoundedRational(num,den);
265 }
266
267 static BoundedRational multiply(BoundedRational r1, BoundedRational r2) {
268 return rawMultiply(r1, r2).maybeReduce();
Hans Boehm682ff5e2015-03-09 14:40:25 -0700269 }
270
Hans Boehmfbcef702015-04-27 18:07:47 -0700271 public static class ZeroDivisionException extends ArithmeticException {
272 public ZeroDivisionException() {
273 super("Division by zero");
274 }
275 }
276
Hans Boehmf599db72015-08-10 16:19:24 -0700277 /**
Hans Boehm995e5eb2016-02-08 11:03:01 -0800278 * Return the reciprocal of r (or null if the argument was null).
Hans Boehmf599db72015-08-10 16:19:24 -0700279 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700280 static BoundedRational inverse(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -0700281 if (r == null) {
282 return null;
283 }
284 if (r.mNum.signum() == 0) {
Hans Boehmfbcef702015-04-27 18:07:47 -0700285 throw new ZeroDivisionException();
Hans Boehm682ff5e2015-03-09 14:40:25 -0700286 }
287 return new BoundedRational(r.mDen, r.mNum);
288 }
289
290 static BoundedRational divide(BoundedRational r1, BoundedRational r2) {
291 return multiply(r1, inverse(r2));
292 }
293
294 static BoundedRational sqrt(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -0700295 // Return non-null if numerator and denominator are small perfect squares.
296 if (r == null) {
297 return null;
298 }
Hans Boehm9e855e82015-04-22 18:03:28 -0700299 r = r.positiveDen().reduce();
Hans Boehmf599db72015-08-10 16:19:24 -0700300 if (r.mNum.signum() < 0) {
Hans Boehm682ff5e2015-03-09 14:40:25 -0700301 throw new ArithmeticException("sqrt(negative)");
302 }
Hans Boehmf599db72015-08-10 16:19:24 -0700303 final BigInteger num_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mNum.doubleValue())));
304 if (!num_sqrt.multiply(num_sqrt).equals(r.mNum)) {
305 return null;
306 }
307 final BigInteger den_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mDen.doubleValue())));
308 if (!den_sqrt.multiply(den_sqrt).equals(r.mDen)) {
309 return null;
310 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700311 return new BoundedRational(num_sqrt, den_sqrt);
312 }
313
314 public final static BoundedRational ZERO = new BoundedRational(0);
315 public final static BoundedRational HALF = new BoundedRational(1,2);
316 public final static BoundedRational MINUS_HALF = new BoundedRational(-1,2);
Hans Boehm995e5eb2016-02-08 11:03:01 -0800317 public final static BoundedRational THIRD = new BoundedRational(1,3);
318 public final static BoundedRational QUARTER = new BoundedRational(1,4);
319 public final static BoundedRational SIXTH = new BoundedRational(1,6);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700320 public final static BoundedRational ONE = new BoundedRational(1);
321 public final static BoundedRational MINUS_ONE = new BoundedRational(-1);
322 public final static BoundedRational TWO = new BoundedRational(2);
323 public final static BoundedRational MINUS_TWO = new BoundedRational(-2);
Hans Boehm995e5eb2016-02-08 11:03:01 -0800324 public final static BoundedRational TEN = new BoundedRational(10);
325 public final static BoundedRational TWELVE = new BoundedRational(12);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700326 public final static BoundedRational THIRTY = new BoundedRational(30);
327 public final static BoundedRational MINUS_THIRTY = new BoundedRational(-30);
328 public final static BoundedRational FORTY_FIVE = new BoundedRational(45);
Hans Boehmf599db72015-08-10 16:19:24 -0700329 public final static BoundedRational MINUS_FORTY_FIVE = new BoundedRational(-45);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700330 public final static BoundedRational NINETY = new BoundedRational(90);
331 public final static BoundedRational MINUS_NINETY = new BoundedRational(-90);
332
Hans Boehm682ff5e2015-03-09 14:40:25 -0700333 private static final BigInteger BIG_TWO = BigInteger.valueOf(2);
334
Hans Boehmf599db72015-08-10 16:19:24 -0700335 /**
Hans Boehm995e5eb2016-02-08 11:03:01 -0800336 * Compute integral power of this, assuming this has been reduced and exp is >= 0.
337 */
338 private BoundedRational rawPow(BigInteger exp) {
339 if (exp.equals(BigInteger.ONE)) {
340 return this;
341 }
342 if (exp.and(BigInteger.ONE).intValue() == 1) {
343 return rawMultiply(rawPow(exp.subtract(BigInteger.ONE)), this);
344 }
345 if (exp.signum() == 0) {
346 return ONE;
347 }
348 BoundedRational tmp = rawPow(exp.shiftRight(1));
349 if (Thread.interrupted()) {
350 throw new CR.AbortedException();
351 }
352 return rawMultiply(tmp, tmp);
353 }
354
355 /**
Hans Boehmf599db72015-08-10 16:19:24 -0700356 * Compute an integral power of this.
357 */
Hans Boehm995e5eb2016-02-08 11:03:01 -0800358 public BoundedRational pow(BigInteger exp) {
Hans Boehmf599db72015-08-10 16:19:24 -0700359 if (exp.signum() < 0) {
Hans Boehm682ff5e2015-03-09 14:40:25 -0700360 return inverse(pow(exp.negate()));
361 }
Hans Boehmf599db72015-08-10 16:19:24 -0700362 if (exp.equals(BigInteger.ONE)) {
363 return this;
364 }
Hans Boehm995e5eb2016-02-08 11:03:01 -0800365 // Reducing once at the beginning means there's no point in reducing later.
366 return reduce().rawPow(exp);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700367 }
368
369 public static BoundedRational pow(BoundedRational base, BoundedRational exp) {
Hans Boehmf599db72015-08-10 16:19:24 -0700370 if (exp == null) {
371 return null;
372 }
373 if (exp.mNum.signum() == 0) {
374 // Questionable if base has undefined value. Java.lang.Math.pow() returns 1 anyway,
375 // so we do the same.
Hans Boehm682ff5e2015-03-09 14:40:25 -0700376 return new BoundedRational(1);
377 }
Hans Boehmf599db72015-08-10 16:19:24 -0700378 if (base == null) {
379 return null;
380 }
Hans Boehm9e855e82015-04-22 18:03:28 -0700381 exp = exp.reduce().positiveDen();
Hans Boehmf599db72015-08-10 16:19:24 -0700382 if (!exp.mDen.equals(BigInteger.ONE)) {
383 return null;
384 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700385 return base.pow(exp.mNum);
386 }
387
Hans Boehm682ff5e2015-03-09 14:40:25 -0700388
389 private static final BigInteger BIG_FIVE = BigInteger.valueOf(5);
Hans Boehmcd740592015-06-13 21:12:23 -0700390 private static final BigInteger BIG_MINUS_ONE = BigInteger.valueOf(-1);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700391
Hans Boehmf599db72015-08-10 16:19:24 -0700392 /**
393 * Return the number of decimal digits to the right of the decimal point required to represent
394 * the argument exactly.
395 * Return Integer.MAX_VALUE if that's not possible. Never returns a value less than zero, even
396 * if r is a power of ten.
397 */
Hans Boehm682ff5e2015-03-09 14:40:25 -0700398 static int digitsRequired(BoundedRational r) {
Hans Boehmf599db72015-08-10 16:19:24 -0700399 if (r == null) {
400 return Integer.MAX_VALUE;
401 }
402 int powersOfTwo = 0; // Max power of 2 that divides denominator
403 int powersOfFive = 0; // Max power of 5 that divides denominator
Hans Boehm682ff5e2015-03-09 14:40:25 -0700404 // Try the easy case first to speed things up.
Hans Boehmf599db72015-08-10 16:19:24 -0700405 if (r.mDen.equals(BigInteger.ONE)) {
406 return 0;
407 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700408 r = r.reduce();
409 BigInteger den = r.mDen;
Hans Boehm82e5a2f2015-07-20 20:08:14 -0700410 if (den.bitLength() > MAX_SIZE) {
411 return Integer.MAX_VALUE;
412 }
Hans Boehm682ff5e2015-03-09 14:40:25 -0700413 while (!den.testBit(0)) {
Hans Boehmf599db72015-08-10 16:19:24 -0700414 ++powersOfTwo;
Hans Boehm682ff5e2015-03-09 14:40:25 -0700415 den = den.shiftRight(1);
416 }
Hans Boehmf599db72015-08-10 16:19:24 -0700417 while (den.mod(BIG_FIVE).signum() == 0) {
418 ++powersOfFive;
Hans Boehm682ff5e2015-03-09 14:40:25 -0700419 den = den.divide(BIG_FIVE);
420 }
Hans Boehmf599db72015-08-10 16:19:24 -0700421 // If the denominator has a factor of other than 2 or 5 (the divisors of 10), the decimal
422 // expansion does not terminate. Multiplying the fraction by any number of powers of 10
423 // will not cancel the demoniator. (Recall the fraction was in lowest terms to start
424 // with.) Otherwise the powers of 10 we need to cancel the denominator is the larger of
425 // powersOfTwo and powersOfFive.
Hans Boehmcd740592015-06-13 21:12:23 -0700426 if (!den.equals(BigInteger.ONE) && !den.equals(BIG_MINUS_ONE)) {
427 return Integer.MAX_VALUE;
428 }
Hans Boehmf599db72015-08-10 16:19:24 -0700429 return Math.max(powersOfTwo, powersOfFive);
Hans Boehm682ff5e2015-03-09 14:40:25 -0700430 }
431}