- Faysal,

there is of course the .modPow( BigInteger _exponent, BigInteger _modulus )

method, but that may not help you very much if you want to use a true

exponentiation without modulus.

What you want is a public BigInteger .pow( BigInteger _exponent ) method,

right ?

You might want to investigate different possibilities:

1) bit-shifting, either in C/C++ or Java; this goes down quite a bit to the

basics, but could provide the fastest implementation. Be prepared for blood,

sweat, tears, and swearing

2) take Colin Plum's source code, study it closely, and use to implement

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.

As for myself, I would start with 3, then 4, investigate upon 2, and then

decide about 1. In a desperate case, I would consider option 5.

I am keeping myself available for more help.

JanOn 8/5/05, fyatim <fyatim@...> wrote:

>

> Jan Van Oort,

>

> Thanks for you quick and clear answer.

>

> NetBeans IDE 4.0 is the Integrated development tool from SUN based on Java

> J2SDK 1.4.

>

> My problem is that the method BigInteger.pow(int) uses an integer as

> exponent, and I need to have some thing like BigInteger.pow(BigInteger).

> The value of the exponent limited to 2^31 -1 is not big enough..

>

> Have you any solution ???

>

> Thanks

>

> Faysal

>

> ------------------------------

>

> *From:* primenumbers@yahoogroups.com [mailto:primenumbers@yahoogroups.com]

> *On Behalf Of *Jan van Oort

> *Sent:* Friday, August 05, 2005 3:23 PM

> *To:* fyatim

> *Cc:* primenumbers@yahoogroups.com

> *Subject:* Re: [PrimeNumbers] big numbers library

>

> Faysal,

> "IDE 4.0 ??" What does that mean ?

> Forte for Java ? For C++ ? Sun Studio ?

> It it's Java you're programming in, I can help you on BigInteger issues...

>

> although it sounds strange to me that the "exponent is not enough", you

> probably mean "the exponent is not big enough".

> The biggest power to which you can raise a java.math.BigInteger by calling

>

> the .pow( int _pow ) method is Integer.MAX_VALUE, which is 2^31 - 1, i.e.

> 2147483648. Knowing that the maximum value of a BigInteger itself is

> theoretically unlimited ( see the constructor BigInteger( byte[] _val ),

> I donot see where - if you agree to calculate intermediate results for

> power-raising operations - the limits are ?

> If you are working in C / C++, consider using Coling Plumb's BigNum

> library

> ( also used in java.math.BigInteger and java.math.BigDecimal ). And of

> course, nothing keeps you from doing your BigInteger operations C / C++,

> compiling into a shared library, and calling that one from your Java

> programs.

> That should keep you going for a while.

> Jan van Oort

>

> On 8/5/05, fyatim <fyatim@...> wrote:

> >

> >

> >

> > Hi all,

> >

> > I'm using IDE 4.0 of Sun and I need to "power" some BigInteger numbers

> > with

> > big exponents (the integer exponent is not enough).

> >

> > Is there any way to do this ???

> >

> > If not, do you know any library that can help doing this ??

> >

> > Thanks in advance

> >

> > Faysal

> >

> >

> >

> >

> >

> > [Non-text portions of this message have been removed]

> >

> >

> >

> > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> > The Prime Pages : http://www.primepages.org/

> >

> >

> >

> >

> >

> > SPONSORED LINKS

> > Music theory<

> http://groups.yahoo.com/gads?t=ms&k=Music+theory&w1=Music+theory&w2=Mathematics+and+computer+science&w3=Theory+of&c=3&s=71&.sig=Y7Fbv0ctFics_2Z_SKrLqg>

> Mathematics

> > and computer science<

> http://groups.yahoo.com/gads?t=ms&k=Mathematics+and+computer+science&w1=Music+theory&w2=Mathematics+and+computer+science&w3=Theory+of&c=3&s=71&.sig=nEe5rsXqmLLRS_bFj0ypUQ>

> Theory

> > of<

> http://groups.yahoo.com/gads?t=ms&k=Theory+of&w1=Music+theory&w2=Mathematics+and+computer+science&w3=Theory+of&c=3&s=71&.sig=9JOCDci6NPxRyTLqK08kMg>

>

> > ------------------------------

> > YAHOO! GROUPS LINKS

> >

> >

> > - Visit your group "primenumbers<

> http://groups.yahoo.com/group/primenumbers>"

> > on the web.

> > - To unsubscribe from this group, send an email to:

> > primenumbers-unsubscribe@yahoogroups.com<

> primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe<http://primenumbers-unsubscribe@yahoogroups.com/?subject=Unsubscribe>

> >

> > - Your use of Yahoo! Groups is subject to the Yahoo! Terms of

> > Service <http://docs.yahoo.com/info/terms/>.

> >

> >

> > ------------------------------

> >

>

>

>

> --

>

> Non sunt multiplicanda entia praeter necessitatem

>

>

> [Non-text portions of this message have been removed]

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

>

> ------------------------------

>

> YAHOO! GROUPS LINKS

>

>

> - Visit your group "primenumbers<http://groups.yahoo.com/group/primenumbers>"

> on the web.

> - To unsubscribe from this group, send an email to:

> primenumbers-unsubscribe@yahoogroups.com<primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe>

> - Your use of Yahoo! Groups is subject to the Yahoo! Terms of

> Service <http://docs.yahoo.com/info/terms/>.

>

> ------------------------------

>

--

Non sunt multiplicanda entia praeter necessitatem

[Non-text portions of this message have been removed] - 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