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
[EMAIL PROTECTED] | 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 [EMAIL PROTECTED]
(this<sup>2</sup>)}.
*
* @return [EMAIL PROTECTED] 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 [EMAIL PROTECTED] (this / val)}.
*
* @param val value by which this BigInteger is to be divided.
* @return [EMAIL PROTECTED] this / val}
+
* @throws ArithmeticException [EMAIL PROTECTED] val==0}
*/
public BigInteger divide(BigInteger val) {
