Programming helps us in solving repetitive tasks by using loop constructs. However, sometimes, our loops may run forever! Let’s discuss one such example.
Table of Contents
- How to find A raised to the power B?
- Brute force Python implementation
- Exponentiation by Squaring or Binary Exponentiation
- Efficient Python implementation to find base raised to the power
- Efficient C++ implementation to find exponent raised to a power
How to find A raised to the power B?
a to itself,
b times. That is,
a^b = a * a * a * ... * a (
b occurrences of
A simple python implementation of that would be:
Notice that the answer to
2^100 is way too large to fit in
int data-type of other languages. To be fair, let’s modify our code to print the result modulo
1000000007. You’d ask why
1000000007? There’s a long story behind that, read it here. TLDR, we want to contain the result within the range of 32 bit
Brute force Python implementation
By the way, in Python we could have simply used
** operator to find
a**b. However, I just wanted to implement the code so that we can easily port the code in other languages.
Now, try and call that function for
a = 2 and
b = 1000000000 i.e.
iterative_power(2, 1000000000). The code will keep running forever. If we analyze the code, Time Complexity is O(power) or in general terms O(N) where
So how do we find the base raised to the power for large numbers, as large as a billion! There’s an algorithm for that, it’s called Exponentiation by Squaring, fast power algorithm. Also known as Binary Exponentiation.
Exponentiation by Squaring or Binary Exponentiation
Exponentiation by Squaring helps us in finding the powers of large positive integers. Idea is to the divide the power in half at each step.
Let’s take an example:
Effectively, power is divided by 2 and base is multiplied to itself. So we can write
3 ^ 10 = 9 ^ 5.
Now, our problem is to find
9 ^ 5
Effectively, when power is not divisible by 2, we make power even by taking out the extra 9. Then we already know the solution when power is divisible by 2. Divide the power by 2 and multiply the base to itself.
Now our problem is to find
(81 ^ 2) * 9
Finally, we have our solution
3 ^ 10 = (6561 ^ 1) * 9 = 6561 * 9 = 59049
Let’s try and implement this algorithm in Python.
Our above code is a bit repetitive and can be simplified. We also have to make changes to keep the final result less than
We will common out the code that is present in both
else. Also, the two statements
power = power - 1 and
power = power / 2 can be simply merged into one like
power = power / 2, because we are performing integers division.
Efficient Python implementation to find base raised to the power
See how we can use Fast Power Algorithm to find Modular Multiplicative Inverse of a number.
Efficient C++ implementation to find exponent raised to a power
A lot of competitive programmers prefer C++ during the contest. So a C++ implementation would always be there for any of my post targeting competitive programmer.
Time Complexity of the above implementation is O(log power) or we can O(log N) (where
power). But how? Notice that we keep dividing the value of power in half in each iteration. Please refer the article that discusses Time Complexity or Order of Growth of various types.
Got a burning question you might wanna get answered? Ask it in the comments.