Why do we need Binary Exponentiation?
In competitive programming, we often need to calculate expressions like a^b. A simple approach might be to use pow(a, b) or a loop, but both are inefficient or unsafe.
Let’s understand why and how we can improve it.
1. The Basic Approach
We can multiply a by itself b times:
int a = 2, b = 13, ans = 1;
const int M = 1e9 + 5;
for(int i = 0; i < b; ++i) {
ans *= a;
ans %= M; // To avoid overflow
}
This works, but its time complexity is O(b) — very slow when b is large (for example, b = 10^9).
2. The Problem with pow() Function
You might think of using the built-in pow() function:
pow(a, b);
But this is not reliable for competitive programming. pow() works with floating point numbers, which cannot store large integers with 100% accuracy. It may give wrong results for big powers.
3. The Idea Behind Binary Exponentiation
We can make it faster using the Divide and Conquer idea.
Instead of computing a^b directly, notice these patterns:
- If
bis even:a^b = (a^(b/2)) * (a^(b/2)) - If
bis odd:a^b = a * (a^(b/2)) * (a^(b/2))
Each time we divide b by 2, so the time complexity becomes O(log b).
4. Step-by-Step Example
Let’s take 2^16:
2^16 = 2^8 * 2^8
2^8 = 2^4 * 2^4
2^4 = 2^2 * 2^2
2^2 = 2^1 * 2^1
We only need 4 steps instead of 16 multiplications. That’s why it’s called Binary Exponentiation — we keep halving the power (like binary bits).
5. Recursive Implementation
Here’s the clean recursive version of Binary Exponentiation:
#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 5;
int binExpRecursion(int a, int b) {
if (b == 0) return 1;
int res = binExpRecursion(a, b / 2);
if (b & 1) {
return (a * (1LL * res * res % M)) % M;
} else {
return (1LL * res * res) % M;
}
}
int main() {
int a = 2, b = 13;
cout << binExpRecursion(a, b) << endl;
}
6. Working Explanation
When b = 13, recursion expands like this:
f(2,13) = 2 * f(2,6) * f(2,6)
f(2,6) = f(2,3) * f(2,3)
f(2,3) = 2 * f(2,1) * f(2,1)
f(2,1) = 2 * f(2,0) * f(2,0)
At the base case, f(2,0) = 1.
So it combines results from the bottom up efficiently, doing only log(b) recursive calls.
7. Complexity
- Time Complexity: O(log b)
- Space Complexity: O(log b) (for recursion stack)
8. Modular Arithmetic Note
We take modulo M (like 1e9 + 7 or 1e9 + 5) to prevent overflow and keep numbers within bounds.
This makes it safe for problems where you need to compute results modulo a large prime.
Summary
| Concept | Formula | Explanation |
|---|---|---|
| Even Power | a^b = (a^(b/2)) * (a^(b/2)) | Divide into two equal halves |
| Odd Power | a^b = a * (a^(b/2)) * (a^(b/2)) | Multiply once more by a |
| Base Case | b == 0 → return 1 | Anything raised to 0 is 1 |
| Complexity | O(log b) | Much faster than O(b) |
Binary exponentiation is one of the most important building blocks in number theory and modular arithmetic. Learn it once, and you’ll use it everywhere.








