asked on

big numbers when doing maths

If I want to do a^b (a to the power of b), and if the result is too big, my long integers cannot take it. What can I do about it?

Infact, I'm doing a prime number test:
(a^((p-1)/2)) % p. so in general the result should be a very small number. ie. 1 ....

but when (a^(p-1)/2) is calculated, it's already too big. I believe there should be a mathematical way to around it but I don't know......

Yam

griessh

There are libraries for large integers. How about http://www.codeproject.com/cpp/largenumber.asp.

======
Werner

griessh

I hate when that happens ....

http://www.codeproject.com/cpp/largenumber.asp

======
Werner

YamSeng

ASKER

what about solving the problem with maths?

Yam

0xDEADBEEF

Try ((a%p)^((p-1)/2)) % p, I think that should work.

ASKER CERTIFIED SOLUTION

ozo

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

YamSeng

ASKER

I found the solution now.

ie for a^(b-1/2)p

I just need to calculate

(a mod p)*(a mod p)*......for ((b-1)/2)times

Then in the end, mod p again for the final result.

Mathematically proven.

I'm not sure about ozo's answer.....is it similar to mine?

if yes, I'll award you.

Cheers!
Yam

ozo

Similar, but you only need to multiply log((b-1)/2) times

YamSeng

ASKER

hmm....yours seems to be a recursive function. I've thought of doing that initially, but it just seems to me as too difficult....(I hate recursive functions!)

Thanks

ozo

//I think it's simpler to understand as a recursive function,
//But it can also be done non-recursively:
long powmod(long a, long p,long m){
long i;
for( i=1; p; p>>=1 ){
if( p&1 ){
i *= a;
i %= m;
}
a *= a;
a %= m;
}
return i;
}

YamSeng

ASKER

but the performance would be slower right? coz it's no longer log((b-1)/2) times ?

ozo

The performance is the same for the recursive and itterative versions of the powmod function above.
One just goes left to right instead of right to left.

YamSeng

ASKER

ozo,

1 thing about right shifting. >> . I've tried right shifting (previously) and found that sometimes when you right shift, 1 bit which is added to the left most is 1 or 0. It's inconsistent. But for left shifting, it's always 0 appended.

But I think there should be a way to ensure consistency for left shifting right?

Yam