Anonymous member wrote: > Out of curiousity, how does the Java implementation compare to GMP in > terms of speed?
(Note: These numbers apply to the *revised* patch that I'll be posting in a few minutes.) It depends on the size of the numbers. When I run the regression tests that I wrote, my updated Java version runs in about 2 minutes. When I run the same regression test in Kaffe using GMP, it takes about 2 *hours*. (Some of the same tests using Java 1.6 take many, many hours without my optimizations for the pow() function). But those are a lot of small numbers. There is a lot of overhead in converting from Java to C types and back, and in Kaffe's relative slowness. And currently, only multiply() has been improved in my Java patches that I've submitted. Kaffe is about 25 times slower on the average program anyway. When you run Kaffe/GMP for very large numbers, Kaffe/GMP starts being very much faster. OpenJDK still can't compete for numbers that are on the cutting edge of number theory. But we'll be much better than we were before. If I were to write the same code in pure C using GMP, then GMP would be much faster. But I haven't done that. So it's hard to compare GMP to Java exactly. 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 Thus, for numbers of this size, my algorithms are more than 10 times faster than JDK 1.6, but 33 times slower than Kaffe/GMP. For multiplying the somewhat special form 2^1000000 * 2^1000001, (the arguments of this in binary are a 1 followed by a million zeroes) JDK 1.6 OpenJDK1.7 with my patches Kaffe w/GMP 117298 ms 386 ms 474 ms So, my algorithm is 303 times faster than JDK, and just slightly faster than Kaffe/GMP. 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 Thus, for numbers of this size, my patches make it 38.9 times faster, but still 99 times slower than GMP. Sigh. Well, to be expected. If you work with large numbers, GMP becomes ridiculously faster. Kaffe with GMP becomes only slightly slower than pure GMP as the portion of time in Java gets small. GMP includes 3-way Toom-Cook multiplication, and the much faster FFT multiplication (which is O(n)) for very large numbers, and hand-crafted assembly language that uses 64-bit instructions and limbs on my 64-bit architecture (as opposed to the 32-bit ints used in BigInteger. Hopefully some day in the future, BigInteger will be rewritten to use longs internally instead of ints. Multiplying two 64-bit longs does 4 times as much work as multiplying two 32-bit ints, and will thus likely be significantly faster, especially on 64-bit architectures.) So GMP is still very much faster for very large numbers. It is also *much* faster in turning numbers into strings, and in exponentiation. The algorithms in BigInteger are horrible for pow() and toString(). See the following bugs: 4641897: BigInteger.toString() algorithm slow for large numbers http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897 4646474: BigInteger.pow() algorithm slow in 1.4.0 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474 I have several fixes for both of these. My JVM-based programming language Frink ( http://futureboy.us/frinkdocs/ ) implements many of these improvements, and is much faster for a variety of arguments. I just need to finish improving these for a variety of different arguments, and considering the threading and memory-size-vs-speed tradeoffs in implementing toString efficiently. -- Alan Eliasen | "Furious activity is no substitute [EMAIL PROTECTED] | for understanding." http://futureboy.us/ | --H.H. Williams
