9

I'm working on a project ( in Scala ), where I have a need to manipulate some very large numbers; far too big to be represented by the integral types. Java provides the BigInteger and BigDecimal classes (and scala provides a nice thin wrapper around them). However, I noticed that these libraries are substantially slower than other arbitrary precision libraries that I've used in the past (i.e. http://www.ginac.de/CLN/), and the speed difference seems larger than what can be attributed to the language alone.

I did some profiling of my program, and 44% of the execution time is being spent in the BigInteger multiply method. I'd like to speed up my program a bit, so I'm looking for a faster and more efficient option than the BigInteger class (and its Scala wrapper). I've looked at LargeInteger ( from JScience) and Aint (from Afloat). However, both seem to perform more slowly than the standard BigInteger class.

Does anyone know of a Java (or available on the JVM) arbitrary precision math library with a focus on high performance integer multiplication and addition?

nomad
  • 1,809
  • 2
  • 18
  • 33
  • There seems to be a some good experience here http://stackoverflow.com/questions/277309/java-floating-point-high-precision-library – thoredge Apr 26 '12 at 06:54
  • Thanks. However, I've seen this question and have tried both the JScience and AFloat libraries (which, as I said, seem to be slower than BigInteger). This may be because my numbers are in the twilight zone in terms of size (~1500 digits). Either way, I know the operations can be much faster (as the C++ code achieved this). Beside the language difference, mutability (vs. the immutable Java impls) could also be at play. – nomad Apr 26 '12 at 10:57

2 Answers2

2

I'm a bit late...well I only know the apfloat library, available in both C++ and Java. Apfloat-Library:

Mao
  • 21
  • 2
1

Unfortunately, I think you are out of luck for a Java native library. I have not found one. I recommend wrapping GMP, which has excellent arbitrary precision performance, using JNI. There is JNI overhead, but if you're in the 1500 digit range, that should be small compared to the difference in algorithmic complexity. You can find various wrappings of GMP for Java (I believe the most popular one is here).

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • Thanks Rex. I'll accept this answer b/c it seems sound. However, it seems that b/c I'm creating such a large number of big integers, the JNI overhead and JVM/native object allocation is actually killing me here; resulting in performance worse than that of Java's BigInteger. – nomad Apr 28 '12 at 16:15
  • @nomad - You need to reuse the integers. GMP can do this, and Scala can give you update-and-return-left-hand-argument operations that can somewhat help the reuse issue. See the "pidigits" Scala program that uses GMP in the Computer Languages Benchmark Game for an idea of how to do this. (I make no claims that this is the most elegant, but it is at least somewhat workable.) – Rex Kerr May 01 '12 at 18:58