Attached is a 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
This patch implements Karatsuba multiplication and Karatsuba squaring
for numbers above a certain size (found by experimentation). These
patches are designed to be as easy to read as possible, and are
implemented in terms of already-existing methods in BigInteger. Some
more performance might be squeezed out of them by doing more low-level
bit-fiddling, but I wanted to get a working version in and tested.
This is quite a bit faster for large arguments. The crossover point
between the "grade-school" algorithm and the Karatsuba algorithm for
multiplication is set at 35 "ints" or about 1120 bits, which was found
to give the best crossover in timing tests, so you won't see improvement
below that. Above that, it's asymptotically faster. (O(n^1.585),
compared to O(n^2)) for the grade-school algorithm. Double the number
of digits, and the "grade school" algorithm takes about 4 times as long,
Karatsuba takes about 3 times as long. It's vastly superior for very
large arguments.
I'd also like to create another RFE for implementing even faster
multiplication algorithms for yet larger numbers, such as Toom-Cook.
Previously, I had indicated that I'd submit faster algorithms for
pow() at the same time, but the number of optimizations for pow() has
grown rather large, and I plan on working on it a bit more and
submitting it separately. Many/most combinations of operands for pow()
are now vastly faster (some hundreds of thousands of times,) but I'd
like to make it faster (or, at the least, the same performance for all
arguments, a few of which have gotten slightly slower.) Unfortunately,
these optimizations add to the size and complexity of that patch, which
is why I'm submitting it separately.
I have created regression tests that may or may not be what you want;
they simply multiply a very large bunch of numbers together and output
their results to a very large file, which you then "diff" against known
correct values. (My tests produce 345 MB of output per run!) I
validated the results by comparing them to the output of both JDK 1.6
and the Kaffe JVM, which was compiled to use the well-known and
widely-tested GMP libraries for its BigInteger work. All tests pass. I
haven't submitted these tests, but am awaiting getting a copy of the
existing regression tests that Joseph Darcy discussed on this list.
Please let me know if there's a problem with the patch. I had to
hand-edit a few lines to remove the work I'm doing for pow().
--
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
/**
@@ -1043,6 +1059,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 +1209,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 +1259,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(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 lowerInts[] = new int[upperLen];
+ System.arraycopy(mag, 0, lowerInts, 0, upperLen);
+
+ return new BigInteger(lowerInts, 1);
+ }
+
+ /**
* Returns a BigInteger whose value is [EMAIL PROTECTED]
(this<sup>2</sup>)}.
*
* @return [EMAIL PROTECTED] this<sup>2</sup>}
@@ -1236,8 +1342,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 +1420,31 @@ 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) {
