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.Random; 23 24 /** 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 */ 34 public class BoundedRational { 35 // TODO: Consider returning null for integers. With some care, large factorials might become 36 // much faster. 37 // TODO: Maybe eventually make this extend Number? 38 39 private static final int MAX_SIZE = 10000; // total, in bits 40 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 64 /** 65 * Convert to String reflecting raw representation. 66 * Debug or log messages only, not pretty. 67 */ 68 public String toString() { 69 return mNum.toString() + "/" + mDen.toString(); 70 } 71 72 /** 73 * Convert to readable String. 74 * Intended for output to user. More expensive, less useful for debugging than 75 * toString(). Not internationalized. 76 */ 77 public String toNiceString() { 78 final BoundedRational nicer = reduce().positiveDen(); 79 String result = nicer.mNum.toString(); 80 if (!nicer.mDen.equals(BigInteger.ONE)) { 81 result += "/" + nicer.mDen; 82 } 83 return result; 84 } 85 86 public static String toString(BoundedRational r) { 87 if (r == null) { 88 return "not a small rational"; 89 } 90 return r.toString(); 91 } 92 93 /** 94 * 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 */ 98 public String toStringTruncated(int n) { 99 String digits = mNum.abs().multiply(BigInteger.TEN.pow(n)).divide(mDen.abs()).toString(); 100 int len = digits.length(); 101 if (len < n + 1) { 102 digits = StringUtils.repeat('0', n + 1 - len) + digits; 103 len = n + 1; 104 } 105 return (signum() < 0 ? "-" : "") + digits.substring(0, len - n) + "." 106 + digits.substring(len - n); 107 } 108 109 /** 110 * Return a double approximation. 111 * The result is correctly rounded if numerator and denominator are 112 * exactly representable as a double. 113 * TODO: This should always be correctly rounded. 114 */ 115 public double doubleValue() { 116 return mNum.doubleValue() / mDen.doubleValue(); 117 } 118 119 public CR crValue() { 120 return CR.valueOf(mNum).divide(CR.valueOf(mDen)); 121 } 122 123 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 131 // Approximate number of bits to left of binary point. 132 // Negative indicates leading zeroes to the right of binary point. 133 public int wholeNumberBits() { 134 if (mNum.signum() == 0) { 135 return Integer.MIN_VALUE; 136 } else { 137 return mNum.bitLength() - mDen.bitLength(); 138 } 139 } 140 141 private boolean tooBig() { 142 if (mDen.equals(BigInteger.ONE)) { 143 return false; 144 } 145 return (mNum.bitLength() + mDen.bitLength() > MAX_SIZE); 146 } 147 148 /** 149 * Return an equivalent fraction with a positive denominator. 150 */ 151 private BoundedRational positiveDen() { 152 if (mDen.signum() > 0) { 153 return this; 154 } 155 return new BoundedRational(mNum.negate(), mDen.negate()); 156 } 157 158 /** 159 * Return an equivalent fraction in lowest terms. 160 * Denominator sign may remain negative. 161 */ 162 private BoundedRational reduce() { 163 if (mDen.equals(BigInteger.ONE)) { 164 return this; // Optimization only 165 } 166 final BigInteger divisor = mNum.gcd(mDen); 167 return new BoundedRational(mNum.divide(divisor), mDen.divide(divisor)); 168 } 169 170 static Random sReduceRng = new Random(); 171 172 /** 173 * Return a possibly reduced version of r that's not tooBig(). 174 * Return null if none exists. 175 */ 176 private static BoundedRational maybeReduce(BoundedRational r) { 177 if (r == null) return null; 178 // Reduce randomly, with 1/16 probability, or if the result is too big. 179 if (!r.tooBig() && (sReduceRng.nextInt() & 0xf) != 0) { 180 return r; 181 } 182 BoundedRational result = r.positiveDen(); 183 result = result.reduce(); 184 if (!result.tooBig()) { 185 return result; 186 } 187 return null; 188 } 189 190 public int compareTo(BoundedRational r) { 191 // Compare by multiplying both sides by denominators, invert result if denominator product 192 // was negative. 193 return mNum.multiply(r.mDen).compareTo(r.mNum.multiply(mDen)) * mDen.signum() 194 * r.mDen.signum(); 195 } 196 197 public int signum() { 198 return mNum.signum() * mDen.signum(); 199 } 200 201 public boolean equals(BoundedRational r) { 202 return compareTo(r) == 0; 203 } 204 205 // We use static methods for arithmetic, so that we can easily handle the null case. We try 206 // to catch domain errors whenever possible, sometimes even when one of the arguments is null, 207 // but not relevant. 208 209 /** 210 * Returns equivalent BigInteger result if it exists, null if not. 211 */ 212 public static BigInteger asBigInteger(BoundedRational r) { 213 if (r == null) { 214 return null; 215 } 216 final BigInteger[] quotAndRem = r.mNum.divideAndRemainder(r.mDen); 217 if (quotAndRem[1].signum() == 0) { 218 return quotAndRem[0]; 219 } else { 220 return null; 221 } 222 } 223 public static BoundedRational add(BoundedRational r1, BoundedRational r2) { 224 if (r1 == null || r2 == null) { 225 return null; 226 } 227 final BigInteger den = r1.mDen.multiply(r2.mDen); 228 final BigInteger num = r1.mNum.multiply(r2.mDen).add(r2.mNum.multiply(r1.mDen)); 229 return maybeReduce(new BoundedRational(num,den)); 230 } 231 232 /** 233 * Return the argument, but with the opposite sign. 234 * Returns null only for a null argument. 235 */ 236 public static BoundedRational negate(BoundedRational r) { 237 if (r == null) { 238 return null; 239 } 240 return new BoundedRational(r.mNum.negate(), r.mDen); 241 } 242 243 public static BoundedRational subtract(BoundedRational r1, BoundedRational r2) { 244 return add(r1, negate(r2)); 245 } 246 247 /** 248 * Return product of r1 and r2 without reducing the result. 249 */ 250 private static BoundedRational rawMultiply(BoundedRational r1, BoundedRational r2) { 251 // It's tempting but marginally unsound to reduce 0 * null to 0. The null could represent 252 // an infinite value, for which we failed to throw an exception because it was too big. 253 if (r1 == null || r2 == null) { 254 return null; 255 } 256 // Optimize the case of our special ONE constant, since that's cheap and somewhat frequent. 257 if (r1 == ONE) { 258 return r2; 259 } 260 if (r2 == ONE) { 261 return r1; 262 } 263 final BigInteger num = r1.mNum.multiply(r2.mNum); 264 final BigInteger den = r1.mDen.multiply(r2.mDen); 265 return new BoundedRational(num,den); 266 } 267 268 public static BoundedRational multiply(BoundedRational r1, BoundedRational r2) { 269 return maybeReduce(rawMultiply(r1, r2)); 270 } 271 272 public static class ZeroDivisionException extends ArithmeticException { 273 public ZeroDivisionException() { 274 super("Division by zero"); 275 } 276 } 277 278 /** 279 * Return the reciprocal of r (or null if the argument was null). 280 */ 281 public static BoundedRational inverse(BoundedRational r) { 282 if (r == null) { 283 return null; 284 } 285 if (r.mNum.signum() == 0) { 286 throw new ZeroDivisionException(); 287 } 288 return new BoundedRational(r.mDen, r.mNum); 289 } 290 291 public static BoundedRational divide(BoundedRational r1, BoundedRational r2) { 292 return multiply(r1, inverse(r2)); 293 } 294 295 public static BoundedRational sqrt(BoundedRational r) { 296 // Return non-null if numerator and denominator are small perfect squares. 297 if (r == null) { 298 return null; 299 } 300 r = r.positiveDen().reduce(); 301 if (r.mNum.signum() < 0) { 302 throw new ArithmeticException("sqrt(negative)"); 303 } 304 final BigInteger num_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mNum.doubleValue()))); 305 if (!num_sqrt.multiply(num_sqrt).equals(r.mNum)) { 306 return null; 307 } 308 final BigInteger den_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mDen.doubleValue()))); 309 if (!den_sqrt.multiply(den_sqrt).equals(r.mDen)) { 310 return null; 311 } 312 return new BoundedRational(num_sqrt, den_sqrt); 313 } 314 315 public final static BoundedRational ZERO = new BoundedRational(0); 316 public final static BoundedRational HALF = new BoundedRational(1,2); 317 public final static BoundedRational MINUS_HALF = new BoundedRational(-1,2); 318 public final static BoundedRational THIRD = new BoundedRational(1,3); 319 public final static BoundedRational QUARTER = new BoundedRational(1,4); 320 public final static BoundedRational SIXTH = new BoundedRational(1,6); 321 public final static BoundedRational ONE = new BoundedRational(1); 322 public final static BoundedRational MINUS_ONE = new BoundedRational(-1); 323 public final static BoundedRational TWO = new BoundedRational(2); 324 public final static BoundedRational MINUS_TWO = new BoundedRational(-2); 325 public final static BoundedRational TEN = new BoundedRational(10); 326 public final static BoundedRational TWELVE = new BoundedRational(12); 327 public final static BoundedRational THIRTY = new BoundedRational(30); 328 public final static BoundedRational MINUS_THIRTY = new BoundedRational(-30); 329 public final static BoundedRational FORTY_FIVE = new BoundedRational(45); 330 public final static BoundedRational MINUS_FORTY_FIVE = new BoundedRational(-45); 331 public final static BoundedRational NINETY = new BoundedRational(90); 332 public final static BoundedRational MINUS_NINETY = new BoundedRational(-90); 333 334 private static final BigInteger BIG_TWO = BigInteger.valueOf(2); 335 336 /** 337 * Compute integral power of this, assuming this has been reduced and exp is >= 0. 338 */ 339 private BoundedRational rawPow(BigInteger exp) { 340 if (exp.equals(BigInteger.ONE)) { 341 return this; 342 } 343 if (exp.and(BigInteger.ONE).intValue() == 1) { 344 return rawMultiply(rawPow(exp.subtract(BigInteger.ONE)), this); 345 } 346 if (exp.signum() == 0) { 347 return ONE; 348 } 349 BoundedRational tmp = rawPow(exp.shiftRight(1)); 350 if (Thread.interrupted()) { 351 throw new CR.AbortedException(); 352 } 353 return rawMultiply(tmp, tmp); 354 } 355 356 /** 357 * Compute an integral power of this. 358 */ 359 public BoundedRational pow(BigInteger exp) { 360 if (exp.signum() < 0) { 361 return inverse(pow(exp.negate())); 362 } 363 if (exp.equals(BigInteger.ONE)) { 364 return this; 365 } 366 // Reducing once at the beginning means there's no point in reducing later. 367 return reduce().rawPow(exp); 368 } 369 370 public static BoundedRational pow(BoundedRational base, BoundedRational exp) { 371 if (exp == null) { 372 return null; 373 } 374 if (exp.mNum.signum() == 0) { 375 // Questionable if base has undefined value. Java.lang.Math.pow() returns 1 anyway, 376 // so we do the same. 377 return new BoundedRational(1); 378 } 379 if (base == null) { 380 return null; 381 } 382 exp = exp.reduce().positiveDen(); 383 if (!exp.mDen.equals(BigInteger.ONE)) { 384 return null; 385 } 386 return base.pow(exp.mNum); 387 } 388 389 390 private static final BigInteger BIG_FIVE = BigInteger.valueOf(5); 391 private static final BigInteger BIG_MINUS_ONE = BigInteger.valueOf(-1); 392 393 /** 394 * Return the number of decimal digits to the right of the decimal point required to represent 395 * the argument exactly. 396 * Return Integer.MAX_VALUE if that's not possible. Never returns a value less than zero, even 397 * if r is a power of ten. 398 */ 399 public static int digitsRequired(BoundedRational r) { 400 if (r == null) { 401 return Integer.MAX_VALUE; 402 } 403 int powersOfTwo = 0; // Max power of 2 that divides denominator 404 int powersOfFive = 0; // Max power of 5 that divides denominator 405 // Try the easy case first to speed things up. 406 if (r.mDen.equals(BigInteger.ONE)) { 407 return 0; 408 } 409 r = r.reduce(); 410 BigInteger den = r.mDen; 411 if (den.bitLength() > MAX_SIZE) { 412 return Integer.MAX_VALUE; 413 } 414 while (!den.testBit(0)) { 415 ++powersOfTwo; 416 den = den.shiftRight(1); 417 } 418 while (den.mod(BIG_FIVE).signum() == 0) { 419 ++powersOfFive; 420 den = den.divide(BIG_FIVE); 421 } 422 // If the denominator has a factor of other than 2 or 5 (the divisors of 10), the decimal 423 // expansion does not terminate. Multiplying the fraction by any number of powers of 10 424 // will not cancel the demoniator. (Recall the fraction was in lowest terms to start 425 // with.) Otherwise the powers of 10 we need to cancel the denominator is the larger of 426 // powersOfTwo and powersOfFive. 427 if (!den.equals(BigInteger.ONE) && !den.equals(BIG_MINUS_ONE)) { 428 return Integer.MAX_VALUE; 429 } 430 return Math.max(powersOfTwo, powersOfFive); 431 } 432 } 433
