Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 271
  • Last Modified:

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
0
YamSeng
Asked:
YamSeng
  • 5
  • 4
  • 2
  • +1
1 Solution
 
griesshCommented:
There are libraries for large integers. How about http://www.codeproject.com/cpp/largenumber.asp.

======
Werner
0
 
griesshCommented:
I hate when that happens ....

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

======
Werner
0
 
YamSengAuthor Commented:
what about solving the problem with maths?

Yam
0
The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

 
0xDEADBEEFCommented:
Try ((a%p)^((p-1)/2)) % p, I think that should work.
0
 
ozoCommented:
#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
 
YamSengAuthor Commented:
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
0
 
ozoCommented:
Similar, but you only need to multiply log((b-1)/2) times
0
 
YamSengAuthor Commented:
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
 
ozoCommented:
//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
 
YamSengAuthor Commented:
but the performance would be slower right?   coz it's no longer log((b-1)/2) times ?
0
 
ozoCommented:
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
 
YamSengAuthor Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

  • 5
  • 4
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now