On this page
Description
Binary exponentiation computes x^n with about 2 log2(n) multiplications instead of n - 1. It squares the base over and over, and multiplies it into the result wherever n's binary form has a 1 bit. With a modulus applied at every step, it computes huge powers like a^b mod m, the operation at the heart of RSA and Diffie-Hellman. The same loop raises matrices to powers, which jumps a linear recurrence like Fibonacci n steps ahead.
We'll go from simple to more technical:
- The pattern: square the base, halve the exponent, multiply in on 1 bits.
- A second flavor: modular exponentiation.
- Where repeated squaring runs in production (cryptography).
- The edge cases around it: negative exponents,
Integer.MIN_VALUE, overflow.
The approach
Multiplying x by itself n times is O(n), far too slow when n is in the billions. Instead, write n in binary. 13 is 1101, which means 8 + 4 + 1. So 3^13 = 3^8 × 3^4 × 3^1. Squaring gives those pieces cheaply: 3, 9, 81, 6561 are 3^1, 3^2, 3^4, 3^8. Read the bits of n from the lowest one up. On a 1 bit, multiply the current piece into the result. Then square the piece and drop the bit.
Computing 3^13:
| Exponent left (binary) | Lowest bit | Current piece | Result after this step |
|---|---|---|---|
| 1101 | 1: multiply in | 3 | 3 |
| 110 | 0: skip | 9 | 3 |
| 11 | 1: multiply in | 81 | 243 |
| 1 | 1: multiply in | 6,561 | 1,594,323 |
Four rounds instead of twelve multiplications.
Java
double result = 1.0;
double current = x;
long exponent = n; // use a wider type - negating Integer.MIN_VALUE overflows an int
while (exponent > 0) {
if ((exponent & 1) == 1) result *= current; // this bit of n is set
current *= current; // current becomes x^(2^k) each iteration
exponent >>= 1;
}
Python
result = 1.0
current = x
exponent = n # n >= 0 here: see "Negative exponents" below
while exponent > 0:
if exponent & 1: # this bit of n is set
result *= current
current *= current # current becomes x^(2^k) each iteration
exponent >>= 1
For a negative n, compute x to the power |n| with the same loop, then take 1 divided by the result.
A second flavor: modular exponentiation
The same loop with integers and a modulus computes (base^exp) mod m. That's the core step behind RSA and Diffie-Hellman:
Java
long result = 1 % m;
long b = base % m;
while (exp > 0) {
if ((exp & 1) == 1) result = (result * b) % m;
b = (b * b) % m;
exp >>= 1;
}
Python
result = 1 % m
b = base % m
while exp > 0:
if exp & 1:
result = result * b % m
b = b * b % m
exp >>= 1
# Python's built-in pow(base, exp, m) does exactly this
The one new rule: reduce % m after every multiplication, not just at the end. A base squared a few times grows past what a 64-bit long can hold. Reducing at each step keeps every value below m. Then each product stays below m^2, which fits in a long for m up to about 3 × 10^9. Every modulus in this skill's questions is at most 10^9. For bigger moduli even one product overflows, so use BigInteger.modPow or a 128-bit multiply built on Math.multiplyHigh.
Where you'll see it
Cryptography depends on it. RSA and Diffie-Hellman compute a^b mod m with exponents hundreds of digits long. That's only possible in O(log b) multiplications, not O(b).
Which tool for which job?
| You need | Use |
|---|---|
| x^n for a large integer n | binary exponentiation, O(log n) |
| a^b mod m | the same loop, reducing mod m after every multiplication |
| A modular inverse (m prime) | a^(m-2) mod m, or Python's pow(a, -1, m) |
| The n-th term of a linear recurrence | a matrix raised to the n-th power |
| A modulus near 10^18 in Java | BigInteger.modPow, or a 128-bit-safe multiply |
| A small fixed power (x^2, x^3) | just multiply |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Ignoring negative exponents | a wrong answer | compute 1 / x^n for -n |
Negating Integer.MIN_VALUE | it stays negative | widen to long first |
| Reducing mod m only at the end | overflow in Java; huge, slow numbers in Python | reduce after every multiplication |
(a * b) % m with m near 10^18 in Java | the product overflows long | BigInteger or Math.multiplyHigh |
Forgetting result = 1 % m when m is 1 | returns 1 instead of 0 | start from 1 % m |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. The loop only runs while exponent > 0. What happens for a negative n if nothing else is done?
Show answer
The loop never runs, so the function returns 1.0, which is wrong for any negative n. Handle it separately: compute x to the power |n|, then take the reciprocal.
2. Why reduce % m after every multiplication, not once at the end?
Show answer
Repeated squaring grows very fast. A few squarings can pass what a 64-bit long holds, and the value silently wraps. Reducing after each multiplication keeps every value below m, so each product stays below m^2.
3. Why does the same loop work for (base^exp) mod m and for plain x^n?
Show answer
Both rest on the same fact: the exponent is a sum of powers of two, so the answer is a product of squarings. Only the multiplication changes, from doubles to integers mod m. The loop stays the same.
Key takeaways
- x^n is the product of x^(2^k) for every 1 bit k of n. Repeated squaring makes those O(log n) pieces.
- Handle a negative exponent separately: compute the positive power, then the reciprocal.
- Negating
Integer.MIN_VALUEoverflows. Widen tolongfirst. - For a^b mod m, reduce after every multiplication.
- Matrix exponentiation uses the same loop with matrix multiplication.