Binary Exponentiation
Read exponent bits, square the base each round, and multiply only when the current bit is set.
Core idea
Decompose the exponent into powers of two. Repeatedly square the base, and multiply the result only for set bits in the exponent.
Read the visualization
Exponent bits disappear from least significant to most significant. The base block squares every round, while result blocks grow only on multiply steps.
Compute 313, exponent 13 = 11012
Result = 1 = 1
Initialize the result to one and represent the exponent by its binary bits.
1function fastPow(a: number, n: number): number {
2 let result = 1;
3 let base = a;
4 while (n > 0) { // from mul digit to mul digit mul n mul
5 if (n & 1) result *= base; // current digit as 1 → mul current square multiply into result
6 base *= base; // base square: a → a² → a⁴ → a⁸
7 n >>= 1; // right skip, skip down one digit
8 }
9 return result;
10}
compute3^13
binary exponent1101₂
result1
1 / 6
Complexity and tradeoffs
Time: O(log exponent). Space: O(1). Modular reduction can be applied after every multiplication without changing the recurrence.
Invariant: At every round, accumulated result times current base to the remaining exponent equals the original requested power.
Where it fits
Binary exponentiation supports modular powers, matrix recurrences, permutation powers, and any associative operation with an identity element.