Attached is a *revised* patch for bug 4837946, for implementing asymptotically faster algorithms for multiplication of large numbers in the BigInteger class: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 It only differs from my patch posted yesterday in one respect--the new methods getLower() and getUpper() now call trustedStripLeadingZeroInts() which has two effects: * Helps preserve the invariant expected by BigInteger that zero has a signum of zero and a mag array with length of zero (due to the way that the private constructor BigInteger(int[] mag, int signum) works.) * Optimizes some cases like multiplying 2*1000000, where the bit string has a large number of zeroes in a row. Please use this patch instead of the one I posted yesterday. -- Alan Eliasen | "Furious activity is no substitute eliasen@mindspring.com | for understanding." http://futureboy.us/ | --H.H. Williams diff --git a/src/share/classes/java/math/BigInteger.java b/src/share/classes/java/math/BigInteger.java --- a/src/share/classes/java/math/BigInteger.java +++ b/src/share/classes/java/math/BigInteger.java @@ -172,6 +172,22 @@ public class BigInteger extends Number i */ private final static long LONG_MASK = 0xffffffffL; + /** + * The threshhold value for using Karatsuba multiplication. If the number + * of ints in both mag arrays are greater than this number, then + * Karatsuba multiplication will be used. This value is found + * experimentally to work well. + */ + private static final int KARATSUBA_THRESHHOLD = 35; + + /** + * The threshhold value for using Karatsuba squaring. If the number + * of ints in the number are larger than this value, + * Karatsuba squaring will be used. This value is found + * experimentally to work well. + */ + private static final int KARATSUBA_SQUARE_THRESHHOLD = 100; + //Constructors /** @@ -530,7 +546,8 @@ public class BigInteger extends Number i if (bitLength < 2) throw new ArithmeticException("bitLength < 2"); // The cutoff of 95 was chosen empirically for best performance - prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd) + prime = (bitLength < SMALL_PRIME_THRESHOLD + ? smallPrime(bitLength, certainty, rnd) : largePrime(bitLength, certainty, rnd)); signum = 1; mag = prime.mag; @@ -1043,6 +1060,11 @@ public class BigInteger extends Number i private static final BigInteger TWO = valueOf(2); /** + * The BigInteger constant -1. (Not exported.) + */ + private static final BigInteger NEGATIVE_ONE = valueOf(-1); + + /** * The BigInteger constant ten. * * @since 1.5 @@ -1188,10 +1210,19 @@ public class BigInteger extends Number i if (val.signum == 0 || signum == 0) return ZERO; - int[] result = multiplyToLen(mag, mag.length, - val.mag, val.mag.length, null); - result = trustedStripLeadingZeroInts(result); - return new BigInteger(result, signum*val.signum); + int xlen = mag.length; + int ylen = val.mag.length; + + if ((xlen < KARATSUBA_THRESHHOLD) || (ylen < KARATSUBA_THRESHHOLD)) + { + + int[] result = multiplyToLen(mag, xlen, + val.mag, ylen, null); + result = trustedStripLeadingZeroInts(result); + return new BigInteger(result, signum*val.signum); + } + else + return multiplyKaratsuba(this, val); } /** @@ -1229,6 +1260,82 @@ public class BigInteger extends Number i } /** + * Multiplies two BigIntegers using the Karatsuba multiplication + * algorithm. This is a recursive divide-and-conquer algorithm which + * is more efficient for large numbers than what is commonly called the + * "grade-school" algorithm used in multiplyToLen. If the numbers to + * be multiplied have length n, the "grade-school" algorithm has + * an asymptotic complexity of O(n^2). In contrast, the Karatsuba + * algorithm has complexity of O(n^(log2(3))), or O(n^1.585). It achieves + * this increased performance by doing 3 multiplies instead of 4 when + * evaluating the product. As it has some overhead, should be used when + * both numbers are larger than a certain threshhold (found + * experimentally). + * + */ + private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y) + { + int xlen = x.mag.length; + int ylen = y.mag.length; + + // The number of ints in each half of the number. + int half = Math.max(xlen, ylen) / 2; + + BigInteger xl = x.getLower(half); + BigInteger xh = x.getUpper(half); + BigInteger yl = y.getLower(half); + BigInteger yh = y.getUpper(half); + + BigInteger p1 = xh.multiply(yh); + BigInteger p2 = xl.multiply(yl); + + // The following is (xh+xl)*(yh+yl) + BigInteger p3 = xh.add(xl).multiply(yh.add(yl)); + + // p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2 + BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2); + + if (x.signum * y.signum == -1) + return result.negate(); + else + return result; + } + + /** + * Returns a new BigInteger representing n lower ints of the number. + * This is used by Karatsuba multiplication and squaring. + */ + private BigInteger getLower(int n) { + int len = mag.length; + + if (len <= n) + return this; + + int lowerInts[] = new int[n]; + System.arraycopy(mag, len-n, lowerInts, 0, n); + + return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1); + } + + /** + * Returns a new BigInteger representing mag.length-n upper + * ints of the number. This is used by Karatsuba multiplication and + * squaring. + */ + private BigInteger getUpper(int n) { + int len = mag.length; + + if (len <= n) + return ZERO; + + int upperLen = len - n; + int upperInts[] = new int[upperLen]; + System.arraycopy(mag, 0, upperInts, 0, upperLen); + + return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1); + } + + /** * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}. * * @return {@code this<sup>2</sup>} @@ -1236,8 +1343,14 @@ public class BigInteger extends Number i private BigInteger square() { if (signum == 0) return ZERO; - int[] z = squareToLen(mag, mag.length, null); - return new BigInteger(trustedStripLeadingZeroInts(z), 1); + int len = mag.length; + if (len < KARATSUBA_SQUARE_THRESHHOLD) + { + int[] z = squareToLen(mag, len, null); + return new BigInteger(trustedStripLeadingZeroInts(z), 1); + } + else + return squareKaratsuba(); } /** @@ -1308,10 +1421,32 @@ public class BigInteger extends Number i } /** + * Squares a BigInteger using the Karatsuba squaring algorithm. + * It should be used when both numbers are larger than a + * certain threshhold (found experimentally). + * It is a recursive divide-and-conquer algorithm that has better + * asymptotic performance than the algorithm used in squareToLen. + */ + private BigInteger squareKaratsuba() + { + int half = mag.length / 2; + + BigInteger xl = getLower(half); + BigInteger xh = getUpper(half); + + BigInteger xhs = xh.square(); + BigInteger xls = xl.square(); + + // xh^2 << 64 + (((xl+xh)^2 - (xh^2 + xl^2)) << 32) + xl^2 + return xhs.shiftLeft(half*32).add(xl.add(xh).square().subtract(xhs.add(xls))).shiftLeft(half*32).add(xls); + } + + /** * Returns a BigInteger whose value is {@code (this / val)}. * * @param val value by which this BigInteger is to be divided. * @return {@code this / val} + * @throws ArithmeticException {@code val==0} */ public BigInteger divide(BigInteger val) {