Review request: Fast multiplication and division

[Tim Buktu]

Hi everyone,

I made a patch against the latest BigInteger.java that speeds up
multiplication and division of large numbers. It is based on Alan
Eliasen's excellent work which unfortunately hasn't been included yet.

There are three algorithms in this patch,
 1) Karatsuba multiplication which is used above ~480 decimal digits;
 2) Toom-Cook multiplication which is used above ~720 decimal digits;
 3) Burnikel-Ziegler division which is used above ~480 decimal digits.

Karatsuba and Toom-Cook were implemented by Alan, and Burnikel-Ziegler
was implemented by me. I have reviewed Alan's code, and I verified that
the patched BigInteger passes BigIntegerTest (using suitable lengths) as
well as my own tests.

On my machine, the speedup for multiplication is as follows:
 * 1.3 times faster for 1,000-digit numbers
 * 3.9 times faster for 10,000-digit numbers
 * 12.4 times faster for 100,000-digit numbers

The speedup for division is as follows:
 * 1.4 times faster for 1,000-digit numbers
 * 3.4 times faster for 10,000-digit numbers
 * 10.4 times faster for 100,000-digit numbers

The patch is at https://gist.github.com/1576016
and the patched BigInteger.java is at https://gist.github.com/1576025 .
Thanks,

Tim