Solved

# big numbers when doing maths

Posted on 2002-03-25
Medium Priority
267 Views
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
0
Question by:YamSeng
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 5
• 4
• 2
• +1

LVL 11

Expert Comment

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

======
Werner
0

LVL 11

Expert Comment

ID: 6894891
I hate when that happens ....

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

======
Werner
0

LVL 1

Author Comment

ID: 6895468
what about solving the problem with maths?

Yam
0

Expert Comment

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

LVL 84

Accepted Solution

ozo earned 80 total points
ID: 6895957
#include <stdlib.h>
#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;
}
0

LVL 1

Author Comment

ID: 6896168
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.

if yes, I'll award you.

Cheers!
Yam
0

LVL 84

Expert Comment

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

LVL 1

Author Comment

ID: 6898540
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
0

LVL 84

Expert Comment

ID: 6901823
//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;
}
0

LVL 1

Author Comment

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

LVL 84

Expert Comment

ID: 6904477
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.
0

LVL 1

Author Comment

ID: 6904814
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
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their waâ€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Botâ€¦
###### Suggested Courses
Course of the Month15 days, 4 hours left to enroll