Fibonacci as a matrix
The Fibonacci numbers satisfy a linear recurrence: each term is the sum of the two before it. That linear step can be captured by a two by two matrix. Multiplying the vector of two consecutive Fibonacci numbers by a fixed matrix produces the next pair.
The power trick
If one multiplication advances the sequence by one step, then raising the matrix to the n-th power advances it by n steps at once. The top entry of the resulting matrix is the n-th Fibonacci number. Because matrices can be raised to powers by squaring, the same logarithmic technique used for fast exponentiation applies here.
- One step is a single matrix multiply.
- Squaring the matrix repeatedly reaches the n-th power in steps proportional to the bit length of n.
This computes far off Fibonacci numbers without iterating through every earlier term, turning a linear walk into a logarithmic climb.
Practical notes
Fibonacci numbers grow exponentially, so for large n you work modulo some value to keep entries bounded, reducing after each multiplication. The same matrix power idea generalizes to any linear recurrence, which is why it is a staple in competitive programming.
Key idea
Writing the Fibonacci step as a matrix lets you raise it to the n-th power by squaring, computing the n-th term in steps proportional to the bit length of n rather than iterating linearly.