Some programming problems require us to find the value of *base*^*power* modulo some positive prime number *M* (*power*>=0).

If you had to find the value of ( *base*^*power* ) % *M*, how would you do it??

The easiest method that comes to mind is iterating a loop.

long long findPower(long long base,long long power,long long M) { long long ans=1; int i; for(i=1;i<=power;i++) ans=(ans*base)%M; return ans; }

The above method is simple but not at all efficient. For values of *power* around 10^8 or more, this method will take a lot of time to run. If you increase the value of *power* to 10^16, you’ll pass out from college before the computation ends! Increase it to around 10^25, the sun will become a Red Giant and swallow Earth before the value is computed!!

But why would we need to find such large values :P. Yeah that’s a valid question; but it shouldn’t stop us from learning a better algorithm!

There is a much better algorithm than the linear one described above, which is the topic of this post.

I’ve already introduced **Binary Exponentiation** as a part of an earlier post. But, I need to formalize it for the next post.

Binary Exponentiation is based on the idea that,

to find *base*^*power*, all we need to do is find *base*^(*power*/2) and square it. And this method can be repeated in finding *base*^(*power*/2) also.

Suppose that we need to find 5^8.

5^8=5^4 * 5^4

5^4=5^2 * 5^2

5^2=5 * 5

The number of steps required to find 5^8 has been reduced from 8 to just 3.

As another example, consider 8^51

8^51 = 8^25 * 8^25 * 8

8^25 = 8^12 * 8^12 * 8

8^12 = 8^6 * 8^6

8^6 = 8^3 * 8^3

8^3 = 8 * 8 * 8

If we used the linear algorithm, we would have required 27 steps. But, using this awesome trick we required roughly 5 steps.

In a general sense, we require steps in the order of **O(logbase2 n)**

This algorithm can be implemented recursively as well as iteratively.

**RECURSIVE IMPLEMENTATION:**

long long fastPower(long long base,long long power,long long M) { if(power==0) return 1; if(power==1) return base; long long halfn=fastPower(base,power/2,M); if(power%2==0) return ( halfn * halfn ) % M; else return ( ( ( halfn * halfn ) % M ) * base ) % M; }

**ITERATIVE IMPLEMENTATION:**

long long int fastPower(long long base,long long power,long long M) { long long result=1; while (power>0) { if (power%2==1) result = (result*base)%M; base = (base*base)%M; power/=2; } return result; }

The iterative implementation can be a little tricky to understand. Take a pen and paper and trace the values of variables through the iterations. That’s an effective way to understand and convince yourself.

The iterative version runs a little faster that the recursive version.

Binary exponentiation will find the value of *base*^(10^25) in about 85 steps only.. Now that’s really cool…

The maximum number of multiplications that are required to compute *base* ^ *power* is 2 X FLOOR(logbase2 (*power*)). Think why 😛

CAN YOU PLEASE EXPLAIN WHAT CAN BE THE VALUE OF M IN THIS QUESTION.AS TAKING VALUE OF M=13,BASE=5,POWER=3 GIVES THE OUTPUT=1 IN CASE OF ITERATIVE APPROACH.?

The value of M should be any prime number.

The output of (5^3)%13 will be 8 no matter which approach is used to compute it.

Shouldnt the last line of iterative implentation say result%M

Actually, result will already be less than M when control reaches that line. So no use in performing modulo operation again.

Excellent !!!