Less-than-linear Fibonacci
Few interview problems are as notorious as the “Fibonacci” interview question. At first glance, it seems good: Most people know something about the problem, and there are several clever ways to achieve a linear time solution. Usually, in interviews, the linear time solution is the expected solution. However, the Fibonacci problem is unique among interview problems in that the expected solution is not the optimal solution. There is an $O(1)$ solution, and to get there, we need a little bit of linear algebra.
In this part, we are going to use basic linear algebra to get to $O(\log(n))$ time complexity. In the next part, we build on this with some more advanced math to get to a generic $O(1)$ solution for Fibonacci-like problems.
The Fibonacci Interview Problem
The Fibonacci numbers are the sequence of numbers constructed such that each number is the sum of the two previous numbers in the sequence, starting with 0 and 1: $$ F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} $$ The resulting sequence is: $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … $$ And so on. You can generalize the formula by changing the initial conditions or the recursive formula (which mathematicians call a recurrence relation). Everything we are discussing applies to the generalized problem.
The interview problem is simple: given a number n, compute the nth Fibonacci number.
According to tradition, the optimal solution to the Fibonacci interview problem is to compute the entire sequence up to that point, using either recursion with memoization or one-dimensional dynamic programming. Both result in a solution that uses linear time and space.
Recurrence Relations and Systems of Equations
To compute the nth Fibonacci in constant time, we need a closed-form solution. There are Googleable solutions for the Fibonacci recurrence relation (specifically Binet’s Formula), but we would like to create a general solution for this class of problem. It turns out that there is a general method to derive a closed-form solution for any recurrence relation, and it is better to learn it once than to look for a Fibonacci-specific answer.
We start by creating a system of equations. The recurrence relation is one of those equations, and the other equations are simple equalities. For the Fibonacci sequence, our system is: $$ F_{n + 1} = F_{n} + F_{n - 1} \\ F_n = F_n $$ We can represent the system as a matrix equation: $$ \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} $$ This is a restatement of the equation above. The top row corresponds to $F_{n + 1} = F_{n} + F_{n - 1}$ and the bottom row is $F_n = F_n$. The left side is the result of the equations, and the right side is the product of the coefficient matrix and the variables that feed into the equations.
Let’s call the big matrix $\textbf{A}$: $$ \textbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$ If the recurrence relation changes, $\textbf{A}$ changes. Using this form, if we want $F_2$, the formula is: $$ \begin{bmatrix} F_{2} \\ F_{1} \end{bmatrix} = \textbf{A} \begin{bmatrix} F_{1} = 1 \\ F_{0} = 0 \end{bmatrix} $$ If we want the third Fibonacci number, we need to do a little more work: $$ \begin{bmatrix} F_{3} \\ F_{2} \end{bmatrix} = \textbf{A} \begin{bmatrix} F_{2} \\ F_{1} \end{bmatrix} = \textbf{A}^2 \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$ We have an interesting relationship here: By computing powers of $\textbf{A}$, we can directly calculate Fibonacci numbers. Our task is now to compute the power of the $\textbf{A}$ matrix quickly. Even the simplest algorithm for this, multiplying $\textbf{A}$ by itself $n$ times, takes $O(n)$ time and $O(1)$ space. This is already better than the “optimal” solution that you can find in Cracking the Coding Interview.
Generalizing Beyond Fibonacci
If we have a different recurrence relation, we can still do this trick. For example, with $X_{n+1} = 2 X_n + 3 X_{n-1}$, $ \textbf{A} $ changes to:
$$ \textbf{A}_X = \begin{bmatrix} 2 & 3 \\ 1 & 0 \end{bmatrix} $$
And for $Y_{n+1} = Y_n + 2 Y_{n-1} + 3 Y_{n-2}$, we can add another equality to the system of equations:
$$ \textbf{A}’ = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} $$
The full equation is:
$$ \begin{bmatrix} F_{n+1} \\ F_{n} \\ F_{n-1} \end{bmatrix} = \textbf{A}’ \begin{bmatrix} F_{n} \\ F_{n-1} \\ F_{n-2} \end{bmatrix} $$
Getting Logarithmic
We have reduced the problem to efficiently computing $\textbf{A}^n$ to get the nth Fibonacci number. Matrix multiplication is associative, so we can re-order the computation of the matrix products for efficiency. A convenient way to do this is to compute the powers of two of the matrix by repeated squaring, and then decomposing the exponentiation into a product of powers of two. For example:
$$ \textbf{A}^{53} = \textbf{A}^{32} * \textbf{A}^{16} * \textbf{A}^4 * \textbf{A}^1 $$
This is similar to how binary code decomposes numbers into a set of ones, so we can use the bits of $n$ to decide which powers to multiply to make $A^n$: When you have a one bit, multiply the corresponding power of $\textbf{A}$ into the result. When you have a zero bit, don’t, and stop when you reach the most significant one bit in $n$.
Note that we do either one or two matrix multiplications (constant time) per bit until we reach the most significant bit of $n$, and then we are done. Starting from the first bit in the ones position, the MSB of $n$ is bit number $\log_2(n)$, so we have $O(\log_2(n))$ time complexity (with constant space).
Working in Python, we get something like the following code. Rust, Python, and many other languages have well-supported easy-to-use matrix multiplication routines, so we are using Python. BLAS is also available for languages like C, C++, and Fortran.
import numpy as np
def log_fibonacci(n):
# Initialize the A matrix and the matrix that represents A^n
a = np.array([[1, 1],
[1, 0]])
result = np.identity(2)
# Computing A^n gives us Fibonacci number n + 1, so decrement n
n -= 1
while n != 0:
# Multiply by the A matrix power if we have a one bit
if n & 1 == 1:
result = result @ a
# Square the a matrix and move to the next bit
a = a @ a
n >>= 1
# Apply the initial conditions
initial_conditions = np.array([1, 0])
return (result @ initial_conditions)[0]
Conclusions
By pairing a little bit of traditional mathematics with algorithms, we have a solution that is a lot better than the traditional “algorithms” approach to the problem of computing Fibonacci numbers. In the next part, we are going to apply more math to do even better.