1682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm/* 2682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * Copyright (C) 2015 The Android Open Source Project 3682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * 4682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * Licensed under the Apache License, Version 2.0 (the "License"); 5682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * you may not use this file except in compliance with the License. 6682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * You may obtain a copy of the License at 7682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * 8682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * http://www.apache.org/licenses/LICENSE-2.0 9682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * 10682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * Unless required by applicable law or agreed to in writing, software 11682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * distributed under the License is distributed on an "AS IS" BASIS, 12682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * See the License for the specific language governing permissions and 14682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm * limitations under the License. 15682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm */ 16682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 17682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehmpackage com.android.calculator2; 18682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 1956bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chinimport com.hp.creals.CR; 20682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 21682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehmimport java.math.BigInteger; 2256bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chinimport java.util.Random; 23682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 24f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm/** 25f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Rational numbers that may turn to null if they get too big. 26f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * For many operations, if the length of the nuumerator plus the length of the denominator exceeds 27f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * a maximum size, we simply return null, and rely on our caller do something else. 28f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * We currently never return null for a pure integer or for a BoundedRational that has just been 29f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * constructed. 30f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * 31f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * We also implement a number of irrational functions. These return a non-null result only when 32f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * the result is known to be rational. 33f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 34682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehmpublic class BoundedRational { 35f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // TODO: Consider returning null for integers. With some care, large factorials might become 36f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // much faster. 37682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm // TODO: Maybe eventually make this extend Number? 38f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm 39995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm private static final int MAX_SIZE = 10000; // total, in bits 40682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 41682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm private final BigInteger mNum; 42682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm private final BigInteger mDen; 43682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 44682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public BoundedRational(BigInteger n, BigInteger d) { 45682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mNum = n; 46682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mDen = d; 47682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 48682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 49682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public BoundedRational(BigInteger n) { 50682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mNum = n; 51682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mDen = BigInteger.ONE; 52682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 53682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 54682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public BoundedRational(long n, long d) { 55682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mNum = BigInteger.valueOf(n); 56682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mDen = BigInteger.valueOf(d); 57682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 58682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 59682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public BoundedRational(long n) { 60682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mNum = BigInteger.valueOf(n); 61682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm mDen = BigInteger.valueOf(1); 62682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 63682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 64f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 65f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Convert to String reflecting raw representation. 66f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Debug or log messages only, not pretty. 67f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 6875ca21c698808b61238a3aff3e0a3dfd5ba95d0eHans Boehm public String toString() { 6975ca21c698808b61238a3aff3e0a3dfd5ba95d0eHans Boehm return mNum.toString() + "/" + mDen.toString(); 7075ca21c698808b61238a3aff3e0a3dfd5ba95d0eHans Boehm } 7175ca21c698808b61238a3aff3e0a3dfd5ba95d0eHans Boehm 72f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 73f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Convert to readable String. 7465a99a423182145394f96d1430e1196ae3db1663Hans Boehm * Intended for output to user. More expensive, less useful for debugging than 75f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * toString(). Not internationalized. 76f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 774a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm public String toNiceString() { 7865a99a423182145394f96d1430e1196ae3db1663Hans Boehm final BoundedRational nicer = reduce().positiveDen(); 794a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm String result = nicer.mNum.toString(); 804a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm if (!nicer.mDen.equals(BigInteger.ONE)) { 814a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm result += "/" + nicer.mDen; 824a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm } 834a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm return result; 844a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm } 854a6b7cb235c305761af5d7f40e74d4704e5058c8Hans Boehm 86682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public static String toString(BoundedRational r) { 87f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r == null) { 88f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return "not a small rational"; 89f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 9075ca21c698808b61238a3aff3e0a3dfd5ba95d0eHans Boehm return r.toString(); 91682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 92682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 93f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 9465a99a423182145394f96d1430e1196ae3db1663Hans Boehm * Returns a truncated (rounded towards 0) representation of the result. 9565a99a423182145394f96d1430e1196ae3db1663Hans Boehm * Includes n digits to the right of the decimal point. 9665a99a423182145394f96d1430e1196ae3db1663Hans Boehm * @param n result precision, >= 0 9765a99a423182145394f96d1430e1196ae3db1663Hans Boehm */ 98995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public String toStringTruncated(int n) { 9965a99a423182145394f96d1430e1196ae3db1663Hans Boehm String digits = mNum.abs().multiply(BigInteger.TEN.pow(n)).divide(mDen.abs()).toString(); 10065a99a423182145394f96d1430e1196ae3db1663Hans Boehm int len = digits.length(); 10165a99a423182145394f96d1430e1196ae3db1663Hans Boehm if (len < n + 1) { 10224c91edb89b3bfecb5167d3ba4f76cf0203cb547Hans Boehm digits = StringUtils.repeat('0', n + 1 - len) + digits; 10365a99a423182145394f96d1430e1196ae3db1663Hans Boehm len = n + 1; 10465a99a423182145394f96d1430e1196ae3db1663Hans Boehm } 10565a99a423182145394f96d1430e1196ae3db1663Hans Boehm return (signum() < 0 ? "-" : "") + digits.substring(0, len - n) + "." 10665a99a423182145394f96d1430e1196ae3db1663Hans Boehm + digits.substring(len - n); 10765a99a423182145394f96d1430e1196ae3db1663Hans Boehm } 10865a99a423182145394f96d1430e1196ae3db1663Hans Boehm 10965a99a423182145394f96d1430e1196ae3db1663Hans Boehm /** 110f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Return a double approximation. 111995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * The result is correctly rounded if numerator and denominator are 112995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * exactly representable as a double. 113995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * TODO: This should always be correctly rounded. 114f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 115682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public double doubleValue() { 116682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return mNum.doubleValue() / mDen.doubleValue(); 117682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 118682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 119995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public CR crValue() { 120682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return CR.valueOf(mNum).divide(CR.valueOf(mDen)); 121682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 122682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 123995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public int intValue() { 124995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm BoundedRational reduced = reduce(); 125995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (!reduced.mDen.equals(BigInteger.ONE)) { 126995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm throw new ArithmeticException("intValue of non-int"); 127995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } 128995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return reduced.mNum.intValue(); 129995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } 130995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm 13182e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm // Approximate number of bits to left of binary point. 132995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm // Negative indicates leading zeroes to the right of binary point. 13382e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm public int wholeNumberBits() { 134995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (mNum.signum() == 0) { 135995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return Integer.MIN_VALUE; 136995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } else { 137995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return mNum.bitLength() - mDen.bitLength(); 138995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } 13982e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm } 14082e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm 141682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm private boolean tooBig() { 142f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (mDen.equals(BigInteger.ONE)) { 143f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return false; 144f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 145682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return (mNum.bitLength() + mDen.bitLength() > MAX_SIZE); 146682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 147682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 148f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 149f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Return an equivalent fraction with a positive denominator. 150f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 1519e855e82dc86b3038b3e048a56be77af114e24f4Hans Boehm private BoundedRational positiveDen() { 152f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (mDen.signum() > 0) { 153f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return this; 154f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 155682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return new BoundedRational(mNum.negate(), mDen.negate()); 156682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 157682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 158f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 159f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Return an equivalent fraction in lowest terms. 160f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Denominator sign may remain negative. 161f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 162682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm private BoundedRational reduce() { 163f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (mDen.equals(BigInteger.ONE)) { 164f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return this; // Optimization only 165f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 166f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm final BigInteger divisor = mNum.gcd(mDen); 167682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return new BoundedRational(mNum.divide(divisor), mDen.divide(divisor)); 168682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 169682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 170995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm static Random sReduceRng = new Random(); 171995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm 172f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 1732ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm * Return a possibly reduced version of r that's not tooBig(). 174f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Return null if none exists. 175f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 1762ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm private static BoundedRational maybeReduce(BoundedRational r) { 1772ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm if (r == null) return null; 178995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm // Reduce randomly, with 1/16 probability, or if the result is too big. 1792ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm if (!r.tooBig() && (sReduceRng.nextInt() & 0xf) != 0) { 1802ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm return r; 181f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 1822ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm BoundedRational result = r.positiveDen(); 183682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm result = result.reduce(); 184f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (!result.tooBig()) { 1852ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm return result; 186f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 187682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return null; 188682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 189682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 190682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public int compareTo(BoundedRational r) { 191f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // Compare by multiplying both sides by denominators, invert result if denominator product 192f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // was negative. 193f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return mNum.multiply(r.mDen).compareTo(r.mNum.multiply(mDen)) * mDen.signum() 194f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * r.mDen.signum(); 195682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 196682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 197682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public int signum() { 19875ca21c698808b61238a3aff3e0a3dfd5ba95d0eHans Boehm return mNum.signum() * mDen.signum(); 199682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 200682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 201682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public boolean equals(BoundedRational r) { 202682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return compareTo(r) == 0; 203682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 204682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 205f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // We use static methods for arithmetic, so that we can easily handle the null case. We try 206f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // to catch domain errors whenever possible, sometimes even when one of the arguments is null, 207f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // but not relevant. 208682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 209f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 210f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Returns equivalent BigInteger result if it exists, null if not. 211f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 212682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public static BigInteger asBigInteger(BoundedRational r) { 213f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r == null) { 214f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 215f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 216f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm final BigInteger[] quotAndRem = r.mNum.divideAndRemainder(r.mDen); 217f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (quotAndRem[1].signum() == 0) { 218f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return quotAndRem[0]; 219f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } else { 220f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 221f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 222682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 223682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public static BoundedRational add(BoundedRational r1, BoundedRational r2) { 224f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r1 == null || r2 == null) { 225f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 226f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 227682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm final BigInteger den = r1.mDen.multiply(r2.mDen); 228f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm final BigInteger num = r1.mNum.multiply(r2.mDen).add(r2.mNum.multiply(r1.mDen)); 2292ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm return maybeReduce(new BoundedRational(num,den)); 230682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 231682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 232995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm /** 233995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * Return the argument, but with the opposite sign. 234995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * Returns null only for a null argument. 235995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm */ 236682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public static BoundedRational negate(BoundedRational r) { 237f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r == null) { 238f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 239f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 240682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return new BoundedRational(r.mNum.negate(), r.mDen); 241682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 242682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 24356bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chin public static BoundedRational subtract(BoundedRational r1, BoundedRational r2) { 244682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return add(r1, negate(r2)); 245682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 246682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 247995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm /** 248995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * Return product of r1 and r2 without reducing the result. 249995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm */ 250995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm private static BoundedRational rawMultiply(BoundedRational r1, BoundedRational r2) { 251f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // It's tempting but marginally unsound to reduce 0 * null to 0. The null could represent 252f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // an infinite value, for which we failed to throw an exception because it was too big. 253f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r1 == null || r2 == null) { 254f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 255f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 256995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm // Optimize the case of our special ONE constant, since that's cheap and somewhat frequent. 257995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (r1 == ONE) { 258995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return r2; 259995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } 260995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (r2 == ONE) { 261995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return r1; 262995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } 263682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm final BigInteger num = r1.mNum.multiply(r2.mNum); 264682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm final BigInteger den = r1.mDen.multiply(r2.mDen); 265995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return new BoundedRational(num,den); 266995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm } 267995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm 26856bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chin public static BoundedRational multiply(BoundedRational r1, BoundedRational r2) { 2692ca183cd5d5b1b4d7ef8b76ea8b9f965dab7e1ffHans Boehm return maybeReduce(rawMultiply(r1, r2)); 270682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 271682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 272fbcef7005de4436682072927f83000b502928d25Hans Boehm public static class ZeroDivisionException extends ArithmeticException { 273fbcef7005de4436682072927f83000b502928d25Hans Boehm public ZeroDivisionException() { 274fbcef7005de4436682072927f83000b502928d25Hans Boehm super("Division by zero"); 275fbcef7005de4436682072927f83000b502928d25Hans Boehm } 276fbcef7005de4436682072927f83000b502928d25Hans Boehm } 277fbcef7005de4436682072927f83000b502928d25Hans Boehm 278f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 279995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * Return the reciprocal of r (or null if the argument was null). 280f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 28156bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chin public static BoundedRational inverse(BoundedRational r) { 282f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r == null) { 283f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 284f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 285f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r.mNum.signum() == 0) { 286fbcef7005de4436682072927f83000b502928d25Hans Boehm throw new ZeroDivisionException(); 287682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 288682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return new BoundedRational(r.mDen, r.mNum); 289682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 290682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 29156bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chin public static BoundedRational divide(BoundedRational r1, BoundedRational r2) { 292682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return multiply(r1, inverse(r2)); 293682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 294682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 29556bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chin public static BoundedRational sqrt(BoundedRational r) { 296f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // Return non-null if numerator and denominator are small perfect squares. 297f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r == null) { 298f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 299f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 3009e855e82dc86b3038b3e048a56be77af114e24f4Hans Boehm r = r.positiveDen().reduce(); 301f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r.mNum.signum() < 0) { 302682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm throw new ArithmeticException("sqrt(negative)"); 303682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 304f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm final BigInteger num_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mNum.doubleValue()))); 305f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (!num_sqrt.multiply(num_sqrt).equals(r.mNum)) { 306f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 307f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 308f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm final BigInteger den_sqrt = BigInteger.valueOf(Math.round(Math.sqrt(r.mDen.doubleValue()))); 309f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (!den_sqrt.multiply(den_sqrt).equals(r.mDen)) { 310f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 311f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 312682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return new BoundedRational(num_sqrt, den_sqrt); 313682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 314682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 315682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational ZERO = new BoundedRational(0); 316682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational HALF = new BoundedRational(1,2); 317682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational MINUS_HALF = new BoundedRational(-1,2); 318995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public final static BoundedRational THIRD = new BoundedRational(1,3); 319995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public final static BoundedRational QUARTER = new BoundedRational(1,4); 320995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public final static BoundedRational SIXTH = new BoundedRational(1,6); 321682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational ONE = new BoundedRational(1); 322682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational MINUS_ONE = new BoundedRational(-1); 323682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational TWO = new BoundedRational(2); 324682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational MINUS_TWO = new BoundedRational(-2); 325995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public final static BoundedRational TEN = new BoundedRational(10); 326995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public final static BoundedRational TWELVE = new BoundedRational(12); 327682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational THIRTY = new BoundedRational(30); 328682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational MINUS_THIRTY = new BoundedRational(-30); 329682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational FORTY_FIVE = new BoundedRational(45); 330f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm public final static BoundedRational MINUS_FORTY_FIVE = new BoundedRational(-45); 331682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational NINETY = new BoundedRational(90); 332682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public final static BoundedRational MINUS_NINETY = new BoundedRational(-90); 333682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 334995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm private static final BigInteger BIG_TWO = BigInteger.valueOf(2); 335682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 336995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm /** 337995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm * Compute integral power of this, assuming this has been reduced and exp is >= 0. 338995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm */ 339995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm private BoundedRational rawPow(BigInteger exp) { 340995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (exp.equals(BigInteger.ONE)) { 341995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return this; 342f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 343995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (exp.and(BigInteger.ONE).intValue() == 1) { 344995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return rawMultiply(rawPow(exp.subtract(BigInteger.ONE)), this); 345f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 346995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (exp.signum() == 0) { 347682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return ONE; 348682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 349995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm BoundedRational tmp = rawPow(exp.shiftRight(1)); 350995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm if (Thread.interrupted()) { 351995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm throw new CR.AbortedException(); 352682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 353995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return rawMultiply(tmp, tmp); 354682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 355682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 356f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 357f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Compute an integral power of this. 358f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 359995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm public BoundedRational pow(BigInteger exp) { 360f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (exp.signum() < 0) { 361682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return inverse(pow(exp.negate())); 362682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 363f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (exp.equals(BigInteger.ONE)) { 364f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return this; 365f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 366995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm // Reducing once at the beginning means there's no point in reducing later. 367995e5eb3b58a5cbef2686feb34f53493c1825866Hans Boehm return reduce().rawPow(exp); 368682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 369682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 370682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm public static BoundedRational pow(BoundedRational base, BoundedRational exp) { 371f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (exp == null) { 372f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 373f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 374f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (exp.mNum.signum() == 0) { 375f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // Questionable if base has undefined value. Java.lang.Math.pow() returns 1 anyway, 376f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // so we do the same. 377682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return new BoundedRational(1); 378682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 379f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (base == null) { 380f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 381f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 3829e855e82dc86b3038b3e048a56be77af114e24f4Hans Boehm exp = exp.reduce().positiveDen(); 383f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (!exp.mDen.equals(BigInteger.ONE)) { 384f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return null; 385f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 386682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm return base.pow(exp.mNum); 387682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 388682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 389682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 390682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm private static final BigInteger BIG_FIVE = BigInteger.valueOf(5); 391cd740596f6f8bdacf02f735f116ffc544f922893Hans Boehm private static final BigInteger BIG_MINUS_ONE = BigInteger.valueOf(-1); 392682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm 393f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm /** 394f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Return the number of decimal digits to the right of the decimal point required to represent 395f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * the argument exactly. 396f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * Return Integer.MAX_VALUE if that's not possible. Never returns a value less than zero, even 397f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm * if r is a power of ten. 398f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm */ 39956bcbf121b29a035fba68a87b0c77ffa9d12a845Annie Chin public static int digitsRequired(BoundedRational r) { 400f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r == null) { 401f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return Integer.MAX_VALUE; 402f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 403f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm int powersOfTwo = 0; // Max power of 2 that divides denominator 404f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm int powersOfFive = 0; // Max power of 5 that divides denominator 405682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm // Try the easy case first to speed things up. 406f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm if (r.mDen.equals(BigInteger.ONE)) { 407f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return 0; 408f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm } 409682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm r = r.reduce(); 410682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm BigInteger den = r.mDen; 41182e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm if (den.bitLength() > MAX_SIZE) { 41282e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm return Integer.MAX_VALUE; 41382e5a2f60afd1cc330ccfa0b81b8824964e976c7Hans Boehm } 414682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm while (!den.testBit(0)) { 415f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm ++powersOfTwo; 416682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm den = den.shiftRight(1); 417682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 418f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm while (den.mod(BIG_FIVE).signum() == 0) { 419f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm ++powersOfFive; 420682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm den = den.divide(BIG_FIVE); 421682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 422f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // If the denominator has a factor of other than 2 or 5 (the divisors of 10), the decimal 423f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // expansion does not terminate. Multiplying the fraction by any number of powers of 10 424f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // will not cancel the demoniator. (Recall the fraction was in lowest terms to start 425f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // with.) Otherwise the powers of 10 we need to cancel the denominator is the larger of 426f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm // powersOfTwo and powersOfFive. 427cd740596f6f8bdacf02f735f116ffc544f922893Hans Boehm if (!den.equals(BigInteger.ONE) && !den.equals(BIG_MINUS_ONE)) { 428cd740596f6f8bdacf02f735f116ffc544f922893Hans Boehm return Integer.MAX_VALUE; 429cd740596f6f8bdacf02f735f116ffc544f922893Hans Boehm } 430f599db7639d61b030cde1189e3392be1f8c35a29Hans Boehm return Math.max(powersOfTwo, powersOfFive); 431682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm } 432682ff5e8ad465d74b289590e5c88e0cf129ca90bHans Boehm} 433