Mark Udstrand wrote:How can this be changed to make the performance linear instead of exponential?
Well, you have a few things in play here:
1. Mike is right: there are probably faster "big" value classes out there; especially in projects dedicated to Maths. I think of Java's as a "general purpose" big integer, and the performance is generally adequate for an app guy like me.
2. BigIntegers are immutable, which means that the result of any calculation has to be copied to a new instance. In a highly specialized environment like a maths library, it's quite possible that you don't have to worry about niceties like Thread-safety and can make all numbers mutable.
3. I suspect the real problem is your division. The
pow() method does use repeated squaring (to be honest I have no idea if there are any faster methods now), but division seems to be pretty much as you'd expect.
4. Java doesn't have unsigned integers (except for
char), which means that there's quite a lot of conversion and masking of
ints to and from
longs. It seems to me that they
might have been able to gain some speed by using
chars and
ints instead; but maybe it's outweighed by the fact that you'd then have extra operations. It's also possible that they work a bit quicker on 64-bit JVMs, but I honestly don't know.
HIH
Winston