Look what I found
Once again I’m working on my mathematical side project (it’s an unhealthy obsession). I’m writing a bunch of Java code for this. I know, “Java is slow.” Shut up: a) you’re wrong and b) it doesn’t matter. I’m trying to tackle a problem that algorithmically should take longer than this planet has left before the sun goes supernova. So what choice of language I use won’t really matter. The algorithm is what matters.
Anyway, I do a lot of stuff using java.util.BigInteger. BigInteger is slow. Even worse, it’s immutable. That means if I do something as simple as adding 1 to a BigInteger, it allocates another BigInteger to hold the answer. I do a lot of very miniscule operations on BigIntegers, so I’m positive my application is spending a ton of time allocating and garbage collecting BigIntegers.
As it turns out, Java has (in 1.5 anyway) a MutableBigInteger class (also in the java.math package). Unfortunately, it’s package private. That means only BigInteger gets to use it. Fortunately, Sun distributes the Java source with the JDK so I should be able to “borrow” that class by simply copying it to one of my packages. My code tends to throw BigIntegers away a lot. If I could switch to using a MutableBigInteger, I could throw them into a free list for later use, saving a lot of object creation and garbage collection overhead down the road.
I know, I could switch my code to C/C++ and use GMP. GMP is super fast, gives you mutable numeric types and is easy to use, I won’t deny that. But C/C++ makes me want to hang myself and most of the big number operations I need aren’t provided by GMP either (I have some odd requirements, don’t ask). I might as well use a language I enjoy and have good tools for.
If you had to work with really big numbers (560 bit and up), what language/library would you use? Multiplication, modulus and bit fiddling are absolute necessities. Speedy execution time would be nice, but right now development time is more important to me.
February 15th, 2006 at 8:26 am
It might be worth checking out Javolution. Nothing for fancy math operations there, but some potentially useful object pooling code.
February 15th, 2006 at 9:24 am
Yeah, I totally need to brush up on my Java-fu. I noticed a ton of shiny stuff in 1.5 that I haven’t played with yet.
February 15th, 2006 at 9:48 am
The ObjectFactory looks like it’s basically a free list. It doesn’t mention how it recycles objects, though. Can I just drop objects allocated by the factory on the floor and the factory will automagically recycle them?
February 15th, 2006 at 9:51 pm
The tricky/clever bit is the use of finally blocks. The basic idea is you initialize a context when you enter the use of pooled objects, and then in a finally clause on the way out, free them all at once (returning them to the free list).
See http://javolution.org/api/javolution/realtime/Context.html
March 9th, 2006 at 9:51 am
Hi Ryan, I f ound you via the Yahoo Java APIs.
Interesting to see you’re working on factorizations. It’s been a compulsion^W passion for me for a while.
I’m trying to do visualization (and aural) analysis since the brain is infinitely quicker in patternizing sounds and pics than any algorithm could be (this is my hypothesis).
Would be interesting to see what you’re doing with RSA.
I need to learn more about Q-Matrices to speed up bigints.
Python’s arbitrary numerical library is pretty fast, btw.