BigInteger performance improvements

[Joseph D. Darcy]

Hello.

Yes, this is the right group :-)  As "Java Floating-Point Czar" I also 
look after BigInteger, although I haven't had much time for proactive 
maintenance there in a while.  I think using faster, more mathematically 
sophisticated algorithms in BigInteger for large values would be a fine 
change to explore, as long as the performance on small values was 
preserved and regression tests appropriate for the new algorithms were 
developed too.

I'd prefer to process changes in smaller chunks rather a huge one all at 
once; however, I may be a bit slow on reviews in the near future due to 
some other openjdk work I'm leading up 
(http://openjdk.java.net/projects/jdk6/).

-Joe Darcy

Alan Eliasen wrote:
>    I'm planning on tackling the performance issues in the BigInteger
> class.  In short, inefficient algorithms are used for
> multiplication, exponentiation, conversion to strings, etc.  I intend to
> improve this by adding algorithms with better asymptotic behavior that
> will work better for large numbers, while preserving the existing
> algorithms for use with smaller numbers.
> 
>    This encompasses a lot of different bug reports:
> 
> 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
> 
>     I've already done the work on this one.  My implementation is
> intended to be easy to read, understand, and check.  It significantly
> improves multiplication performance for large numbers.
> 
> 
> 4646474: BigInteger.pow() algorithm slow in 1.4.0
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
> 
>    This will be improved in a couple ways:
> 
>    * Rewrite pow() to use the above Karatsuba multiplication
>    * Implement Karatsuba squaring
>    * Finding a good threshhold for Karatsuba squaring
>    * Rewrite pow() to use Karatsuba squaring
>    * Add an optimization to use left-shifting for multiples of 2 in the
> base.  This improves speed by thousands of times for things like
> Mersenne numbers.
> 
> 
> 4641897: BigInteger.toString() algorithm slow for large numbers
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897
> 
>     This algorithm uses a very inefficient algorithm for large numbers.
>  I plan to replace it with a recursive divide-and-conquer algorithm
> devised by Schoenhage and Strassen.  I have developed and tested this in
> my own software.  This operates hundreds or thousands of times faster
> than the current version for large numbers.  It will also benefit from
> faster multiplication and exponentiation.
> 
> 
>    In the future, we should also add multiplication routines that are
> even more efficient for very large numbers, such as Toom-Cook
> multiplication, which is more efficient than Karatsuba multiplication
> for even larger numbers.
> 
>    Has anyone else worked on these?  Is this the right group?
> 
>    I will probably submit the Karatsuba multiplication patch soon.
> Would it be more preferable to implement *all* of these parts first and
> submit one large patch?
>