Skip to content
Tutorials Center
My learning

Topics

Lesson 180 of 225 ยท Math and Bit Manipulation

Fast Exponentiation and Matrix Power

Compute powers in O(log n) with binary exponentiation in Python, add a modulus, then use matrix power to get Fibonacci numbers and linear recurrences fast.

How long does it take to compute x to the power n? The obvious loop multiplies n times. For n = 10**18 that is hopeless, yet competitive programmers compute such powers instantly. The trick is called binary exponentiation (or exponentiation by squaring), and it needs only about log2(n) multiplications.

The same idea works for anything you can multiply associatively, not just numbers. With matrices, it turns linear recurrences like Fibonacci into a power computation, giving the millionth Fibonacci number modulo a prime in a few dozen steps. This lesson builds all of it, counting multiplications so the speed-up is visible.

The naive way

To get x**n, multiply x by itself n - 1 times. Time O(n) multiplications.

TEXT
3^8 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3     7 multiplications

The squaring idea

Squares let you skip ahead. x^8 = ((x^2)^2)^2: three squarings instead of seven multiplications.

TEXT
3^1 = 3
3^2 = 9          (square the previous)
3^4 = 81         (square again)
3^8 = 6561       (square again)

What about exponents that are not powers of two? Write the exponent in binary. Each 1 bit says "include this square":

TEXT
13 = 8 + 4 + 1 = 1101 in binary
x^13 = x^8 * x^4 * x^1

So walk the bits of n from the lowest to the highest. Keep base = x^(2^i). If the current bit is 1, multiply it into the result. Then square base and shift to the next bit. It takes at most log2(n) + 1 squarings and as many extra multiplications: O(log n) time, O(1) space.

TEXT
x = 3, n = 13 (binary 1101), reading bits from the right
bit  base    result
 1   3       3          result *= 3
 0   9       3
 1   81      243        result *= 81   (3 * 81)
 1   6561    1594323    result *= 6561 (243 * 6561)
3^13 = 1594323
Python Binary exponentiation with a multiplication counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

(The last squaring in the loop is unused, so a tuned version can skip it. The count is still O(log n).)

A recursive version

The same idea recursively: x^n = (x^(n/2))^2 for even n, and x * x^(n-1) for odd n. The recursion depth is about log2(n), so it never comes close to Python's limit.

Python Recursive fast power

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compute half once. Writing fast_pow(x, n // 2) * fast_pow(x, n // 2) makes two calls per level and brings the cost back to O(n).

Modular exponentiation

When the answer is huge, problems ask for x**n % m. Reduce after every multiplication so numbers stay below m * m:

Python Power modulo m

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In real code just call the built-in pow(x, n, m), which does exactly this in C. See number theory for how it gives modular inverses (pow(a, -1, m)).

Matrix exponentiation

Squaring needs only two things: an associative multiplication and an identity element. Square matrices have both. Multiplying two k x k matrices takes O(k^3) operations, so a matrix power costs O(k^3 log n).

Why? Linear recurrences become matrices

The Fibonacci rule F(n+1) = F(n) + F(n-1) can be written as a matrix acting on a pair:

TEXT
| F(n+1) |   | 1  1 |   | F(n)   |
|        | = |      | * |        |
| F(n)   |   | 1  0 |   | F(n-1) |

Apply it n times and you get the matrix power:

TEXT
| 1 1 |^n   | F(n+1)  F(n)   |
| 1 0 |   = | F(n)    F(n-1) |

So F(n) is an entry of M**n, and fast exponentiation computes that in O(log n) matrix products. Each product of 2x2 matrices is a constant number of operations, so Fibonacci takes O(log n) arithmetic operations.

Comparison of Fibonacci methods

Method Time Space
Naive recursion exponential O(n) stack
Loop with two variables O(n) O(1)
Matrix power O(log n) multiplications O(1)
Python Fibonacci by matrix power

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here M**(n-1) has F(n) in its top-left corner, which is why fib uses n - 1.

Python Check matrix Fibonacci against a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Any linear recurrence

The idea scales: a recurrence that depends on the previous k values, with fixed coefficients, becomes a k x k matrix. For example, T(n) = T(n-1) + T(n-2) + T(n-3) (tribonacci) uses a 3x3 matrix. Counting walks of length n in a graph is the same trick: the (i, j) entry of the adjacency matrix to the power n counts walks from i to j.

Python Tribonacci and walk counting with matrix power

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting the cost

The size of the numbers matters too. Python integers grow without bound, so fib(10**6) without a modulus has over 200,000 digits, and each multiplication of such numbers is not O(1). The O(log n) count refers to arithmetic operations; use a modulus when the problem allows it.

Common mistakes

  • Two recursive calls instead of one reused half.
  • Forgetting to reduce modulo m after each multiplication, producing huge intermediate integers.
  • Starting result at 0. It must be the multiplicative identity: 1 for numbers, the identity matrix for matrices.
  • Matrix multiplication is not commutative. Keep the order consistent (result * base) when the matrices are not powers of the same base.
  • Off-by-one in the Fibonacci exponent. [[1,1],[1,0]]**n has F(n) at top-right; pick one convention and check small values.
  • Negative exponents. x**-n is 1 / x**n; modularly it is pow(x, -n, m) when an inverse exists.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many multiplications does binary exponentiation need for x^n?

    Each loop step halves the exponent, so there are about log2(n) steps, each doing at most one squaring and one multiplication into the result.
  2. 2. What is the correct starting value of result when computing a matrix power?

    The identity is the multiplicative neutral element, the matrix counterpart of 1 for plain numbers. Starting from zeros would make every product zero.
  3. 3. Why must fast_pow compute fast_pow(x, n // 2) only once per call?

    With two recursive calls on each level, the number of calls doubles per level over log n levels, which is O(n) again.
  4. 4. In which form does the Fibonacci recurrence turn into a power problem?

    Multiplying the vector (F(n), F(n-1)) by that matrix gives (F(n+1), F(n)), so n steps equal the n-th matrix power.
  5. 5. What is the time of exponentiating a k x k matrix to the power n with fast exponentiation?

    There are O(log n) matrix products and each product of k x k matrices takes O(k^3) with the standard method.

Summary

  • Binary exponentiation computes x**n in O(log n) multiplications by squaring and using the bits of n.
  • Reduce modulo m after every multiplication; the built-in pow(x, n, m) does it for you.
  • The idea works for any associative product with an identity element, including matrices (O(k^3 log n)).
  • Linear recurrences such as Fibonacci and tribonacci become matrix powers; graph walk counts do too.
  • Start result at the identity, compute the recursive half once, and keep the multiplication order consistent for matrices.

Next: Combinatorics and Counting