RE: [PrimeNumbers] big numbers library
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...
From: firstname.lastname@example.org [mailto:email@example.com] On
Behalf Of Alan Eliasen
Sent: Sunday, August 07, 2005 3:34 PM
Cc: 'Jan van Oort'; 'Prime Number'
Subject: Re: [PrimeNumbers] big numbers library
> I wrote a small method using a well known algorithm "Exponentiation byThat's because Sun's Java implementation still uses horrible O(n^2)
> Squaring", but it still take horrible execution time.
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);
big = big.pow(exponent);
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: firstname.lastname@example.org
The Prime Pages : http://www.primepages.org/
Yahoo! Groups Links