In Production · ICPC · Fundamentals
Fibonacci of 10¹⁸ in 84 multiplications
Every linear recurrence can be written as matrix multiplication. And matrices can be raised to a power fast.
What is the 10¹⁸th Fibonacci number, modulo something reasonable? A loop would still be running long after the contest ended. You get there with 84 multiplications.
A linear recurrence is a sequence in which each term is a linear combination of the ones before it, and Fibonacci is the famous example. Any such step can be written as a matrix T times a vector of recent terms. One application of T moves the sequence forward by one. Two applications, T², move it by two. And T^(n−1), applied to f(0) and f(1), which you already know, lands on f(n).
So the question becomes how fast you can raise a matrix to a power. You do not need n multiplications to reach xⁿ. From x you get x², from x² you get x⁴, and from x⁴ you get x⁸. Any exponent is a sum of those powers of two, read straight from its binary digits. Squaring turns n steps into about log n.
Loading interactive figure…
Static version: f(10¹⁸) takes 84 multiplications of 2×2 matrices, against 10¹⁸ additions in the simple loop.
The loop needs 10¹⁸ steps; the matrix needs 84 multiplications. When something grows one step at a time, look for the form that doubles. There almost always is one.