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 [EMAIL PROTECTED] | for understanding." http://futureboy.us/ | --H.H. Williams
