[UPDATED PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

   Attached is an UPDATED 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

   The difference between this patch and the one posted earlier are:

   * This patch now also implements 3-way Toom-Cook multiplication and
3-way Toom-Cook squaring in addition to the Karatsuba squaring.  3-way
Toom-Cook multiplication has an asymptotic efficiency of O(n^1.465),
compared to O(n^1.585) for Karatsuba and O(n^2) for the "grade-school"
algorithm, making it significantly faster for very large numbers.

   * Thresholds for various multiplications were slightly modified for
better performance.  The lower limit for Karatsuba multiplication is now
45 ints (1440 bits), and the lower limit for 3-way Toom-Cook
multiplication is now 85 ints (2720 bits).

   * Threshholds for squaring were changed.  Karatsuba squaring is used
at 100 ints (3200 bits) and 3-way Toom-Cook squaring is at 190 ints
(6080 bits.)

   This has been extensively tested.  My regression tests are probably
significant overkill for Sun's purposes.  They take about 30 hours to
run and produce about 232 gigabytes of output.  (Multiply each of those
numbers by 2 because you have to run it twice to compare the outputs of
different VMs, and then compare output.)

   Again, my question is:  how much time and space is acceptable for
regression tests?  I posed this before, but didn't get an answer.

   This patch contains only multiplication- and squaring-related
patches.  I will be submitting another patch of my changes to make the
pow() function very much faster, but that will be a separate patch.

   For those who'd rather just replace their BigInteger with my much
faster version, that also contains my patches for pow(), it's available at:

http://futureboy.us/temp/BigInteger.java

   Note that my version of pow() will probably change somewhat before
submission, but this current version works perfectly and is faster for
most arguments.  It's gotten slightly slower for some mid-size
arguments, which is what I will be fixing.

   Previous patch report follows:

>    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/20080328/c15ad1cc/BigInteger.diff>