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@mindspring.com | for understanding." http://futureboy.us/ | --H.H. Williams