Algorithms
Fast Exponentiation
O(log n) time — each step cuts the exponent in half, so even huge exponents finish in a handful of multiplications · O(log n) space for the recursive calls (O(1) if you write it as a loop).
The idea, in plain English
Imagine folding a piece of paper in half again and again. Each fold doubles the number of layers, so you reach a huge number of layers in just a few folds, instead of adding one layer at a time. Fast exponentiation computes powers (a number multiplied by itself repeatedly) the same way. Instead of multiplying the base number by itself n times in a row, it repeatedly squares a smaller result, cutting the exponent in half at each step.
How it works
- 1If the exponent is 0, the answer is 1. This is the base case, the simplest input where you stop.
- 2If the exponent is even, compute the base raised to half the exponent, then square that result.
- 3If the exponent is odd, compute the base raised to one less than the exponent, which is now even, the same way. Then multiply by one more base.
When you'd use it
Use it to compute large powers quickly — modular exponentiation in cryptography (like RSA), fast matrix powers, or any place where you would otherwise multiply the same number hundreds of times.
Common beginner mistakes
- Forgetting the odd-exponent case and only handling even ones. This silently gives wrong answers for odd powers.
- Computing the base raised to half the exponent twice, instead of computing it once and squaring it. This throws away the entire speed advantage.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
2^10 = 1024
3^13 = 1594323See it in motion
Compute 5^8. In binary, 8 = 1000. Start the result at 1 and the base at 5.
Not sure this is the right topic? See the learning paths → or where this leads →