[PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger
Alan Eliasen
eliasen at mindspring.com
Wed Feb 20 22:45:48 UTC 2008
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
eliasen at mindspring.com | for understanding."
http://futureboy.us/ | --H.H. Williams
More information about the core-libs-dev
mailing list