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 import com.hp.creals.CR; 20 21 import java.math.BigInteger; 22 import java.util.Objects; 23 import java.util.Random; 24 25 /** 26 * Rational numbers that may turn to null if they get too big. 27 * For many operations, if the length of the nuumerator plus the length of the denominator exceeds 28 * a maximum size, we simply return null, and rely on our caller do something else. 29 * We currently never return null for a pure integer or for a BoundedRational that has just been 30 * constructed. 31 * 32 * We also implement a number of irrational functions. These return a non-null result only when 33 * the result is known to be rational. 34 */ 35 public class BoundedRational { 36 // TODO: Consider returning null for integers. With some care, large factorials might become 37 // much faster. 38 // TODO: Maybe eventually make this extend Number? 39 40 private static final int MAX_SIZE = 10000; // total, in bits 41 42 private final BigInteger mNum; 43 private final BigInteger mDen; 44 45 public BoundedRational(BigInteger n, BigInteger d) { 46 mNum = n; 47 mDen = d; 48 } 49 50 public BoundedRational(BigInteger n) { 51 mNum = n; 52 mDen = BigInteger.ONE; 53 } 54 55 public BoundedRational(long n, long d) { 56 mNum = BigInteger.valueOf(n); 57 mDen = BigInteger.valueOf(d); 58 } 59 60 public BoundedRational(long n) { 61 mNum = BigInteger.valueOf(n); 62 mDen = BigInteger.valueOf(1); 63 } 64 65 /** 66 * Produce BoundedRational equal to the given double. 67 */ 68 public static BoundedRational valueOf(double x) { 69 final long l = Math.round(x); 70 if ((double) l == x && Math.abs(l) <= 1000) { 71 return valueOf(l); 72 } 73 final long allBits = Double.doubleToRawLongBits(Math.abs(x)); 74 long mantissa = (allBits & ((1L << 52) - 1)); 75 final int biased_exp = (int)(allBits >>> 52); 76 if ((biased_exp & 0x7ff) == 0x7ff) { 77 throw new ArithmeticException("Infinity or NaN not convertible to BoundedRational"); 78 } 79 final long sign = x < 0.0 ? -1 : 1; 80 int exp = biased_exp - 1075; // 1023 + 52; we treat mantissa as integer. 81 if (biased_exp == 0) { 82 exp += 1; // Denormal exponent is 1 greater. 83 } else { 84 mantissa += (1L << 52); // Implied leading one. 85 } 86 BigInteger num = BigInteger.valueOf(sign * mantissa); 87 BigInteger den = BigInteger.ONE; 88 if (exp >= 0) { 89 num = num.shiftLeft(exp); 90 } else { 91 den = den.shiftLeft(-exp); 92 } 93 return new BoundedRational(num, den); 94 } 95 96 /** 97 * Produce BoundedRational equal to the given long. 98 */ 99 public static BoundedRational valueOf(long x) { 100 if (x >= -2 && x <= 10) { 101 switch((int) x) { 102 case -2: 103 return MINUS_TWO; 104 case -1: 105 return MINUS_ONE; 106 case 0: 107 return ZERO; 108 case 1: 109 return ONE; 110 case 2: 111 return TWO; 112 case 10: 113 return TEN; 114 } 115 } 116 return new BoundedRational(x); 117 } 118 119 /** 120 * Convert to String reflecting raw representation. 121 * Debug or log messages only, not pretty. 122 */ 123 public String toString() { 124 return mNum.toString() + "/" + mDen.toString(); 125 } 126 127 /** 128 * Convert to readable String. 129 * Intended for output to user. More expensive, less useful for debugging than 130 * toString(). Not internationalized. 131 */ 132 public String toNiceString() { 133 final BoundedRational nicer = reduce().positiveDen(); 134 String result = nicer.mNum.toString(); 135 if (!nicer.mDen.equals(BigInteger.ONE)) { 136 result += "/" + nicer.mDen; 137 } 138 return result; 139 } 140 141 public static String toString(BoundedRational r) { 142 if (r == null) { 143 return "not a small rational"; 144 } 145 return r.toString(); 146 } 147 148 /** 149 * Returns a truncated (rounded towards 0) representation of the result. 150 * Includes n digits to the right of the decimal point. 151 * @param n result precision, >= 0 152 */ 153 public String toStringTruncated(int n) { 154 String digits = mNum.abs().multiply(BigInteger.TEN.pow(n)).divide(mDen.abs()).toString(); 155 int len = digits.length(); 156 if (len < n + 1) { 157 digits = StringUtils.repeat('0', n + 1 - len) + digits; 158 len = n + 1; 159 } 160 return (signum() < 0 ? "-" : "") + digits.substring(0, len - n) + "." 161 + digits.substring(len - n); 162 } 163 164 /** 165 * Return a double approximation. 166 * The result is correctly rounded to nearest, with ties rounded away from zero. 167 * TODO: Should round ties to even. 168 */ 169 public double doubleValue() { 170 final int sign = signum(); 171 if (sign < 0) { 172 return -BoundedRational.negate(this).doubleValue(); 173 } 174 // We get the mantissa by dividing the numerator by denominator, after 175 // suitably prescaling them so that the integral part of the result contains 176 // enough bits. We do the prescaling to avoid any precision loss, so the division result 177 // is correctly truncated towards zero. 178 final int apprExp = mNum.bitLength() - mDen.bitLength(); 179 if (apprExp < -1100 || sign == 0) { 180 // Bail fast for clearly zero result. 181 return 0.0; 182 } 183 final int neededPrec = apprExp - 80; 184 final BigInteger dividend = neededPrec < 0 ? mNum.shiftLeft(-neededPrec) : mNum; 185 final BigInteger divisor = neededPrec > 0 ? mDen.shiftLeft(neededPrec) : mDen; 186 final BigInteger quotient = dividend.divide(divisor); 187 final int qLength = quotient.bitLength(); 188 int extraBits = qLength - 53; 189 int exponent = neededPrec + qLength; // Exponent assuming leading binary point. 190 if (exponent >= -1021) { 191 // Binary point is actually to right of leading bit. 192 --exponent; 193 } else { 194 // We're in the gradual underflow range. Drop more bits. 195 extraBits += (-1022 - exponent) + 1; 196 exponent = -1023; 197 } 198 final BigInteger bigMantissa = 199 quotient.add(BigInteger.ONE.shiftLeft(extraBits - 1)).shiftRight(extraBits); 200 if (exponent > 1024) { 201 return Double.POSITIVE_INFINITY; 202 } 203 if (exponent > -1023 && bigMantissa.bitLength() != 53 204 || exponent <= -1023 && bigMantissa.bitLength() >= 53) { 205 throw new AssertionError("doubleValue internal error"); 206 } 207 final long mantissa = bigMantissa.longValue(); 208 final long bits = (mantissa & ((1l << 52) - 1)) | (((long) exponent + 1023) << 52); 209 return Double.longBitsToDouble(bits); 210 } 211 212 public CR crValue() { 213 return CR.valueOf(mNum).divide(CR.valueOf(mDen)); 214 } 215 216 public int intValue() { 217 BoundedRational reduced = reduce(); 218 if (!reduced.mDen.equals(BigInteger.ONE)) { 219 throw new ArithmeticException("intValue of non-int"); 220 } 221 return reduced.mNum.intValue(); 222 } 223 224 // Approximate number of bits to left of binary point. 225 // Negative indicates leading zeroes to the right of binary point. 226 public int wholeNumberBits() { 227 if (mNum.signum() == 0) { 228 return Integer.MIN_VALUE; 229 } else { 230 return mNum.bitLength() - mDen.bitLength(); 231 } 232 } 233 234 /** 235 * Is this number too big for us to continue with rational arithmetic? 236 * We return fals for integers on the assumption that we have no better fallback. 237 */ 238 private boolean tooBig() { 239 if (mDen.equals(BigInteger.ONE)) { 240 return false; 241 } 242 return (mNum.bitLength() + mDen.bitLength() > MAX_SIZE); 243 } 244 245 /** 246 * Return an equivalent fraction with a positive denominator. 247 */ 248 private BoundedRational positiveDen() { 249 if (mDen.signum() > 0) { 250 return this; 251 } 252 return new BoundedRational(mNum.negate(), mDen.negate()); 253 } 254 255 /** 256 * Return an equivalent fraction in lowest terms. 257 * Denominator sign may remain negative. 258 */ 259 private BoundedRational reduce() { 260 if (mDen.equals(BigInteger.ONE)) { 261 return this; // Optimization only 262 } 263 final BigInteger divisor = mNum.gcd(mDen); 264 return new BoundedRational(mNum.divide(divisor), mDen.divide(divisor)); 265 } 266 267 static Random sReduceRng = new Random(); 268 269 /** 270 * Return a possibly reduced version of r that's not tooBig(). 271 * Return null if none exists. 272 */ 273 private static BoundedRational maybeReduce(BoundedRational r) { 274 if (r == null) return null; 275 // Reduce randomly, with 1/16 probability, or if the result is too big. 276 if (!r.tooBig() && (sReduceRng.nextInt() & 0xf) != 0) { 277 return r; 278 } 279 BoundedRational result = r.positiveDen(); 280 result = result.reduce(); 281 if (!result.tooBig()) { 282 return result; 283 } 284 return null; 285 } 286 287 public int compareTo(BoundedRational r) { 288 // Compare by multiplying both sides by denominators, invert result if denominator product 289 // was negative. 290 return mNum.multiply(r.mDen).compareTo(r.mNum.multiply(mDen)) * mDen.signum() 291 * r.mDen.signum(); 292 } 293 294 public int signum() { 295 return mNum.signum() * mDen.signum(); 296 } 297 298 @Override 299 public int hashCode() { 300 // Note that this may be too expensive to be useful. 301 BoundedRational reduced = reduce().positiveDen(); 302 return Objects.hash(reduced.mNum, reduced.mDen); 303 } 304 305 @Override 306 public boolean equals(Object r) { 307 return r != null && r instanceof BoundedRational && compareTo((BoundedRational) r) == 0; 308 } 309 310 // We use static methods for arithmetic, so that we can easily handle the null case. We try 311 // to catch domain errors whenever possible, sometimes even when one of the arguments is null, 312 // but not relevant. 313 314 /** 315 * Returns equivalent BigInteger result if it exists, null if not. 316 */ 317 public static BigInteger asBigInteger(BoundedRational r) { 318 if (r == null) { 319 return null; 320 } 321 final BigInteger[] quotAndRem = r.mNum.divideAndRemainder(r.mDen); 322 if (quotAndRem[1].signum() == 0) { 323 return quotAndRem[0]; 324 } else { 325 return null; 326 } 327 } 328 public static BoundedRational add(BoundedRational r1, BoundedRational r2) { 329 if (r1 == null || r2 == null) { 330 return null; 331 } 332 final BigInteger den = r1.mDen.multiply(r2.mDen); 333 final BigInteger num = r1.mNum.multiply(r2.mDen).add(r2.mNum.multiply(r1.mDen)); 334 return maybeReduce(new BoundedRational(num,den)); 335 } 336 337 /** 338 * Return the argument, but with the opposite sign. 339 * Returns null only for a null argument. 340 */ 341 public static BoundedRational negate(BoundedRational r) { 342 if (r == null) { 343 return null; 344 } 345 return new BoundedRational(r.mNum.negate(), r.mDen); 346 } 347 348 public static BoundedRational subtract(BoundedRational r1, BoundedRational r2) { 349 return add(r1, negate(r2)); 350 } 351 352 /** 353 * Return product of r1 and r2 without reducing the result. 354 */ 355 private static BoundedRational rawMultiply(BoundedRational r1, BoundedRational r2) { 356 // It's tempting but marginally unsound to reduce 0 * null to 0. The null could represent 357 // an infinite value, for which we failed to throw an exception because it was too big. 358 if (r1 == null || r2 == null) { 359 return null; 360 } 361 // Optimize the case of our special ONE constant, since that's cheap and somewhat frequent. 362 if (r1 == ONE) { 363 return r2; 364 } 365 if (r2 == ONE) { 366 return r1; 367 } 368 final BigInteger num = r1.mNum.multiply(r2.mNum); 369 final BigInteger den = r1.mDen.multiply(r2.mDen); 370 return new BoundedRational(num,den); 371 } 372 373 public static BoundedRational multiply(BoundedRational r1, BoundedRational r2) { 374 return maybeReduce(rawMultiply(r1, r2)); 375 } 376 377 public static class ZeroDivisionException extends ArithmeticException { 378 public ZeroDivisionException() { 379 super("Division by zero"); 380 } 381 } 382 383 /** 384 * Return the reciprocal of r (or null if the argument was null). 385 */ 386 public static BoundedRational inverse(BoundedRational r) { 387 if (r == null) { 388 return null; 389 } 390 if (r.mNum.signum() == 0) { 391 throw new ZeroDivisionException(); 392 } 393 return new BoundedRational(r.mDen, r.mNum); 394 } 395 396 public static BoundedRational divide(BoundedRational r1, BoundedRational r2) { 397 return multiply(r1, inverse(r2)); 398 } 399 400 public static BoundedRational sqrt(BoundedRational r) { 401 // Return non-null if numerator and denominator are small perfect squares. 402 if (r == null) { 403 return null; 404 } 405 r = r.positiveDen().reduce(); 406 if (r.mNum.signum() < 0) { 407 throw new ArithmeticException("sqrt(negative)"); 408 } 409 final BigInteger num_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mNum.doubleValue()))); 410 if (!num_sqrt.multiply(num_sqrt).equals(r.mNum)) { 411 return null; 412 } 413 final BigInteger den_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mDen.doubleValue()))); 414 if (!den_sqrt.multiply(den_sqrt).equals(r.mDen)) { 415 return null; 416 } 417 return new BoundedRational(num_sqrt, den_sqrt); 418 } 419 420 public final static BoundedRational ZERO = new BoundedRational(0); 421 public final static BoundedRational HALF = new BoundedRational(1,2); 422 public final static BoundedRational MINUS_HALF = new BoundedRational(-1,2); 423 public final static BoundedRational THIRD = new BoundedRational(1,3); 424 public final static BoundedRational QUARTER = new BoundedRational(1,4); 425 public final static BoundedRational SIXTH = new BoundedRational(1,6); 426 public final static BoundedRational ONE = new BoundedRational(1); 427 public final static BoundedRational MINUS_ONE = new BoundedRational(-1); 428 public final static BoundedRational TWO = new BoundedRational(2); 429 public final static BoundedRational MINUS_TWO = new BoundedRational(-2); 430 public final static BoundedRational TEN = new BoundedRational(10); 431 public final static BoundedRational TWELVE = new BoundedRational(12); 432 public final static BoundedRational THIRTY = new BoundedRational(30); 433 public final static BoundedRational MINUS_THIRTY = new BoundedRational(-30); 434 public final static BoundedRational FORTY_FIVE = new BoundedRational(45); 435 public final static BoundedRational MINUS_FORTY_FIVE = new BoundedRational(-45); 436 public final static BoundedRational NINETY = new BoundedRational(90); 437 public final static BoundedRational MINUS_NINETY = new BoundedRational(-90); 438 439 private static final BigInteger BIG_TWO = BigInteger.valueOf(2); 440 private static final BigInteger BIG_MINUS_ONE = BigInteger.valueOf(-1); 441 442 /** 443 * Compute integral power of this, assuming this has been reduced and exp is >= 0. 444 */ 445 private BoundedRational rawPow(BigInteger exp) { 446 if (exp.equals(BigInteger.ONE)) { 447 return this; 448 } 449 if (exp.and(BigInteger.ONE).intValue() == 1) { 450 return rawMultiply(rawPow(exp.subtract(BigInteger.ONE)), this); 451 } 452 if (exp.signum() == 0) { 453 return ONE; 454 } 455 BoundedRational tmp = rawPow(exp.shiftRight(1)); 456 if (Thread.interrupted()) { 457 throw new CR.AbortedException(); 458 } 459 BoundedRational result = rawMultiply(tmp, tmp); 460 if (result == null || result.tooBig()) { 461 return null; 462 } 463 return result; 464 } 465 466 /** 467 * Compute an integral power of this. 468 */ 469 public BoundedRational pow(BigInteger exp) { 470 int expSign = exp.signum(); 471 if (expSign == 0) { 472 // Questionable if base has undefined or zero value. 473 // java.lang.Math.pow() returns 1 anyway, so we do the same. 474 return BoundedRational.ONE; 475 } 476 if (exp.equals(BigInteger.ONE)) { 477 return this; 478 } 479 // Reducing once at the beginning means there's no point in reducing later. 480 BoundedRational reduced = reduce().positiveDen(); 481 // First handle cases in which huge exponents could give compact results. 482 if (reduced.mDen.equals(BigInteger.ONE)) { 483 if (reduced.mNum.equals(BigInteger.ZERO)) { 484 return ZERO; 485 } 486 if (reduced.mNum.equals(BigInteger.ONE)) { 487 return ONE; 488 } 489 if (reduced.mNum.equals(BIG_MINUS_ONE)) { 490 if (exp.testBit(0)) { 491 return MINUS_ONE; 492 } else { 493 return ONE; 494 } 495 } 496 } 497 if (exp.bitLength() > 1000) { 498 // Stack overflow is likely; a useful rational result is not. 499 return null; 500 } 501 if (expSign < 0) { 502 return inverse(reduced).rawPow(exp.negate()); 503 } else { 504 return reduced.rawPow(exp); 505 } 506 } 507 508 public static BoundedRational pow(BoundedRational base, BoundedRational exp) { 509 if (exp == null) { 510 return null; 511 } 512 if (base == null) { 513 return null; 514 } 515 exp = exp.reduce().positiveDen(); 516 if (!exp.mDen.equals(BigInteger.ONE)) { 517 return null; 518 } 519 return base.pow(exp.mNum); 520 } 521 522 523 private static final BigInteger BIG_FIVE = BigInteger.valueOf(5); 524 525 /** 526 * Return the number of decimal digits to the right of the decimal point required to represent 527 * the argument exactly. 528 * Return Integer.MAX_VALUE if that's not possible. Never returns a value less than zero, even 529 * if r is a power of ten. 530 */ 531 public static int digitsRequired(BoundedRational r) { 532 if (r == null) { 533 return Integer.MAX_VALUE; 534 } 535 int powersOfTwo = 0; // Max power of 2 that divides denominator 536 int powersOfFive = 0; // Max power of 5 that divides denominator 537 // Try the easy case first to speed things up. 538 if (r.mDen.equals(BigInteger.ONE)) { 539 return 0; 540 } 541 r = r.reduce(); 542 BigInteger den = r.mDen; 543 if (den.bitLength() > MAX_SIZE) { 544 return Integer.MAX_VALUE; 545 } 546 while (!den.testBit(0)) { 547 ++powersOfTwo; 548 den = den.shiftRight(1); 549 } 550 while (den.mod(BIG_FIVE).signum() == 0) { 551 ++powersOfFive; 552 den = den.divide(BIG_FIVE); 553 } 554 // If the denominator has a factor of other than 2 or 5 (the divisors of 10), the decimal 555 // expansion does not terminate. Multiplying the fraction by any number of powers of 10 556 // will not cancel the demoniator. (Recall the fraction was in lowest terms to start 557 // with.) Otherwise the powers of 10 we need to cancel the denominator is the larger of 558 // powersOfTwo and powersOfFive. 559 if (!den.equals(BigInteger.ONE) && !den.equals(BIG_MINUS_ONE)) { 560 return Integer.MAX_VALUE; 561 } 562 return Math.max(powersOfTwo, powersOfFive); 563 } 564 } 565
