Want the 1,000,000th Fibonacci number? Adding one at a time is a million steps. But Fibonacci hides inside a tiny 2×2 matrix: raise [[1,1],[1,0]] to the n-th power and F(n) falls out. And you can raise anything to a huge power in ~log n steps by squaring — so a million-step recurrence collapses to about twenty matrix multiplies.
O(log n) time · binary exponentiation · linear recurrence
transition matrix
[[1,1],[1,0]] advances the Fibonacci state one step.
the power
That matrix to the n gives F(n) in its entries.
square, don’t multiply
Squaring doubles the exponent — the log-time trick.
binary bits
Multiply the result in only where n has a 1 bit.
matpow.js — square the base, multiply on set bits
n =
Ready
We raise the Fibonacci matrix B=[[1,1],[1,0]] to the power n. Read n in binary from the low bit. Press Step: if this bit is 1, fold B into the result; then square B and move to the next bit.
–
current bit
0
multiplies
–
F(n)
How it works
Two ideas snap together. First, Fibonacci is a linear recurrence, so one step of it is a matrix multiply: [F(k+1), F(k)] × [[1,1],[1,0]] = [F(k+2), F(k+1)]. Apply that matrix n times and you’ve advanced n steps — meaning [[1,1],[1,0]]ⁿ literally contains F(n). Second, you don’t apply it n times; you square your way there.
1
Write n in binary
Say n = 13 = 1101₂. Each bit, low to high, corresponds to B, B², B⁴, B⁸…
2
Bit is 1 → fold it in
Multiply the running result by the current power of B. That bit’s contribution is now included.
3
Square the base
Replace B with B×B — the next bit represents twice the exponent. Advance to that bit.
✓
Read F(n)
After ~log₂(n) rounds, the result is Bⁿ; its top-right entry is F(n). Twenty rounds reach a million.
Time
O(log n)
Naive loop
O(n)
Rounds for 10⁶
~20
Space
O(1)
The code
# F(n) via matrix power, O(log n)def mul(A, B):
return [[A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]],
[A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]]]
def fib(n):
result = [[1,0],[0,1]] # identity
base = [[1,1],[1,0]] # Fibonacci matrixwhile n > 0:
if n & 1: result = mul(result, base) # bit set → fold in
base = mul(base, base) # square
n >>= 1 # next bitreturn result[0][1] # F(n)
Swap the matrix and you get any linear recurrence — Tribonacci, or an adjacency matrix whose n-th power counts length-n paths in a graph. The fast-exponentiation skeleton is identical to modular exponentiation for numbers; only the multiply changes.
Quick check
1. Why is raising the matrix O(log n), not O(n)?
Right — each square doubles the power B represents (B → B² → B⁴ → …), and you fold into the result only on set bits. An n-bit exponent needs about log₂(n) squarings.
2. What does the matrix let you compute besides Fibonacci?
The technique is general: pick the transition matrix for your recurrence, or an adjacency matrix to count walks of length n. Same O(log n) squaring skeleton.
FAQ
What is matrix exponentiation?
Raising a square matrix to a large integer power in O(log n) matrix multiplications using binary exponentiation (repeated squaring) — the fast way to evaluate a linear recurrence at a huge index.
How does a 2×2 matrix give Fibonacci?
Multiplying the state [F(k+1), F(k)] by [[1,1],[1,0]] yields [F(k+2), F(k+1)]. So that matrix to the n-th power encodes F(n) — its entries are consecutive Fibonacci numbers.
Why not just loop n times?
For huge n (say 10¹⁸, common in competitive programming, often modulo a prime), an O(n) loop is far too slow. Matrix exponentiation is O(log n) — about 60 rounds for 10¹⁸.
How is it related to modular exponentiation?
Identical skeleton — square the base, multiply the result on set bits — but the "multiply" is matrix multiplication instead of scalar multiplication. Both compute xⁿ in O(log n).
The picture: squares you keep, squares you skip
Computing B¹³. The base is squared every round; the result only takes the squares whose bit of 13 is 1. Four squarings and three multiplies replace twelve.
Worked example, step by step
Compute F(13). Write 13 = 1101₂, start with result = I and base = B = [[1, 1], [1, 0]]. Each round reads the lowest bit, multiplies if it is 1, then squares the base.
Bit
Value
Base at this bit
Action
Result after
0
1
[[1, 1], [1, 0]]
multiply result by base
[[1, 1], [1, 0]]
1
0
[[2, 1], [1, 1]]
skip
[[1, 1], [1, 0]]
2
1
[[5, 3], [3, 2]]
multiply result by base
[[8, 5], [5, 3]]
3
1
[[34, 21], [21, 13]]
multiply result by base
[[377, 233], [233, 144]]
The bits are consumed low to high, so bit 0 uses B, bit 1 uses B², bit 2 uses B⁴ and bit 3 uses B⁸; the bases are the 2ᵏ-th powers. The result accumulates B · B⁴ · B⁸ = B¹³ = [[377, 233], [233, 144]], whose top-right entry is F(13) = 233. Notice that every matrix is made of consecutive Fibonacci numbers: B⁸ holds 34, 21, 13, and the final matrix holds 377, 233, 144. The naive loop would have done 13 additions; this did 3 matrix multiplications plus 4 squarings (and the last one, B¹⁶, is wasted work you can skip).
The same loop on a 3 × 3 matrix. Take a(n) = a(n−1) + a(n−2) + a(n−3) with a(0) = 0, a(1) = 1, a(2) = 1. Its transition matrix puts the three coefficients in the first row and shifts the rest down: [[1, 1, 1], [1, 0, 0], [0, 1, 0]]. Multiplying the state column [a(2), a(1), a(0)] = [1, 1, 0] by M18 gives [66012, 35890, 19513], which is a(20), a(19) and a(18). Since 18 = 10010₂, the loop does 2 multiplies and 4 squarings, 6 matrix products in all. Each 3 × 3 product costs 27 scalar multiplies against 8 for a 2 × 2. That is the k³ in O(k³ log n): the exponent is cheap, and the matrix size is what you pay for.
Complexity and trade-offs
Case
Time
Space
Why
Matrix power (d × d)
O(d³ · log n) multiplies
O(d²)
Squaring plus folding takes at most 2·⌊log₂ n⌋ multiplies. For n = 10⁶ that is 20 bits and 26 multiplications, against a million steps.
Simple loop
O(n) additions
O(1)
Best for small n, and the only choice if you need every term, not just the n-th.
Fast doubling (Fibonacci only)
O(log n)
O(1)
Uses F(2k) and F(2k+1) formulas; fewer multiplies than 2×2 matrices, but specific to Fibonacci.
Closed form (Binet)
O(1) in theory
O(1)
Floating point loses exactness past about F(70); exact versions need big numbers anyway.
Large exact value
O(M(n) ) per multiply
O(n) digits
F(10⁶) has 208,988 decimal digits, so the multiplies are no longer constant time. Ask for the result modulo a prime and they are.
With a modulus the arithmetic stays machine-sized: F(10¹⁸) mod 1,000,000,007 is 209783453, found in 83 multiplies. The cost to remember is d³: a recurrence with d = 50 states needs 125,000 operations per multiply, so a long recurrence with a big order can lose to a different method. The log n factor wins when n is huge and d is small.
Common mistakes
Starting result at zeros instead of the identity
result = [[0,0],[0,0]] gives a zero matrix forever, since 0 × anything is 0. The multiplicative identity is [[1,0],[0,1]]; for n = 0 it correctly returns F(0) = 0.
Reading the wrong entry
For B = [[1,1],[1,0]], Bⁿ[0][1] is F(n) and Bⁿ[0][0] is F(n+1). Returning [0][0] is off by one: for n = 13 it gives 377 instead of 233.
Forgetting the modulus on every multiply
Reducing only at the end overflows 64-bit integers by about F(93). Reduce each entry of every product, including the squaring step, and use a 128-bit or modular multiply when the modulus is near 2⁶³.
Squaring in place while multiplying
Writing result = mul(result, base) and base = mul(base, base) through one shared temporary overwrites an input mid-multiply. Compute the product into a fresh matrix.
Using signed shifts on negative n
A negative exponent has no meaning for this loop (in Python, -1 >> 1 stays -1, so while n never ends). Validate n ≥ 0; negative Fibonacci indices need the identity F(−n) = (−1)ⁿ⁺¹ F(n).
Skipping the modulus because the language has big integers
Python never overflows, so the loop still returns the exact F(n) with no modulus. But F(1000) already has 209 digits, and each product then costs big-number arithmetic that grows with n. The log n count of multiplies means O(log n) time only while every entry stays a fixed size, so reduce mod m whenever the problem allows it.
Where this shows up
Huge-index recurrences
Problems that ask for F(n), Tribonacci or any linear recurrence “mod 10⁹ + 7” with n up to 10¹⁸ are solved this way. The transition matrix has the recurrence coefficients in its first row.
Counting walks in a graph
The (i, j) entry of the adjacency matrix to the k-th power is the number of walks of length k from i to j. Counting paths of length 10¹² in a small graph is a matrix power.
Markov chains
The distribution after n steps is the initial row vector times the n-th power of the transition matrix; raising it by squaring gives long-run behaviour in log n multiplies.
Modular exponentiation
The skeleton is identical to computing an mod m for numbers, which underlies RSA and Diffie-Hellman. Only the multiply changes.
SOLVE IT YOURSELF
Solve it: the billionth Fibonacci number
Any linear recurrence is a matrix multiply in disguise — and a matrix power can be squared just like an integer one. That turns an O(n) loop into O(log n). Python or TypeScript.
YOUR TASK
Implement mat_mult (2×2), mat_pow by squaring, and fib(n) on top of them. fib(0) is 0 and fib(1) is 1.
HINTS — 6 IDEAS
The identity: [[1,1],[1,0]]ⁿ equals [[F(n+1), F(n)], [F(n), F(n−1)]], so the answer is one entry of the matrix power.
Multiply 2×2 matrices by hand — four dot products, no loops needed.
Raise by squaring exactly like integer mod_pow: start from the identity matrix, square the base each round, fold it into the result on every set bit of the exponent.
The identity matrix [[1,0],[0,1]] is the right starting value for the same reason 1 is for integers.
Handle n = 0 before the loop — M⁰ is the identity and its [0][1] entry is 0, which happens to be right, but being explicit is clearer.
Note for JavaScript: Fibonacci exceeds the exact-integer range (2⁵³) around F(79), so the TypeScript tests stop below that. Python has arbitrary precision and does not care.