# Fibonacci of 10¹⁸ in 84 multiplications

> Every linear recurrence can be written as matrix multiplication. And matrices can be raised to a power fast.

- Author: Marcello Oliveira (https://mrcll.me/about/)
- Published: Nov 2, 2026
- Topics: ICPC, Fundamentals
- URL: https://mrcll.me/stories/linear-recurrences-log-time/

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.

> Interactive figure (Recurrence): open the web version at https://mrcll.me/stories/linear-recurrences-log-time/

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.