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
