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):
if exp == 1: return base
if exp == 0: return 1
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):
if exp == 1: return base
if exp == 0: return 1
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.
