# Algorithm #11: Binary Exponentiation

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 😛

Advertisements

## 7 comments

1. nitin vashisth says:

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.?

1. abhinav92003 says:

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.

2. sarthakmunshi says:

Shouldnt the last line of iterative implentation say result%M

1. abhinav92003 says:

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

3. vikram says:

Excellent !!!

4. Anonymous says:

in last lines you says that max multiplications will be 2*(logbase2(power)) but i cant understand y we multiply by 2