Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Anyone want a higher performance not-quite-so BigInteger

Reply
Thread Tools

Anyone want a higher performance not-quite-so BigInteger

 
 
pete kirkham
Guest
Posts: n/a
 
      08-11-2003
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

 
Reply With Quote
 
 
 
 
Chris Smith
Guest
Posts: n/a
 
      08-11-2003
pete kirkham wrote:
> 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
 
Reply With Quote
 
 
 
 
Roedy Green
Guest
Posts: n/a
 
      08-11-2003
On Mon, 11 Aug 2003 21:51:28 +0100, pete kirkham
<(E-Mail Removed)> wrote or quoted :

> 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.

--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
 
Reply With Quote
 
pete kirkham
Guest
Posts: n/a
 
      08-12-2003
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

 
Reply With Quote
 
Thomas Weidenfeller
Guest
Posts: n/a
 
      08-13-2003
pete kirkham <(E-Mail Removed)> writes:
> 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
 
Reply With Quote
 
pete kirkham
Guest
Posts: n/a
 
      08-13-2003
Thomas Weidenfeller wrote:
> 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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
tomcat for higher performance gavino Java 0 10-06-2008 08:58 PM
Accessing higher security level from higher security level nderose@gmail.com Cisco 0 07-11-2005 10:20 PM
how to convert "BigInteger" into "Integer"? how to print out a BigInteger binary value? nick Java 1 10-26-2004 02:45 PM
how to convert "BigInteger" into "Integer"? how to print out a BigInteger binary value? nick Java 0 10-26-2004 08:18 AM
math.BigInteger Performance rmcnutt Java 4 02-04-2004 03:54 PM



Advertisments