# Fast Power Algorithm - Exponentiation by Squaring - C++ and Python Implementation

We know how to find 2 raised to the power 10. But what if we have to find 2 raised to the power very large number such as 1000000000? We discuss how to find solution to such a problem using an fast, efficient algorithm

May 18, 2013 - 9 minute read -

Programming helps us in solving repetitive tasks by using loop constructs. However, sometimes, our loops may run forever! Let’s discuss one such example.

## How to find A raised to the power B?

We multiply `a` to itself, `b` times. That is, `a^b = a * a * a * ... * a` (`b` occurrences of `a`). 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 `int`.

## Brute force Python implementation

By the way, in Python we could have simply used `**` operator to find `a^b` like `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 `N` is `power` or `b`.

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 `1000000007`. We will common out the code that is present in both `if` and `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 `N` is `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.