1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package java.math; 19 20 /** 21 * Static library that provides all multiplication of {@link BigInteger} methods. 22 */ 23 class Multiplication { 24 25 /** Just to denote that this class can't be instantiated. */ Multiplication()26 private Multiplication() {} 27 28 // BEGIN android-removed 29 // /** 30 // * Break point in digits (number of {@code int} elements) 31 // * between Karatsuba and Pencil and Paper multiply. 32 // */ 33 // static final int whenUseKaratsuba = 63; // an heuristic value 34 // END android-removed 35 36 /** 37 * An array with powers of ten that fit in the type {@code int}. 38 * ({@code 10^0,10^1,...,10^9}) 39 */ 40 static final int[] tenPows = { 41 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 42 }; 43 44 /** 45 * An array with powers of five that fit in the type {@code int}. 46 * ({@code 5^0,5^1,...,5^13}) 47 */ 48 static final int[] fivePows = { 49 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 50 1953125, 9765625, 48828125, 244140625, 1220703125 51 }; 52 53 /** 54 * An array with the first powers of ten in {@code BigInteger} version. 55 * ({@code 10^0,10^1,...,10^31}) 56 */ 57 static final BigInteger[] bigTenPows = new BigInteger[32]; 58 59 /** 60 * An array with the first powers of five in {@code BigInteger} version. 61 * ({@code 5^0,5^1,...,5^31}) 62 */ 63 static final BigInteger bigFivePows[] = new BigInteger[32]; 64 65 66 67 static { 68 int i; 69 long fivePow = 1L; 70 71 for (i = 0; i <= 18; i++) { 72 bigFivePows[i] = BigInteger.valueOf(fivePow); 73 bigTenPows[i] = BigInteger.valueOf(fivePow << i); 74 fivePow *= 5; 75 } 76 for (; i < bigTenPows.length; i++) { 77 bigFivePows[i] = bigFivePows[i - 1].multiply(bigFivePows[1]); 78 bigTenPows[i] = bigTenPows[i - 1].multiply(BigInteger.TEN); 79 } 80 } 81 82 // BEGIN android-note: multiply has been removed in favor of using OpenSSL BIGNUM 83 // END android-note 84 85 /** 86 * Multiplies a number by a positive integer. 87 * @param val an arbitrary {@code BigInteger} 88 * @param factor a positive {@code int} number 89 * @return {@code val * factor} 90 */ multiplyByPositiveInt(BigInteger val, int factor)91 static BigInteger multiplyByPositiveInt(BigInteger val, int factor) { 92 BigInt bi = val.getBigInt().copy(); 93 bi.multiplyByPositiveInt(factor); 94 return new BigInteger(bi); 95 } 96 97 /** 98 * Multiplies a number by a power of ten. 99 * This method is used in {@code BigDecimal} class. 100 * @param val the number to be multiplied 101 * @param exp a positive {@code long} exponent 102 * @return {@code val * 10<sup>exp</sup>} 103 */ multiplyByTenPow(BigInteger val, long exp)104 static BigInteger multiplyByTenPow(BigInteger val, long exp) { 105 // PRE: exp >= 0 106 return ((exp < tenPows.length) 107 ? multiplyByPositiveInt(val, tenPows[(int)exp]) 108 : val.multiply(powerOf10(exp))); 109 } 110 111 /** 112 * It calculates a power of ten, which exponent could be out of 32-bit range. 113 * Note that internally this method will be used in the worst case with 114 * an exponent equals to: {@code Integer.MAX_VALUE - Integer.MIN_VALUE}. 115 * @param exp the exponent of power of ten, it must be positive. 116 * @return a {@code BigInteger} with value {@code 10<sup>exp</sup>}. 117 */ powerOf10(long exp)118 static BigInteger powerOf10(long exp) { 119 // PRE: exp >= 0 120 int intExp = (int)exp; 121 // "SMALL POWERS" 122 if (exp < bigTenPows.length) { 123 // The largest power that fit in 'long' type 124 return bigTenPows[intExp]; 125 } else if (exp <= 50) { 126 // To calculate: 10^exp 127 return BigInteger.TEN.pow(intExp); 128 } else if (exp <= 1000) { 129 // To calculate: 5^exp * 2^exp 130 return bigFivePows[1].pow(intExp).shiftLeft(intExp); 131 } 132 // "LARGE POWERS" 133 /* 134 * To check if there is free memory to allocate a BigInteger of the 135 * estimated size, measured in bytes: 1 + [exp / log10(2)] 136 */ 137 long byteArraySize = 1 + (long)(exp / 2.4082399653118496); 138 139 if (byteArraySize > Runtime.getRuntime().freeMemory()) { 140 throw new ArithmeticException(); 141 } 142 if (exp <= Integer.MAX_VALUE) { 143 // To calculate: 5^exp * 2^exp 144 return bigFivePows[1].pow(intExp).shiftLeft(intExp); 145 } 146 /* 147 * "HUGE POWERS" 148 * 149 * This branch probably won't be executed since the power of ten is too 150 * big. 151 */ 152 // To calculate: 5^exp 153 BigInteger powerOfFive = bigFivePows[1].pow(Integer.MAX_VALUE); 154 BigInteger res = powerOfFive; 155 long longExp = exp - Integer.MAX_VALUE; 156 157 intExp = (int)(exp % Integer.MAX_VALUE); 158 while (longExp > Integer.MAX_VALUE) { 159 res = res.multiply(powerOfFive); 160 longExp -= Integer.MAX_VALUE; 161 } 162 res = res.multiply(bigFivePows[1].pow(intExp)); 163 // To calculate: 5^exp << exp 164 res = res.shiftLeft(Integer.MAX_VALUE); 165 longExp = exp - Integer.MAX_VALUE; 166 while (longExp > Integer.MAX_VALUE) { 167 res = res.shiftLeft(Integer.MAX_VALUE); 168 longExp -= Integer.MAX_VALUE; 169 } 170 res = res.shiftLeft(intExp); 171 return res; 172 } 173 174 /** 175 * Multiplies a number by a power of five. 176 * This method is used in {@code BigDecimal} class. 177 * @param val the number to be multiplied 178 * @param exp a positive {@code int} exponent 179 * @return {@code val * 5<sup>exp</sup>} 180 */ multiplyByFivePow(BigInteger val, int exp)181 static BigInteger multiplyByFivePow(BigInteger val, int exp) { 182 // PRE: exp >= 0 183 if (exp < fivePows.length) { 184 return multiplyByPositiveInt(val, fivePows[exp]); 185 } else if (exp < bigFivePows.length) { 186 return val.multiply(bigFivePows[exp]); 187 } else {// Large powers of five 188 return val.multiply(bigFivePows[1].pow(exp)); 189 } 190 } 191 } 192