Fast exponentiation

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Compute 2¹⁰. By hand you multiply by 2, ten times: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. That is 9 multiplications and it works fine. Now compute 3^{1,000,000,000} modulo some number, which is what a programming problem will ask. A billion multiplications is a billion steps, far too slow. The exponent itself is the problem, so the exponent is what we must shrink.

Here is the one observation that does it. Multiplying by 2 ten times is the same as multiplying by 4 five times, and multiplying by 4 five times is 4 · (16)². Each time you square the base you can halve the exponent:

x^2k = (x²)^k, and x^2k+1 = x · (x²)^k

Build the structure, one piece at a time

There is no data structure here beyond three variables, and the "structure" is the binary spelling of the exponent. Write 10 in binary: 1010, which means 8 + 2. So 2¹⁰ = 2⁸ · 2². The powers 2¹, 2², 2⁴, 2⁸ are each the square of the one before, so we can produce them one squaring at a time and multiply in the ones whose bit is set.

Keep three things: result (starts at 1), base (starts at 2) and exp (starts at 10). Each round looks at the lowest bit of exp, squares base, and shifts exp right by one bit:

Four rounds instead of nine multiplications, and the gap widens enormously for big exponents. If the problem asks for the answer modulo m, take the remainder after every multiplication; the numbers then never grow beyond m².

Why it is correct

The invariant is that at the start of every round

result · base^exp = xⁿ

At the beginning it is 1 · 2¹⁰, true. Suppose it holds and exp is even, say 2k. Squaring the base and halving the exponent gives result · (base²)^k, which equals result · base^2k, the same value. If exp is odd, 2k + 1, we first move one factor of base into result, leaving result · base · base^2k, and then square and halve as before. So the product never changes. When exp reaches 0 the product is result · 1, so result is the answer.

Why it is fast

Each round removes one bit from exp, so the number of rounds is the number of bits in n, which is ⌊log₂ n⌋ + 1. Each round does at most two multiplications (one square, possibly one multiply into result). For n = 10⁹ that is 30 rounds and at most 60 multiplications, against a billion the slow way. That is O(log n).

The same loop works for anything that can be multiplied associatively: numbers modulo m, and matrices. Raising a 2×2 matrix to a power this way computes Fibonacci numbers in logarithmic time, the subject of the matrix exponentiation pattern.

How to recognise it in an interview

Look for an exponent that is huge (10⁹ or more), a "modulo 10⁹ + 7" in the statement, or a count that multiplies the same factor many times. Say: "the exponent is too big to loop over, so I will square the base and halve the exponent, which is logarithmic in n".

Pow(x, n) is the pattern itself, with the extra care of a negative n (invert the base) and the most negative integer. Count Good Numbers reduces to 5^⌈n/2⌉ · 4^⌊n/2⌋ modulo 10⁹ + 7, two fast powers and one multiplication.

02The idea in one line

Square the base and halve the exponent; multiply in when the bit is set.

Reach for it when: pow(x, n), count good numbers, modular power, matrix power (fibonacci).

Cost: O(log n) time.

03The walk-through, step by step

The video works one example: Pow(2, 10) by squaring. These are its captions in order, so you can follow without the video or check a step you missed.

1. 10 = 1010: write the exponent in binary
2. low bit is 0: result unchanged
3. square the base → 4, shift the exponent → 5
4. low bit is 1: result = result · base = 4
5. square the base → 16, shift the exponent → 2
6. low bit is 0: result unchanged
7. square the base → 256, shift the exponent → 1
8. low bit is 1: result = result · base = 1024
9. square the base → 65536, shift the exponent → 0
10. exp is 0: result = 1024 = 2¹⁰
11. One squaring per bit: O(log n) multiplications; same loop for modular power and matrix power

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Math: GCD and number theory, Digit-by-digit arithmetic, Random pick and reservoir sampling, Coordinate geometry with hashing.