- Jan van Oort wrote:
> 2) take Colin Plum's source code, study it closely, and use to implement

I need to clarify that Sun's JVM hasn't used Colin Plumb's library

> your own method in a shared library ( .so or .dll compiled from C/C++ ).

> Probably closely related to 1)

> 3) download the sources of java.math.BigInteger and see if you can learn

> anything from it, i.e. from the non-native ( Java ) part.

> 4) look on the internet --- developer's forums etc --- if somebody has

> already had the same idea / need as you, and developed something

> 5) contact Colin Plum and ask him directly.

since version 1.2. Since then, BigInteger has been implented in pure Java.

If you use the free Kaffe JVM, it can be compiled to use the GMP

library for BigInteger. You need to both compile with this and enable

it at runtime with a command-line switch. Still, there's no API to have

BigInteger exponents.

In any case, BigInteger represents its bits as an int[] array. This

limits the size of the numbers that can be represented to about

68 billion digits, or possibly less.

But Sun's algorithms are horrible--they only use the most naive

O(n^2) algorithm for multiplication, and equally horrible algorithms for

radix conversion and exponentiation, so your program would be horribly

time-bound. For example, it takes about 16 hours just to convert one of

the larger Mersenne numbers, about 2^13000000, (which is *way, way*

smaller than the 2^2147483647 limit that you're complaining about) to

decimal on my computer. The exponentiation takes horribly long unless

you write your own bit-shifting algorithms to fix Sun's inadequacies too.

In short, if you're going to use numbers that big, you're going to

have to write your own library. Or try Kaffe. NB: make sure you

compile Kaffe with the option that intermediate numbers are allocated on

the heap, not the stack, 'cause your stack isn't gigabytes in size.

--

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

That'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);

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