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