[PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

   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
  eliasen at mindspring.com    |    for understanding."
  http://futureboy.us/      |           --H.H. Williams
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: BigInteger.diff
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080219/27dfad64/BigInteger.diff>