[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

4646474: BigInteger.pow() algorithm slow in 1.4.0

   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