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

6 comments

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

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