Large numbers calculation..!

general
,
1

When we calulate very large number after multipication and then storing it in array(suppose 10 raised to the power 32) . now if i want to find the modulo (1000000007) of this number , then how can i find it…?

2

In such questions, we usually avoid storing the number in an array as it becomes difficult to perform further operations on it (eg the modulo operation), though its not impossible. It’s just not the way most people prefer doing it.

For finding p^q in a fast way we can use the concept of [Exponentiation by squaring][1]. It uses only O(lgq) multiplications.
Code snippet for Exponentiation by squaring -

while (q != 0) {
    if (q % 2 == 1) {    // q is odd
        r *= p;
        q--;
    }
    p *= p;
    q /= 2;
}

print r;

If you want to find a^b modulo M where a,b are some really big numbers and M is some given constant, we can utilize the method of exponentiation by squaring and [Properties of Modulo Operation ][2] in a function like this -

long long int pow(long long int a, long long int b, long long int MOD){

long long int x=1,y=a;
while(b > 0){
    if(b%2 == 1){
           x = ( x*y );
           if( x > MOD ) 
               x %= MOD;
    }
    y = ( y*y );
    if( y > MOD ) 
        y%=MOD;
    b /= 2;
}
return x;

}

What we do is that, instead of calculating the whole result and then performing the modulo operation we keep on performing the modulo operation on the intermediate results.
[1]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
[2]: http://stackoverflow.com/questions/5595517/properties-of-the-modulo-operation

3

okay, thanks @sakshichauhan… :slight_smile:

4

You have some mistakes. For example: it should be “if ( x >= MOD )”