### 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

So my pseudo code function is

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

previous=power(n,k/2)%M