Follow

Follow

# Fast Power Algorithm

## A fast and efficient method to calculate exponents

Amr Saber
·Dec 5, 2022·

When we need to calculate the value of some number `base` raised to the power of another number `exp` we can do so naively using the following algorithm:

``````def power(base, exp):
result := 1
for i = 1 to exp:
result *= base
return result
``````

The problem with this algorithm is that it is very slow, its complexity is `O(exp)` which is linear in the value of the exponent.

To solve this problem, there is a simple algorithm called Power By Squaring or just "Fast Power" algorithm.

It is built on the observation that we can manipulate the exponentiation into a sequence of squaring, here are some examples:

• \( a^4 = (a^2)^2 \) -- Can be calculated in 2 steps (instead of 4)
• \( a^8 = ((a^2)^2)^2 \) -- Can be calculated in 3 steps (instead of 8)
• \( a^3 = a * a^2 \) -- Can be calculated in 2 steps (instead of 3)
• \( a^5 = a * (a^2)^2 \) -- Can be calculated in 3 steps (instead of 5)
• \( a^{12} = ((a * a^2)^2)^2 \) -- Can be calculated in 5 steps (instead of 12)

For this we can write a simple recursive algorithm:

``````def fast_power(base, exp):
// Base conditions
if exp == 1: return base
if exp == 0: return 1

// The recursive definitions
if exp % 2 == 0: return fast_power(base * base, exp / 2)
return base * fast_power(base, exp-1)
``````

The sense of this algorithm is the following:

• If you can split the current power in 2, then you can factor out the 2, calculate square the base, and now you have half the power remaining. i.e. \( a^{2e} = (a^2)^e \)
• If you can't split the current power in 2, then subtract 1 of that power, multiply that 1 manually, and recurse (which will lead you to the first case). i.e. \(a^{2e+1} = a * a^{2e} \)

And of course we need the 2 base conditions to specify when we are going to end our loop.

Now, thanks to halfing the exponent on each step, the complexity of this algorithm is `O(log(exp))`. Which is much better than what we had before.

### One last bit

In problem solving we are often required to calculate a huge exponent and get the result module some constant. knowing that the modulus operator can be distributed on multiplication, i.e. `(a * b) % m = ( (a % m) * (b % m)) % m`, we can update the fast power algorithm to accomodate for that:

``````def fast_power(base, exp, mod):
// Base conditions
if exp == 1: return base
if exp == 0: return 1

// The recursive definitions
if exp % 2 == 0: return fast_power((base * base) % mod, exp / 2, mod)
return (base * fast_power(base, exp-1, mod)) % mod
``````

### Conclusion

In conclusion, the Fast Power algorithm is a fast and efficient way to calculate exponents with a complexity of O(log(exp)). It can also be modified to calculate the result modulo a constant if needed. You can now use this algorithm to improve the performance of your code when dealing with large exponents.

If you think this article was useful, leave me a reaction and/or a comment. If you think people in your circle can make use of this article feel free to share it.