With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

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

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

======

Werner

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

Thanks

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

}

One just goes left to right instead of right to left.

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

All Courses

From novice to tech pro — start learning today.

#include <iostream.h>

long powmod(long a, long p,long m){

long i;

i = 1;

if( p ){

i = powmod(a,p>>1,m);

i *= i;

i %= m;

}

if( p&1 ){

i *= a;

i %= m;

}

return i;

}

main(int argc,char *argv[]){

long a,p;

a = atol(argv[1]);

p = atol(argv[2]);

cout << powmod(a,(p-1)/2,p) << endl;

}