Binary Exponentiation

Fast exponentiation using binary representation of the exponent in O(log n) multiplications.

[Algebra]|

Jul 9, 2026

|explanatory_notes.md|

#binary-exponentiation#power#modular#fast-power

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

ll binpow(ll a, ll b, ll m) {
    if (m == 1) return 0;
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = (__int128)res * a % m;
        a = (__int128)a * a % m;
        b >>= 1;
    }
    return res;
}

25 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Binary Exponentiation

Compute $a^n$ in $O(\log n)$ multiplications by decomposing the exponent into its binary representation:

a^n = \prod_{i:\, b_i = 1} a^{2^i}

How It Works

Start with

\text{result} = 1

While

n > 0

: if the lowest bit of

n

is 1, multiply result by current base

Square the base and right-shift

n

each iteration

For the modular version, reduce mod

m

after every multiplication

When to Use

Computing

a^n \bmod m

for very large

n

Matrix exponentiation for Fibonacci / linear recurrences

Permutation exponentiation — applying a permutation

k

times

Counting walks of length

k

via adjacency matrix powers

Complexity

Time —

O(\log n)

multiplications

Space —

O(1)