Fibonacci in O(1) space and matrix exponentiation in Python

Why this matters

Fibonacci is the first dynamic programming problem most people meet. The memoization and tabulation lesson showed how to stop recomputing the same values. This lesson asks two harder questions: can the table be made smaller, and can the answer be found without visiting every step from 0 up to n?

Interviewers ask both questions. The first one checks whether you can see which values a recurrence really needs. The second one checks whether you know that a loop running n times is not always fast enough. When n is 10^18, a loop that adds one step per cycle would take about 30 years at a billion steps per second. Matrix exponentiation gets the same answer in about 120 small matrix multiplications.

Every program here is a plain Python file. Run one with python3 main.py. The outputs shown were produced on Python 3.14.

The problem

The Fibonacci numbers start with 0 and 1. Each later number is the sum of the two before it.

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) for n of 2 or more

The first eleven values are 0 1 1 2 3 5 8 13 21 34 55. So F(10) is 55, the value at position 10 counting from 0.

Step 1: The plain recursion is slow

The recurrence is easy to write as a function that calls itself. The code below counts how many calls it makes, so you can see the cost. It uses a list with one number in it as the counter, because a function cannot change a plain number that belongs to its caller unless it uses global or nonlocal.

Output:

n=5 F(n)=5 calls=15
n=10 F(n)=55 calls=177
n=20 F(n)=6765 calls=21891
n=30 F(n)=832040 calls=2692537

Look at the call counts. Going from n = 20 to n = 30 multiplies the calls by about 123. The same subproblem is solved again and again. For example, F(3) is computed inside F(5), inside F(6), inside F(7) and in many other places. The count is always 2 * F(n + 1) - 1. For n = 30 that is 2 * 1346269 - 1 = 2692537, which matches the output.

A table fixes this. Store each F(i) in a list as you go, and each value is computed once. That takes O(n) time, meaning the work grows in step with n, and O(n) memory for the list. The next step removes the list.

Step 2: Keep only the last two numbers

To compute F(i), you need only F(i - 1) and F(i - 2). Once you have F(i), the value F(i - 2) is never read again. So you can keep two variables and move them forward.

Let a hold F(i) and b hold F(i + 1). The start is a = 0 and b = 1, which are F(0) and F(1). One step forward is a, b = b, a + b. Python computes the right side first, using the old values, and then assigns both names. So the new a is the old b, and the new b is the sum. Here is the trace for n = 6.

After 6 steps a is 8, which is F(6). The code below does this loop. Many languages need a temporary variable for this swap. Python does not, because of the tuple assignment.

Output:

0 1 1 2 3 5 8 13 21 34 55
F(50) = 12586269025
F(90) = 2880067194370816120

The loop runs n times, so the time is O(n). The memory is always the same two names, a and b, whatever n is. That is what O(1) space means: the amount of working memory does not grow with the input. Be careful with the word "space" here. The numbers themselves get longer as n grows. F(90) needs 62 binary digits. The claim covers the count of names, not the number of bits inside them.

Python integers have no fixed size, so the loop never wraps around. That is different from a 64-bit integer in Java, which runs past its limit and wraps to a wrong value. The Python version is always exact. The cost is that a big number takes more time and memory to add.

Why the function returns a

After the loop runs n times, a holds F(n) and b holds F(n + 1). Returning b gives the next value, which is a common off-by-one error. The mistakes section shows what that looks like.

Step 3: The loop is still too slow for huge n

Consider a problem that asks for F(n) with n as large as 10^18. The loop needs 10^18 steps. A fast machine doing one billion steps per second needs about 10^9 seconds, which is around 31 years.

Problems like this usually ask for the answer modulo a prime, often 1000000007. Modulo means the remainder after division. So the answer is the Fibonacci number with its value wrapped into the range 0 to 1000000006. The modulus keeps every number small. The loop still needs 10^18 steps, so a different method is needed.

Step 4: One Fibonacci step is a matrix multiplication

A matrix is a grid of numbers. A 2 by 2 matrix has two rows and two columns. Here is the key fact. Let

M = [ 1  1 ]
    [ 1  0 ]

Multiply M by a column that holds F(n) and F(n - 1). The first row gives F(n) + F(n - 1), which is F(n + 1). The second row gives F(n). So one multiplication moves the pair one step forward.

[ 1  1 ] [ F(n)   ]   [ F(n) + F(n-1) ]   [ F(n+1) ]
[ 1  0 ] [ F(n-1) ] = [ F(n)          ] = [ F(n)   ]

Doing this n times from the start pair [F(1), F(0)] = [1, 0] gives M raised to the power n. The result is a 2 by 2 grid:

M^n = [ F(n+1)  F(n)   ]
      [ F(n)    F(n-1) ]

You can check this for small n. M^1 is [1 1; 1 0], which matches F(2), F(1), F(1), F(0). M^2 is [2 1; 1 1], which matches F(3), F(2), F(2), F(1). Once you have the matrix power, F(n) is the entry in row 0 and column 1.

Why powers are fast

Matrix multiplication is associative. That means (M * M) * M and M * (M * M) give the same grid. Binary is base 2, which writes a whole number with only the digits 0 and 1. Each place is a power of two. So M^13 can be built from powers that are themselves built by squaring:

13 in binary is 1101, which is 8 + 4 + 1
M^13 = M^8 * M^4 * M^1

Squaring doubles the power each time. Starting from M^1, squaring gives M^2, M^4, M^8, and so on. To reach M^n, you square about log2(n) times, then multiply together the squares that match the binary digits of n. For n = 10^18, log2(n), the number of times n can be halved before it reaches 1, is about 60, so the work is about 120 matrix multiplications. Each matrix multiplication is 8 multiplications of numbers, so the total is under a thousand multiplications of numbers.

Step 5: Fast power in code

The loop below builds M^p by reading the binary digits of p, called bits, from the lowest digit upward. The variable base holds M raised to a power of two. Each time the lowest bit of p is 1, the code multiplies result by base. After that, base is squared and p is shifted right by one bit. In Python, p & 1 gives the lowest bit, and p >>= 1 shifts the bits one place to the right.

Here is the trace for p = 13, which is 1101 in binary.

The last squaring to M^16 is not needed. The code still does it, which costs one extra multiplication. It does no harm.

The full program takes the remainder by MOD after every addition inside the matrix multiplication. Each entry in a matrix is then smaller than MOD, so every number in the program stays below about 10^18. That keeps the time for each step fixed, which the next section explains.

Output:

0 1 1 2 3 5 8 13 21 34 55
F(50) mod MOD = 586268941
F(90) mod MOD = 210345902
F(10^18) mod MOD = 209783453

The first line matches the table from Step 2. The value 586268941 is F(50) = 12586269025 with 1000000007 subtracted 12 times. You can check the value for n = 50 yourself with fib(50) % MOD from the loop in Step 2. The value for 10^18 cannot be checked this way, because the loop would need 10^18 steps.

The identity matrix [[1, 0], [0, 1]] is the starting result. It plays the role that 1 plays in ordinary multiplication: multiplying by it changes nothing. For p = 0 the loop does not run, so fib_matrix(0) returns the entry q[0][1], which is 0, the correct value for F(0).

The expression 10**18 means 10 to the power 18. The underscores in 1_000_000_007 are only for reading. Python ignores them.

Step 6: What O(log n) means here

Count the work. The loop runs once for each binary digit of p, so about log2(p) times. Each run does up to two matrix multiplications. A matrix multiplication of 2 by 2 matrices is a fixed set of 8 multiplications and 4 additions, and with the modulo each of those numbers stays small. So the total time is O(log n) operations. That is the claim to make in an interview, with the modulo stated as the reason each step costs a fixed amount.

Without the modulo, the claim fails. The numbers in M^n grow with n, so each multiplication takes longer as the numbers get bigger. Python keeps every digit, so nothing goes wrong silently. But the size of the numbers grows fast. The next program shows the exact value for a few large n, and it shows the result you would get from a 64-bit integer, which is what a language like Java or C gives for long. The second value is computed by keeping only the low 64 bits of the exact number.

Output:

n=90 wrapped=2880067194370816120 exact=2880067194370816120
n=92 wrapped=7540113804746346429 exact=7540113804746346429
n=93 wrapped=-6246583658587674878 exact=12200160415121876738
n=100 wrapped=3736710778780434371 exact=354224848179261915075

Up to n = 92 the 64-bit value is exact. From n = 93 on, the value wraps around and even becomes negative. A 64-bit Java long would print the same wrapped number, with no error. This is why problems that ask for a large Fibonacci number almost always ask for it modulo a prime.

The exact numbers also grow in length. F(100) has 21 digits, and F(1000) has 209 digits. The number of digits of F(n) grows in step with n, so F(10^18) would have about 2 * 10^17 digits. No computer can store that. That is why the modulo is required for large n, even in Python.

Common mistakes

Swapping the two assignments. If you write a = b before computing the sum, the sum uses the new a. The loop then gives a different sequence. The next program shows it.

Output:

swapped F(5) = 16

The correct answer is 5. The bug is that b = a + b reads the a that was just overwritten, so b doubles on each step.

Returning b instead of a. After n steps, a is F(n) and b is F(n + 1). Returning b moves the answer one place forward. The next program shows it for n = 5.

Output:

return b gives 8

The expected value is 5. Check your return statement against the trace table in Step 2 before you submit.

Forgetting the modulo in one place. The multiply function must take the remainder after each addition, not only at the end. If one product is never reduced, the next step multiplies a huge number, and the numbers keep growing. The result is still right in Python, but each step gets slower as the numbers grow, so the time is no longer O(log n).

Using the wrong index for the answer. The answer is q[0][1] in the program above. Writing q[0][0] gives F(n + 1). Writing q[1][1] gives F(n - 1). A quick test on small values such as n = 0, 1 and 2 catches this at once. The next program prints the matrix for n = 3 so you can see the entries. It does not read input.

Output:

M^2 = [[2, 1], [1, 1]]
M^3 = [[3, 2], [2, 1]]

The entries of M^3 are F(4), F(3) in the top row and F(3), F(2) in the bottom row.

Passing a negative n. The loop while p > 0 does nothing for a negative value, so fib_matrix(-1) returns the identity's entry, which is 0. No error is raised. If the problem allows only n of 0 or more, add a check at the top of the function, and raise an error for anything else with raise ValueError("n must be 0 or more").

Practice

Exercise 1. Trace the loop in fib for n = 7. Write the value of a after each step.

Show the answer

The values of a are 0 (start), 1, 1, 2, 3, 5, 8, 13. After 7 steps a is 13, which is F(7).

Exercise 2. How many matrix multiplications does matrix_power perform for p = 8? Count the calls to multiply, including the squarings and the multiplications into result.

Show the answer

The loop runs four times, for p = 8, 4, 2 and 1. Each run squares base, which gives 4 multiplications. The lowest bit is set only when p = 1, which adds one multiplication into result. The total is 5.

Exercise 3. Compute M^3 by hand from M^2 = [2 1; 1 1] and M = [1 1; 1 0]. Check the entries against Fibonacci numbers.

Show the answer

The entry in row 0, column 0 is 2 * 1 + 1 * 1 = 3. Row 0, column 1 is 2 * 1 + 1 * 0 = 2. Row 1, column 0 is 1 * 1 + 1 * 1 = 2. Row 1, column 1 is 1 * 1 + 1 * 0 = 1. So M^3 = [3 2; 2 1], which matches F(4), F(3), F(3), F(2).

Exercise 4. The exact value of F(100) is 354224848179261915075, from the program in Step 6. Find the last digit of F(100) without using that number. Hint: the last digits of Fibonacci numbers repeat with period 60, and 100 mod 60 is 40. F(40) is 102334155.

Show the answer

100 mod 60 is 40, and F(40) = 102334155 ends in 5. So F(100) ends in 5, which matches the exact value.

Exercise 5. Write a function pair_fib(n) that returns (F(n), F(n + 1)) using the two-variable loop from Step 2, without the matrix code.

Show the answer

def pair_fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a, b

After n steps a is F(n) and b is F(n + 1), so the function returns (F(n), F(n + 1)).

Summary

• Keeping two variables instead of a table makes the Fibonacci loop use constant memory, while the time stays O(n).
• A pair of Fibonacci numbers moves forward by one multiplication with the 2 by 2 matrix [1 1; 1 0].
• Squaring the matrix repeatedly and reading the binary digits of n gives F(n) in about 2 * log2(n) multiplications.
• Use a modulo after every multiplication and addition, because the numbers grow quickly and a large exact value has too many digits to store.
• Check the index you return and test small values such as 0, 1 and 2 before trusting the code.