Karatsuba is a recursive algorithm for multiplying multi precision integers. It has a running time of O(n ^ 1.58) compared to O(n ^ 2) [or O(n * m)] for the "simple" multiplication algorithm. It is discussed in Knuth volume 2 and http://cr.yp.to/papers/m3.pdf as well as other literature.

Anecdotal evidence indicates that Karatsuba is the best multiplication algorithm for numbers of around 500 to a few 1000 bits as are commonly used in cryptographic and other common applications. Therefore, we should consider implementing it in BigInteger.

  xxxxx@xxxxx   2003-03-26

N/A

Using more efficient and sophisticated algorithms to implement BigInteger operations is a venerable goal.

  xxxxx@xxxxx   2003-03-26

Currently deferring until a post-Tiger release.

  xxxxx@xxxxx   2003-10-21

Implementing Karatsuba multiplication is dead easy.  For example, see:

http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html

I warn that that implementation has two potential problems:

* It may not handle negative numbers correctly.  Easy enough to fix.  Flip the signs before applying it

* The decision to use Karatsuba vs. "grade school" multiplication is set at 20,000 bits.  I think this is probably way too high.  An optimal value may be found by experiment, but it's probably somewhere between 300 and 2000 bits. 

By the way, should there be separate requests to implement Toom-Cook and FFT multiplication?

I have submitted a patch for Karatsuba multiplication and Karatsuba squaring to the OpenJDK project.  This improves the performance of multiplication for numbers above about 1200 bits.  I am working on patches for pow() and toString().  Hopefully these will be included in the next release.

The previous posting was mine.  I have now submitted a revised patch to the OpenJDK project that implements both Karatsuba multiplication and 3-way Toom-Cook multiplication.  This is very much faster than the current implementation for large numbers.  For example, 3^14,000,000 * 3^14,000,001 is approximately 90 times faster than JDK 1.6  (it reduces the time from over 58 minutes to about 37 seconds.)

I will be submitting patches with my improvements for the pow() function and for radix conversions soon. 

Please contact me if you want to test or examine my patches.

--Alan Eliasen

For some reason, my username isn't showing up.  The last 2 posts were mine.  Please contact me with questions.

Alan Eliasen
eliasen@mindspring.com