BigInteger performance improvements

[Alan Eliasen]

   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?

-- 
  Alan Eliasen              |  "Furious activity is no substitute
  eliasen at mindspring.com    |    for understanding."
  http://futureboy.us/      |           --H.H. Williams