Anyone want a higher performance not-quite-so BigInteger

[pete kirkham]

As a result of doing a fibbonacci function example in C++, I wrote some
code for big integer addition that is 31 bit packed (not having 64bit
longs in the version of C++ I was using). The implementation of
BigInteger on Sun's and Apple's JVMs is 32 bit packed and casts to long
to allow the words to overflow, instead of using the high bit on 32bit
addition/subtraction. Basically, the 31 bit packed version does more,
less costly operations.

On Apple's 1.4.1 JVM on a G4:
For addition of small values, ~75% faster.
For addition of ~1000 digit values, ~35% faster.
For addition of ~10000 digit values, ~25% faster.

I would expect the performance gain to tail off as the number of digits
increases.

I would expect this method to be slower on an 64 bit JVM implementation,
should someone write one (it is word length dependant). Is the JVM for
the intel chip 64 bit?

Is there anyone out there who is doing addition/subtraction intensive
calculations in that range of digits on 32 bit machines that would want
to use it? If so, I'll write the other operations (subtraction will be
as good as addition; multiplication is likely to be slower by 1/32;
division I don't know without doing it as I'd play with the algorithm a
bit) and put it on sourceforge. Otherwise I'll play with a bit and
release it much later as part of (kin).


Pete

 

[Chris Smith]

I would expect this method to be slower on an 64 bit JVM implementation,
should someone write one (it is word length dependant). Is the JVM for
the intel chip 64 bit?

Not sure, but the JVM for DEC/Compaq/HP's Tru64 UNIX has been 64-bit for
some time, and I'm sure there are plenty of others. Not sure where the
"64-bit VMs don't exist yet" myth came from, and it may well have been
true when it became popular knowledge, but it's been false for years
now.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Roedy Green]

Is the JVM for
the intel chip 64 bit?

For the AMD Opteron and Intel Itanium long would be a native 64 bit
long, but for the Pentium implementations, long arithmetic is done
with a pair of 32 bit values.

 

[pete kirkham]

Roedy Green wrote:>

For the AMD Opteron and Intel Itanium long would be a native 64 bit
long, but for the Pentium implementations, long arithmetic is done
with a pair of 32 bit values.

I was packing at 31 bits as I'd ported it from a 32bit C++, but it
occured to me today that it would be most efficient to pack at two less
than the largest integer word size supported, so that you do nearly the
fewest operations during addition, and you can still multiply half
your pack-word and stay within the pack-word size size.

Packing at 62 bits is around 40% faster on addition than packing at 32
bits on my setup (basically it's doing nearly half as many adds, and one
of the carries is native in the JVM instead of being coded outside it,
or in hardware if it's a 64bit JVM), so whether the JVM is 32 or 64 bit
doesn't matter after all.

You have 64/62 N digits instead of N digits, so multiplication is likely
to be ~7% slower (digits^2 64 bit operations, overflow not important).


Pete

 

[Thomas Weidenfeller]

I was packing at 31 bits as I'd ported it from a 32bit C++, but it
occured to me today that it would be most efficient to pack at two less
than the largest integer word size supported, so that you do nearly the
fewest operations during addition, and you can still multiply half
your pack-word and stay within the pack-word size size.

I know Sun is not known to react very fast to user suggestions / bug
reports, but maybe you can managet to contact someone at Sun and push
your implementation into a future version of Java. Just an idea ...

/Thomas

 

[pete kirkham]

I know Sun is not known to react very fast to user suggestions / bug
reports, but maybe you can managet to contact someone at Sun and push
your implementation into a future version of Java. Just an idea ...

/Thomas

Since I'm stuck at work at java 1.4.1 as the company can't afford to
replace the software that upgrading the OS (or even applying service
packs) would break, and at home I'm happy on Apple, what Sun might do in
the future takes a long to effect me. But I'll submit it to the process
after I've played with it a bit and got bored.

If you want to look at the skeletal implementation for additon and
multiplication, you can at http://tme.g-well.net/bignum.html.

If anyone is running a 64bit JVM, I'd be interested to see the effect.

Cheers,


Pete