Anyone want a higher performance not-quite-so BigInteger

Discussion in 'Java' started by pete kirkham, Aug 11, 2003.

  1. pete kirkham

    pete kirkham Guest

    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
    pete kirkham, Aug 11, 2003
    #1
    1. Advertising

  2. pete kirkham

    Chris Smith Guest

    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
    Chris Smith, Aug 11, 2003
    #2
    1. Advertising

  3. pete kirkham

    Roedy Green Guest

    On Mon, 11 Aug 2003 21:51:28 +0100, pete kirkham
    <> 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.
    Roedy Green, Aug 11, 2003
    #3
  4. pete kirkham

    pete kirkham Guest

    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
    pete kirkham, Aug 12, 2003
    #4
  5. pete kirkham <> 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
    Thomas Weidenfeller, Aug 13, 2003
    #5
  6. pete kirkham

    pete kirkham Guest

    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
    pete kirkham, Aug 13, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. rmcnutt

    math.BigInteger Performance

    rmcnutt, Feb 3, 2004, in forum: Java
    Replies:
    4
    Views:
    1,610
    Juergen Kreileder
    Feb 4, 2004
  2. nick
    Replies:
    0
    Views:
    883
  3. nick
    Replies:
    1
    Views:
    31,699
    Eric Sosman
    Oct 26, 2004
  4. Replies:
    5
    Views:
    323
  5. Richard \(MrBonus\)

    onBeforeUnload doesn't work quite the way I want it too

    Richard \(MrBonus\), Sep 2, 2004, in forum: Javascript
    Replies:
    1
    Views:
    111
    Robert
    Sep 7, 2004
Loading...

Share This Page