Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] big numbers library

Expand Messages
  • Alan Eliasen
    If it wasn t clear (and it wasn t,) the algorithm I just posted was one to speed up exponentiation. I use it as a wrapper around BigInteger.pow(BigInteger
    Message 1 of 9 , Aug 7, 2005
    • 0 Attachment
      If it wasn't clear (and it wasn't,) the algorithm I just posted was
      one to speed up exponentiation. I use it as a wrapper around
      BigInteger.pow(BigInteger big, int exponent) in Java.

      --
      Alan Eliasen | "It is not enough to do your best;
      eliasen@... | you must know what to do and THEN
      http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
    • fyatim
      Alan, Yes is clear .. Thanks. But, my problem still the same when the exponent is a prime 2... I m trying to find out the best (fastest) way to calculate it
      Message 2 of 9 , Aug 21, 2005
      • 0 Attachment
        Alan,
        Yes is clear .. Thanks.
        But, my problem still the same when the exponent is a prime > 2...
        I'm trying to find out the best (fastest) way to calculate it ...
        I welcome any new ideas...
        Regards
        Faysal

        -----Original Message-----
        From: primenumbers@yahoogroups.com [mailto:primenumbers@yahoogroups.com] On
        Behalf Of Alan Eliasen
        Sent: Sunday, August 07, 2005 3:34 PM
        To: fyatim
        Cc: 'Jan van Oort'; 'Prime Number'
        Subject: Re: [PrimeNumbers] big numbers library

        fyatim wrote:
        > I wrote a small method using a well known algorithm "Exponentiation by
        > Squaring", but it still take horrible execution time.

        That's because Sun's Java implementation still uses horrible O(n^2)
        algorithms for multiplication. Their exponentiation routine already
        does exponentiation by squaring, so you probably can't improve on it
        without fixing multiplication.

        > Where can I find the algorithm you are mentioning i.e. "bit shifting" ??

        "Bit shifting" works when your base contains powers of 2. This is
        because you can do powers of 2 by simply left-shifting the binary
        representation by the appropriate number of bits. If you're doing
        something like calculating large Mersenne numbers, this makes it about a
        thousand times faster or more than Sun's implementation. It's an easy
        and obvious optimization that Sun missed.

        In short, here's a code snippet that does it. The base is expected
        to be in a BigInteger called "big", and the exponent in an int called
        "exponent". It factors out powers of two quickly by the call to
        getLowestSetBit(), and does the exponentiation for powers of two rapidly
        with shiftLeft() and then multiplies it by the remaining part that isn't
        a power of 2.

        This only helps if your base contains powers of 2.

        if (big.signum() > 0)
        {
        // Get factor of two
        int bit = big.getLowestSetBit();

        if (bit > 0)
        {
        big = big.shiftRight(bit);
        BigInteger twoPower = FrinkBigInteger.ONE.shiftLeft(bit*exponent);
        if (big.equals(FrinkBigInteger.ONE))
        return FrinkInteger.construct(twoPower);
        else
        {
        big = big.pow(exponent);
        return FrinkInteger.construct(big.multiply(twoPower));
        }
        }
        }

        --
        Alan Eliasen | "It is not enough to do your best;
        eliasen@... | you must know what to do and THEN
        http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming


        Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        The Prime Pages : http://www.primepages.org/


        Yahoo! Groups Links
      Your message has been successfully submitted and would be delivered to recipients shortly.