testUser44's blog

By testUser44, history, 13 months ago, In English

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 b is even: a^b = (a^(b/2)) * (a^(b/2))
  • If b is 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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?