Fibonacci numbers
The Fibonacci numbers start with F_0 = 0 and F_1 = 1, and each next one is the sum of the two before it, F_n = F_{n-1} + F_{n-2}: 0, 1, 1, 2, 3, 5, 8, 13, 21, … A short loop computes F_n. For up to 10^{18}, binary exponentiation on 2×2 tables of numbers computes F_n modulo .
Explanation
Write the Fibonacci numbers in a row of cells numbered from 0, so that cell holds F_n. To find the number in cell 10, we go along the row from the left. Since the next number needs only the last two, we keep just those. Each cell costs one addition, so cell takes about additions.
Fig. 1. Each number is the sum of the two before it. The loop keeps only the last two.
The numbers grow fast, each about 1.6 times the one before (the number in cell 31 divided by the number in cell 30 is 1.618…). The number in cell 46, 1836311903, is the last that fits in an int, and the number in cell 92, 7540113804746346429, is the last that fits in a long long. Problems with larger therefore ask for the number modulo some , often 10^9 + 7. The loop still works: the remainder of a sum depends only on the remainders of its terms (modular arithmetic), so we take the remainder after every addition.
For n = 10^{18} the loop needs 10^{18} additions. At a rule of thumb of about 10^8 simple operations per second, that is more than 300 years. The trouble is that the loop moves one cell at a time.
For powers, binary exponentiation jumped far ahead by squaring: from 3^5 it got 3^{10} in one multiplication. Here that would be a jump from cell 5 to cell 10. Squaring the 5 in cell 5 gives 25, but cell 10 holds 55. Squaring the 2 in cell 3 gives 4, but cell 6 holds 8.
The next number depends on the last two, so we jump with a pair. A step takes the pair of the last two numbers, larger first, and makes the next pair: the pair (a, b) becomes (a + b, a). Start from any pair (x, y) and do 5 steps:
(x, y) becomes (x + y, x),
then (2x + y, x + y),
then (3x + 2y, 2x + y),
then (5x + 3y, 3x + 2y),
then (8x + 5y, 5x + 3y).
Whatever the start, 5 steps are described by four numbers. We write them as a table with two rows, the top row for the new first number and the bottom row for the new second: \begin{pmatrix} 8 & 5 \\ 5 & 3 \end{pmatrix}. From the numbers in cells 1 and 0, the pair (1, 0), it gives (8, 5), the numbers in cells 6 and 5.
Ten steps are 5 steps done twice: put the result of the first 5 steps into the same rule. The new first number is 8 · (8x + 5y) + 5 · (5x + 3y) = 89x + 55y, and the new second is 5 · (8x + 5y) + 3 · (5x + 3y) = 55x + 34y. The table for 10 steps is \begin{pmatrix} 89 & 55 \\ 55 & 34 \end{pmatrix}, and 55, the number in cell 10, is in it. Each number of the new table is a row of the first table times a column of the second: the 55 in the top right is 8 · 5 + 5 · 3.
Fig. 2. The table for 10 steps is made from the table for 5 steps, row times column.
A table of four numbers in two rows and two columns is called a 2×2 matrix, and combining two tables like this is multiplying matrices. The table for one step is \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, since (a, b) becomes (1 · a + 1 · b, 1 · a + 0 · b). The table for steps is the table for one step multiplied by itself times, its -th power.
To find the number in cell in that table, put x = 1 and y = 0: the pair becomes (top left, bottom left), the left column. The pair (1, 0) is the numbers in cells 1 and 0, so after steps the left column holds the numbers in cells n + 1 and . The pair (0, 1) gives the right column, and it becomes (1, 0) after one step, so after steps it is one cell behind: the numbers in cells and n - 1. The top-right number is therefore the number in cell . In the table for 10 steps, 89 55 / 55 34, the left column holds the numbers in cells 11 and 10, and the right column those in cells 10 and 9.
The same tables work for other rows of numbers. A strip 2 cells high and cells long is covered with 1×2 dominoes and 2×2 squares. Its right end is one standing domino, or two lying dominoes, or a square, so the number of coverings for length is the number for n - 1 plus twice the number for n - 2. For lengths 0, 1, 2, … that gives 1, 1, 3, 5, 11, 21, … One step turns the pair (a, b) into (a + 2b, a), so the table for one step is \begin{pmatrix} 1 & 2 \\ 1 & 0 \end{pmatrix}, and its square, the table for 2 steps, is \begin{pmatrix} 3 & 2 \\ 1 & 2 \end{pmatrix}.
Binary exponentiation computes the power from squares: 10 is 1010 in binary, 8 + 2, so the table for 10 steps is the table for 2 steps times the table for 8 steps. The table for 0 steps, \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, leaves every pair as it is, so the answer starts from it, as the answer for a power of a number starts from 1. Each round has three stages: take the digit, square, halve. Raising a matrix to a power this way is called matrix exponentiation. Here is the run for cell 10, round by round.
Start: n is 10, binary 1010. The answer so far is the table for 0 steps, and the current square is the table for one step. The number above a square is its number of steps; the outlined digit is the last one.
Fig. 3. Step through the run with the buttons or the arrow keys. Only the squares under a digit 1 enter the answer.
The run took 4 rounds, one for each binary digit of 10, with at most two products per round. 10^{18} has 60 binary digits, so it needs at most 120 products instead of 10^{18} additions.
Implementation
A table is the type Mat, a 2×2 array of long long; using gives the type this short name. Unlike a plain array, an array can be returned from a function and copied with =. a[0][1] is the number in the top row, right column. The function mul multiplies two tables, row times column, with % m on each entry. It takes them as const Mat&, so they aren't copied, and m is a global variable so that mul can read it. The loop is the binary exponentiation loop for a power of a number: n is the number of steps left, base the current square and result the answer so far, which ends as the table for n steps.
Start:
base = {{1, 1}, {1, 0}},result = {{1, 0}, {0, 1}}.Take the digit: if
n % 2 == 1,result = mul(result, base).Square:
base = mul(base, base).Halve:
n /= 2.Stop when
n == 0; the answer isresult[0][1]. Otherwise go back to Take the digit.
The input is n and m, with 0 ≤ n ≤ 10^18, and the program prints F_n modulo m. For = 10 modulo 10^9 + 7 the input is:
10 1000000007#include <array>
#include <iostream>
using namespace std;
using Mat = array<array<long long, 2>, 2>; // a 2x2 table of numbers
long long m;
// multiply: row of a times column of b, % m on each entry
Mat mul(const Mat& a, const Mat& b) {
Mat c;
c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % m;
c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % m;
c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % m;
c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % m;
return c;
}
int main() {
long long n;
cin >> n >> m;
// start
Mat base = {{{1, 1}, {1, 0}}}; // one step
Mat result = {{{1, 0}, {0, 1}}}; // 0 steps: changes nothing
while (n > 0) { // stop when n is 0
// take the digit
if (n % 2 == 1) result = mul(result, base);
// square
base = mul(base, base);
// halve
n /= 2;
}
cout << result[0][1] << '\n'; // F_n is the top-right entry
}There is one round per binary digit of n, and each product is 8 multiplications and 4 additions, so the time is O(\log n) and the memory is .
A loop for smaller n
When n is at most 92, F_n fits in long long, and the loop along the row is simpler. a and b hold the last two numbers; each round adds them into c and shifts the pair one cell right.
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long a = 0, b = 1; // F_0 and F_1
for (long long i = 0; i < n; i++) {
// add
long long c = a + b; // c = (a + b) % m; if the problem asks for the remainder
// shift
a = b;
b = c;
}
cout << a << '\n'; // a is F_n
}It takes time, and with % m it also works for a remainder when n is up to about 10^8. For many queries, fill an array F[0..n] once and look each one up.
Common mistakes
Plain recursion
fib(n - 1) + fib(n - 2). Forn= 45 it makes 3672623805 calls, more than half a minute at 10^8 per second; the loop makes additions.Overflow in a fixed-size type. F_{47} in
intprints −1323752223, and F_{93} inlong longprints −6246583658587674878. Uselong longup to F_{92}, the remainder when the problem asks for one, and big integers when all digits are needed.The wrong start of the row. Some problems start from F_1 = F_2 = 1, which is the same row, and some from f_0 = f_1 = 1, where f_n is F_{n+1} (then f_{45} = 1836311903). Check the first values against the sample and shift
n.Binet's formula in floating point. It says that F_n is \varphi^n / \sqrt{5} rounded, with = 1.618…, written as
llround(pow(phi, n) / sqrt(5)). Withdoubleit gives 308061521170130 for = 71, while F_{71} = 308061521170129, and it can't give a remainder modulomat all. Use the loop or matrix exponentiation.Taking
% monly at the end. Without% minsidemul, the entries overflow after a few rounds, and an overflowinglong longhas no reliable value: on100 1000000007one compiler printed 623459107 instead of 687995182.
Similar algorithms
Matrix exponentiation works for any sequence where the next value is a fixed sum of the last values, with a × matrix. Fibonacci numbers are the 2×2 case.
Fast doubling writes out the square of the table as two formulas that give F_{2k} and F_{2k+1} from F_k and F_{k+1}; a recursion that halves with them also takes O(\log n) steps.
Counting problems in dynamic programming often give Fibonacci numbers: climbing stairs 1 or 2 at a time, or tiling a 2× strip with dominoes.
Practice
Very easy · Implementation
Very easy · Dynamic programming
Medium · Dynamic programming · Math · Strings
Medium · Math · Brute force
Easy · Dynamic programming · Matrix
Easy · Number theory · Math
Very easy · Dynamic programming