Vibe Engines Learn
Algorithms · Fast Exponentiation

Fibonacci, Fast-Forwarded.

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 matrix while n > 0: if n & 1: result = mul(result, base) # bit set → fold in base = mul(base, base) # square n >>= 1 # next bit return 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)?

2. What does the matrix let you compute besides Fibonacci?

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).

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
  1. 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.
  2. Multiply 2×2 matrices by hand — four dot products, no loops needed.
  3. 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.
  4. The identity matrix [[1,0],[0,1]] is the right starting value for the same reason 1 is for integers.
  5. 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.
  6. 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.
CPython · WebAssembly

Keep going

Algorithm

Modular Exponentiation →
Algorithm

Coin Change (DP) →
Algorithm

Floyd-Warshall →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 99 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →
Challenges →