Efficiently Calculate (a^b)%M

Have you ever had a problem calculating a^b where a and b could be very very large and you have to calculate just the answer modulo M????

So here is the solution for you.

Of Course first approach that comes in our mind is greedy approach that is multiply b times a through a for loop each time doing modulo operation.But what if k is 10^18 and so????

Here it takes much time .Of Course you could not calculate with traditional pow(a,b) library function . Because it uses logarithmic approach and for calculating large power(10^9,10^18) it will not work properly.

So What to do Now???

I have a solution that can be done in O(logN) time where N is b here.

So lets see now.

Lets say you have to calculate 9^16 what you would do to calculate this on pen and paper???

One can use greedy approach mentioned earlier but smarter approach would be

just calculate 9^8 and suppose we got value as K.

then our answer would be K*K; (Time got reduced to half)

In same way calculate 9^8 from 9^4 and so on……

you will get answer in O(logN) time.

Yaah that’s only our approach.

One thing to note when in a^b b is odd calculate power(a^[b/2])) where [b/2] denotes integer part.

and then multiply it extra by a;

ex… to calculate 9^17 calculate 9^8 and lets its value is K

Then answer is K*K*9;

So my pseudo code function is

power(n,k)%M
{
if(k==1)
return n%M;

previous=power(n,k/2)%M
answer=(previous*previous)%M;
if(k%2!=0)
{
answer*=n;
answer%=M;
}
return answer;
}

So here I complete.

If you have any doubts please comment so I would also able to know

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s