001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.math;
019:
020: import org.apache.harmony.math.internal.nls.Messages;
021:
022: /**
023: * Static library that provides all multiplication of {@link BigInteger} methods.
024: *
025: * @author Intel Middleware Product Division
026: * @author Instituto Tecnologico de Cordoba
027: */
028: class Multiplication {
029:
030: /** Just to denote that this class can't be instantiated. */
031: private Multiplication() {
032: }
033:
034: /**
035: * Break point in digits (number of {@code int} elements)
036: * between Karatsuba and Pencil and Paper multiply.
037: */
038: static final int whenUseKaratsuba = 63; // an heuristic value
039:
040: /**
041: * An array with powers of ten that fit in the type {@code int}.
042: * ({@code 10^0,10^1,...,10^9})
043: */
044: static final int tenPows[] = { 1, 10, 100, 1000, 10000, 100000,
045: 1000000, 10000000, 100000000, 1000000000 };
046:
047: /**
048: * An array with powers of five that fit in the type {@code int}.
049: * ({@code 5^0,5^1,...,5^13})
050: */
051: static final int fivePows[] = { 1, 5, 25, 125, 625, 3125, 15625,
052: 78125, 390625, 1953125, 9765625, 48828125, 244140625,
053: 1220703125 };
054:
055: /**
056: * An array with the first powers of ten in {@code BigInteger} version.
057: * ({@code 10^0,10^1,...,10^31})
058: */
059: static final BigInteger[] bigTenPows = new BigInteger[32];
060:
061: /**
062: * An array with the first powers of five in {@code BigInteger} version.
063: * ({@code 5^0,5^1,...,5^31})
064: */
065: static final BigInteger bigFivePows[] = new BigInteger[32];
066:
067: static {
068: int i;
069: long fivePow = 1L;
070:
071: for (i = 0; i <= 18; i++) {
072: bigFivePows[i] = BigInteger.valueOf(fivePow);
073: bigTenPows[i] = BigInteger.valueOf(fivePow << i);
074: fivePow *= 5;
075: }
076: for (; i < bigTenPows.length; i++) {
077: bigFivePows[i] = bigFivePows[i - 1]
078: .multiply(bigFivePows[1]);
079: bigTenPows[i] = bigTenPows[i - 1].multiply(BigInteger.TEN);
080: }
081: }
082:
083: /**
084: * Performs a multiplication of two BigInteger and hides the algorithm used.
085: * @see BigInteger#multiply(BigInteger)
086: */
087: static BigInteger multiply(BigInteger x, BigInteger y) {
088: return karatsuba(x, y);
089: }
090:
091: /**
092: * Performs the multiplication with the Karatsuba's algorithm.
093: * <b>Karatsuba's algorithm:</b>
094: *<tt>
095: * u = u<sub>1</sub> * B + u<sub>0</sub><br>
096: * v = v<sub>1</sub> * B + v<sub>0</sub><br>
097: *
098: *
099: * u*v = (u<sub>1</sub> * v<sub>1</sub>) * B<sub>2</sub> + ((u<sub>1</sub> - u<sub>0</sub>) * (v<sub>0</sub> - v<sub>1</sub>) + u<sub>1</sub> * v<sub>1</sub> +
100: * u<sub>0</sub> * v<sub>0</sub> ) * B + u<sub>0</sub> * v<sub>0</sub><br>
101: *</tt>
102: * @param op1 first factor of the product
103: * @param op2 second factor of the product
104: * @return {@code op1 * op2}
105: * @see #multiply(BigInteger, BigInteger)
106: */
107: static BigInteger karatsuba(BigInteger op1, BigInteger op2) {
108: BigInteger temp;
109: if (op2.numberLength > op1.numberLength) {
110: temp = op1;
111: op1 = op2;
112: op2 = temp;
113: }
114: if (op2.numberLength < whenUseKaratsuba) {
115: return multiplyPAP(op1, op2);
116: }
117: /* Karatsuba: u = u1*B + u0
118: * v = v1*B + v0
119: * u*v = (u1*v1)*B^2 + ((u1-u0)*(v0-v1) + u1*v1 + u0*v0)*B + u0*v0
120: */
121: // ndiv2 = (op1.numberLength / 2) * 32
122: int ndiv2 = (op1.numberLength & 0xFFFFFFFE) << 4;
123: BigInteger upperOp1 = op1.shiftRight(ndiv2);
124: BigInteger upperOp2 = op2.shiftRight(ndiv2);
125: BigInteger lowerOp1 = op1.subtract(upperOp1.shiftLeft(ndiv2));
126: BigInteger lowerOp2 = op2.subtract(upperOp2.shiftLeft(ndiv2));
127:
128: BigInteger upper = karatsuba(upperOp1, upperOp2);
129: BigInteger lower = karatsuba(lowerOp1, lowerOp2);
130: BigInteger middle = karatsuba(upperOp1.subtract(lowerOp1),
131: lowerOp2.subtract(upperOp2));
132: middle = middle.add(upper).add(lower);
133: middle = middle.shiftLeft(ndiv2);
134: upper = upper.shiftLeft(ndiv2 << 1);
135:
136: return upper.add(middle).add(lower);
137: }
138:
139: /**
140: * Multiplies two BigIntegers.
141: * Implements traditional scholar algorithm described by Knuth.
142: *
143: * <br><tt>
144: * <table border="0">
145: * <tbody>
146: *
147: *
148: * <tr>
149: * <td align="center">A=</td>
150: * <td>a<sub>3</sub></td>
151: * <td>a<sub>2</sub></td>
152: * <td>a<sub>1</sub></td>
153: * <td>a<sub>0</sub></td>
154: * <td></td>
155: * <td></td>
156: * </tr>
157: *
158: *<tr>
159: * <td align="center">B=</td>
160: * <td></td>
161: * <td>b<sub>2</sub></td>
162: * <td>b<sub>1</sub></td>
163: * <td>b<sub>1</sub></td>
164: * <td></td>
165: * <td></td>
166: * </tr>
167: *
168: * <tr>
169: * <td></td>
170: * <td></td>
171: * <td></td>
172: * <td>b<sub>0</sub>*a<sub>3</sub></td>
173: * <td>b<sub>0</sub>*a<sub>2</sub></td>
174: * <td>b<sub>0</sub>*a<sub>1</sub></td>
175: * <td>b<sub>0</sub>*a<sub>0</sub></td>
176: * </tr>
177: *
178: * <tr>
179: * <td></td>
180: * <td></td>
181: * <td>b<sub>1</sub>*a<sub>3</sub></td>
182: * <td>b<sub>1</sub>*a<sub>2</sub></td>
183: * <td>b<sub>1</sub>*a1</td>
184: * <td>b<sub>1</sub>*a0</td>
185: * </tr>
186: *
187: * <tr>
188: * <td>+</td>
189: * <td>b<sub>2</sub>*a<sub>3</sub></td>
190: * <td>b<sub>2</sub>*a<sub>2</sub></td>
191: * <td>b<sub>2</sub>*a<sub>1</sub></td>
192: * <td>b<sub>2</sub>*a<sub>0</sub></td>
193: * </tr>
194: *
195: *<tr>
196: * <td></td>
197: *<td>______</td>
198: * <td>______</td>
199: * <td>______</td>
200: * <td>______</td>
201: * <td>______</td>
202: * <td>______</td>
203: *</tr>
204: *
205: * <tr>
206: *
207: * <td align="center">A*B=R=</td>
208: * <td align="center">r<sub>5</sub></td>
209: * <td align="center">r<sub>4</sub></td>
210: * <td align="center">r<sub>3</sub></td>
211: * <td align="center">r<sub>2</sub></td>
212: * <td align="center">r<sub>1</sub></td>
213: * <td align="center">r<sub>0</sub></td>
214: * <td></td>
215: * </tr>
216: *
217: * </tbody>
218: * </table>
219: *
220: *</tt>
221: *
222: * @param op1 first factor of the multiplication {@code op1 >= 0}
223: * @param op2 second factor of the multiplication {@code op2 >= 0}
224: * @return a {@code BigInteger} of value {@code op1 * op2}
225: */
226: static BigInteger multiplyPAP(BigInteger a, BigInteger b) {
227: // PRE: a >= b
228: int aLen = a.numberLength;
229: int bLen = b.numberLength;
230: int resLength = aLen + bLen;
231: int resSign = (a.sign != b.sign) ? -1 : 1;
232: // A special case when both numbers don't exceed int
233: if (resLength == 2) {
234: long val = (a.digits[0] & 0xFFFFFFFFL)
235: * (b.digits[0] & 0xFFFFFFFFL);
236: int valueLo = (int) val;
237: int valueHi = (int) (val >>> 32);
238: return ((valueHi == 0) ? new BigInteger(resSign, valueLo)
239: : new BigInteger(resSign, 2, new int[] { valueLo,
240: valueHi }));
241: }
242: int[] aDigits = a.digits;
243: int[] bDigits = b.digits;
244: int resDigits[] = new int[resLength];
245: long carry;
246: long bDigit;
247: int i, j, m;
248: // Common case
249: for (j = 0; j < bLen; j++) {
250: carry = 0;
251: bDigit = (bDigits[j] & 0xFFFFFFFFL);
252: for (i = 0, m = j; i < aLen; i++, m++) {
253: carry += (aDigits[i] & 0xFFFFFFFFL) * bDigit
254: + (resDigits[m] & 0xFFFFFFFFL);
255: resDigits[m] = (int) carry;
256: carry >>>= 32;
257: }
258: resDigits[m] = (int) carry;
259: }
260: BigInteger result = new BigInteger(resSign, resLength,
261: resDigits);
262: result.cutOffLeadingZeroes();
263: return result;
264: }
265:
266: /**
267: * Multiplies an array of integers by an integer value
268: * and saves the result in {@code res}.
269: * @param a the array of integers
270: * @param aSize the number of elements of intArray to be multiplied
271: * @param factor the multiplier
272: * @return the top digit of production
273: */
274: private static int multiplyByInt(int res[], int a[],
275: final int aSize, final int factor) {
276: long carry = 0;
277:
278: for (int i = 0; i < aSize; i++) {
279: carry += (a[i] & 0xFFFFFFFFL) * (factor & 0xFFFFFFFFL);
280: res[i] = (int) carry;
281: carry >>>= 32;
282: }
283: return (int) carry;
284: }
285:
286: /**
287: * Multiplies an array of integers by an integer value.
288: * @param a the array of integers
289: * @param aSize the number of elements of intArray to be multiplied
290: * @param factor the multiplier
291: * @return the top digit of production
292: */
293: static int multiplyByInt(int a[], final int aSize, final int factor) {
294: return multiplyByInt(a, a, aSize, factor);
295: }
296:
297: /**
298: * Multiplies a number by a positive integer.
299: * @param val an arbitrary {@code BigInteger}
300: * @param factor a positive {@code int} number
301: * @return {@code val * factor}
302: */
303: static BigInteger multiplyByPositiveInt(BigInteger val, int factor) {
304: int resSign = val.sign;
305: if (resSign == 0) {
306: return BigInteger.ZERO;
307: }
308: int aNumberLength = val.numberLength;
309: int[] aDigits = val.digits;
310:
311: if (aNumberLength == 1) {
312: long res = (aDigits[0] & 0xFFFFFFFFL) * (factor);
313: int resLo = (int) res;
314: int resHi = (int) (res >>> 32);
315: return ((resHi == 0) ? new BigInteger(resSign, resLo)
316: : new BigInteger(resSign, 2, new int[] { resLo,
317: resHi }));
318: }
319: // Common case
320: int resLength = aNumberLength + 1;
321: int resDigits[] = new int[resLength];
322:
323: resDigits[aNumberLength] = multiplyByInt(resDigits, aDigits,
324: aNumberLength, factor);
325: BigInteger result = new BigInteger(resSign, resLength,
326: resDigits);
327: result.cutOffLeadingZeroes();
328: return result;
329: }
330:
331: static BigInteger pow(BigInteger base, int exponent) {
332: // PRE: exp > 0
333: BigInteger res = BigInteger.ONE;
334: BigInteger acc = base;
335:
336: for (; exponent > 1; exponent >>= 1) {
337: if ((exponent & 1) != 0) {
338: // if odd, multiply one more time by acc
339: res = res.multiply(acc);
340: }
341: // acc = base^(2^i)
342: //a limit where karatsuba performs a faster square than the square algorithm
343: if (acc.numberLength == 1) {
344: acc = acc.multiply(acc); // square
345: } else {
346: acc = new BigInteger(1, square(acc.digits,
347: acc.numberLength));
348: }
349: }
350: // exponent == 1, multiply one more time
351: res = res.multiply(acc);
352: return res;
353: }
354:
355: /**
356: * Performs a<sup>2</sup>
357: * @param a The number to square.
358: * @param length The length of the number to square.
359: */
360: static int[] square(int[] a, int s) {
361: int[] t = new int[s << 1];
362: long cs;
363: long aI;
364: for (int i = 0; i < s; i++) {
365: cs = 0;
366: aI = (0xFFFFFFFFL & a[i]);
367: for (int j = i + 1; j < s; j++) {
368: cs += (0xFFFFFFFFL & t[i + j]) + aI
369: * (0xFFFFFFFFL & a[j]);
370: t[i + j] = (int) cs;
371: cs >>>= 32;
372: }
373:
374: t[i + s] = (int) cs;
375: }
376: BitLevel.shiftLeft(t, t, 0, 1);
377: cs = 0;
378:
379: for (int i = 0, index = 0; i < s; i++, index++) {
380: aI = (0xFFFFFFFFL & a[i]);
381: cs += aI * aI + (t[index] & 0xFFFFFFFFL);
382: t[index] = (int) cs;
383: cs >>>= 32;
384: index++;
385: cs += t[index] & 0xFFFFFFFFL;
386: t[index] = (int) cs;
387: cs >>>= 32;
388: }
389: return t;
390: }
391:
392: /**
393: * Multiplies a number by a power of ten.
394: * This method is used in {@code BigDecimal} class.
395: * @param val the number to be multiplied
396: * @param exp a positive {@code long} exponent
397: * @return {@code val * 10<sup>exp</sup>}
398: */
399: static BigInteger multiplyByTenPow(BigInteger val, long exp) {
400: // PRE: exp >= 0
401: return ((exp < tenPows.length) ? multiplyByPositiveInt(val,
402: tenPows[(int) exp]) : val.multiply(powerOf10(exp)));
403: }
404:
405: /**
406: * It calculates a power of ten, which exponent could be out of 32-bit range.
407: * Note that internally this method will be used in the worst case with
408: * an exponent equals to: {@code Integer.MAX_VALUE - Integer.MIN_VALUE}.
409: * @param exp the exponent of power of ten, it must be positive.
410: * @return a {@code BigInteger} with value {@code 10<sup>exp</sup>}.
411: */
412: static BigInteger powerOf10(long exp) {
413: // PRE: exp >= 0
414: int intExp = (int) exp;
415: // "SMALL POWERS"
416: if (exp < bigTenPows.length) {
417: // The largest power that fit in 'long' type
418: return bigTenPows[intExp];
419: } else if (exp <= 50) {
420: // To calculate: 10^exp
421: return BigInteger.TEN.pow(intExp);
422: } else if (exp <= 1000) {
423: // To calculate: 5^exp * 2^exp
424: return bigFivePows[1].pow(intExp).shiftLeft(intExp);
425: }
426: // "LARGE POWERS"
427: /*
428: * To check if there is free memory to allocate a BigInteger of the
429: * estimated size, measured in bytes: 1 + [exp / log10(2)]
430: */
431: long byteArraySize = 1 + (long) (exp / 2.4082399653118496);
432:
433: if (byteArraySize > Runtime.getRuntime().freeMemory()) {
434: // math.01=power of ten too big
435: throw new OutOfMemoryError(Messages.getString("math.01")); //$NON-NLS-1$
436: }
437: if (exp <= Integer.MAX_VALUE) {
438: // To calculate: 5^exp * 2^exp
439: return bigFivePows[1].pow(intExp).shiftLeft(intExp);
440: }
441: /*
442: * "HUGE POWERS"
443: *
444: * This branch probably won't be executed since the power of ten is too
445: * big.
446: */
447: // To calculate: 5^exp
448: BigInteger powerOfFive = bigFivePows[1].pow(Integer.MAX_VALUE);
449: BigInteger res = powerOfFive;
450: long longExp = exp - Integer.MAX_VALUE;
451:
452: intExp = (int) (exp % Integer.MAX_VALUE);
453: while (longExp > Integer.MAX_VALUE) {
454: res = res.multiply(powerOfFive);
455: longExp -= Integer.MAX_VALUE;
456: }
457: res = res.multiply(bigFivePows[1].pow(intExp));
458: // To calculate: 5^exp << exp
459: res = res.shiftLeft(Integer.MAX_VALUE);
460: longExp = exp - Integer.MAX_VALUE;
461: while (longExp > Integer.MAX_VALUE) {
462: res = res.shiftLeft(Integer.MAX_VALUE);
463: longExp -= Integer.MAX_VALUE;
464: }
465: res = res.shiftLeft(intExp);
466: return res;
467: }
468:
469: /**
470: * Multiplies a number by a power of five.
471: * This method is used in {@code BigDecimal} class.
472: * @param val the number to be multiplied
473: * @param exp a positive {@code int} exponent
474: * @return {@code val * 5<sup>exp</sup>}
475: */
476: static BigInteger multiplyByFivePow(BigInteger val, int exp) {
477: // PRE: exp >= 0
478: if (exp < fivePows.length) {
479: return multiplyByPositiveInt(val, fivePows[exp]);
480: } else if (exp < bigFivePows.length) {
481: return val.multiply(bigFivePows[exp]);
482: } else {// Large powers of five
483: return val.multiply(bigFivePows[1].pow(exp));
484: }
485: }
486: }
|