# Fast Power Algorithm

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](https://en.wikipedia.org/wiki/Exponentiation_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.