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
18package java.math;
19
20/**
21 * Static library that provides all multiplication of {@link BigInteger} methods.
22 */
23class Multiplication {
24
25    /** Just to denote that this class can't be instantiated. */
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     */
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     */
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     */
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     */
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