Further BigInteger performance improvements

[Alan Eliasen]

   A few weeks ago, I posted some performance numbers for the
improvements I'm making to the BigInteger class.  Those performance
numbers were for the Karatsuba multiplication algorithm that I
implemented.  I've now implemented 3-way Toom-Cook multiplication (and
Toom-Cook squaring) which has better asymptotic performance than
Karatsuba multiplication.  (Karatsuba is O(n^1.585), 3-way Toom Cook is
O(n^1.465).  Compare this to Java 1.6 which used only O(n^2)
algorithms.)  One of the three algorithms are then chosen according to
the size of the numbers.

   There's also a lot of room for doing asymmetrical Toom-Cook
multiplication, with, say, one side being broken into 4 parts, and the
other into 2 parts, but that's lower on my priority list.

   Since I haven't heard of any progress on including my previous patch,
I'll be submitting a revised patch with Toom-Cook multiplication
included soon.  Below, interspersed among my previous statements, are
some updated performance numbers with the Toom-Cook algorithm:

Alan Eliasen wrote:
>    But some numbers.  For multiplying the numbers 3^1000000 * 3^1000001,
> (with my fixes to do the exponentiation hundreds of thousands of times
> faster factored out; without these, JDK 1.6 would be thousands of times
> slower,) the times for 20 iterations are:
> 
>    JDK 1.6	OpenJDK1.7 with my patches	Kaffe w/GMP
>    292987 ms	28650 ms			866 ms

With Toom/Cook: 18054 ms
Performance improvement over Java 1.6:  16.2x

>    For multiplying numbers 3^14000000 * 3^14000001, the time for 1
> iteration is:
> 
>    JDK 1.6	OpenJDK1.7 with my patches	Kaffe w/GMP
>    3499115 ms	89505 ms			910 ms

With Toom/Cook: 43636 ms

Performance improvement over Java 1.6:  80.18x

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