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