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

[Alan Eliasen]

   Attached is an UPDATED patch for bug 4837946, (and others) 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 also affects other bugs:

4228681:  Some BigInteger operations are slow with very large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681

   (This was closed but never fixed.)


4837946: Implement Karatsuba multiplication algorithm in BigInteger
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

    This is done, along with Toom-Cook multiplication.  My
implementation is intended to be easy to read, understand, and check.
It significantly improves multiplication performance for large numbers.
This bug will be able to be closed with this patch.

   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.


   This patch is almost identical to the ones posted earlier, but I've
merged Xiaobin Lu's recent changes to BigInteger with my code.  The
other change was removing an unnecessary carry check from the
exactDivideBy3 routine.

   I have again run tuning tests with Xiaobin's changes (no changes were
made to the thresholds as a result; the previous combinations worked
well.)

   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.)

   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.  Sun
has requested patches as small as possible.

   I will also have patches for pow() (see
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474 ) and for
toString ( http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897 )
once these are approved and I'm informed that I'm working in the right
direction.

   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.


   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

   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.

-- 
  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.patch
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090608/98ead44c/BigInteger.patch>