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 } 129 130 BigInteger res = null; 131 try { 132 // "LARGE POWERS" 133 if (exp <= Integer.MAX_VALUE) { 134 // To calculate: 5^exp * 2^exp 135 res = bigFivePows[1].pow(intExp).shiftLeft(intExp); 136 } else { 137 /* 138 * "HUGE POWERS" 139 * 140 * This branch probably won't be executed since the power of ten is too 141 * big. 142 */ 143 // To calculate: 5^exp 144 BigInteger powerOfFive = bigFivePows[1].pow(Integer.MAX_VALUE); 145 res = powerOfFive; 146 long longExp = exp - Integer.MAX_VALUE; 147 148 intExp = (int) (exp % Integer.MAX_VALUE); 149 while (longExp > Integer.MAX_VALUE) { 150 res = res.multiply(powerOfFive); 151 longExp -= Integer.MAX_VALUE; 152 } 153 res = res.multiply(bigFivePows[1].pow(intExp)); 154 // To calculate: 5^exp << exp 155 res = res.shiftLeft(Integer.MAX_VALUE); 156 longExp = exp - Integer.MAX_VALUE; 157 while (longExp > Integer.MAX_VALUE) { 158 res = res.shiftLeft(Integer.MAX_VALUE); 159 longExp -= Integer.MAX_VALUE; 160 } 161 res = res.shiftLeft(intExp); 162 } 163 } catch (OutOfMemoryError error) { 164 throw new ArithmeticException(error.getMessage()); 165 } 166 167 return res; 168 } 169 170 /** 171 * Multiplies a number by a power of five. 172 * This method is used in {@code BigDecimal} class. 173 * @param val the number to be multiplied 174 * @param exp a positive {@code int} exponent 175 * @return {@code val * 5<sup>exp</sup>} 176 */ multiplyByFivePow(BigInteger val, int exp)177 static BigInteger multiplyByFivePow(BigInteger val, int exp) { 178 // PRE: exp >= 0 179 if (exp < fivePows.length) { 180 return multiplyByPositiveInt(val, fivePows[exp]); 181 } else if (exp < bigFivePows.length) { 182 return val.multiply(bigFivePows[exp]); 183 } else {// Large powers of five 184 return val.multiply(bigFivePows[1].pow(exp)); 185 } 186 } 187 } 188