[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 (which also improves the
performance of large numbers BigDecimal, etc.)

   This patch slightly modifies the patch I sent before, primarily by
removing an unused method that I let slip through when editing the patch
file.  It also adds comments and links to further information about the
algorithms, and in one place renames a variable in one of my functions
for pedagogical correctness.  It also slightly changes a signum test to
follow the new convention set elsewhere by Xiaobin Lu, which will be
slightly more efficient.

   This patch supersedes any others.  As always, if you just want to
drop in my whole BigInteger class with other proposed fixes for pow(),
it's available at:

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

   I'd also like to put out a call for volunteers to help Sun review
this patch and get it into JDK 1.7.  The Karatsuba and Toom-Cook
multiplication algorithms are well-understood and straightforward, and
have been written in as simple and direct way as possible, building on
existing methods in Java.  If you are able to review this patch, please
contact me.  Thanks!  From all the e-mails I get, I know this is very
important to a lot of people.


Alan Eliasen wrote:
>   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
  eliasen at mindspring.com
  http://futureboy.us/

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: BigInteger.patch
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090609/fd964029/BigInteger.patch>