## Thursday, January 23, 2020

### Fibonacci and Matrix Exponentiation

Problem statement
The Fibonacci numbers, commonly denoted Fn form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is
and
for n > 1.
The beginning of the sequence is thus:

A common coding interview question is to compute the n-th Fibonacci number.

## Naive solution

A naive way of implementing F(n) is to use recursion:

def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)

Such an implementation leads to an exponential runtime. The issue is that we compute the same values over and over again. Let's take a look at the recursion tree:

We can quickly estimate an upper bound for the time complexity as O(2^n). A tight bound Θ((1+sqrt(5)/2)^n) = (Fib(n)) can be determined by using generating functions and the golden ratio.

## Linear solution

We can easily improve the previous solution by using memorization to avoid recomputing the same value multiple times:

fib = {
0: 0,
1: 1
}

def fibonacci(n):
if n in fib:
return fib[n]

fib[n] = fibonacci(n - 1) + fibonacci(n - 2)
return fib[n]

The time complexity is now linear O(n), but we also using O(n) memory. Let's rewrite the solution iteratively:

def fibonacci(n):
fib = [0, 1]
for i in xrange(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
return fib[n]

Note how at each step we only need to look at the previous two values. Thus we can achieve the same result with constant O(1) additional memory:

def fibonacci(n):
if n <= 1:
return n

tmp0 = 0
tmp1 = 1
for i in xrange(2, n + 1):
curr = tmp0 + tmp1
tmp0 = tmp1
tmp1 = curr
return tmp1

## Optimal solution

The linear solution is the one described in most coding interview training resources. But can we do better? As it turns out we can actually solve the problem in logarithmic time. Let's see how.

We will rewrite the Fibonacci formula using simple matrix algebra:

which is also equivalent to

now all we need to do is compute the matrix exponentiation which can be implemented in O(logN) time. The pseudocode implementation is not too difficult either:

power(result_matrix, base_matrix, exponent):
if exponent == 1:
result_matrix = base_matrix.copy()
return

if exponent % 2 == 1:
power(result_matrix, base_matrix, exponent - 1)
result_matrix = result_matrix * base_matrix
else
power(result_matrix, base_matrix, exponent / 2)
result_matrix = result_matrix * result_matrix

fibonacci(n):
base_matrix = [ [1,1], [1, 0] ]
result_matrix = []
power(result_matrix, base_matrix, n)

return result_matrix[0][1]

## Solving linear recurrence problems

linear recurrence relation is an equation that defines the $n^\text{th}$ term in a sequence in terms of the $k$ previous terms in the sequence. The recurrence relation is in the form:
$x_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k}$
Where each $c_i$ is a constant coefficient.

The Fibonacci problem is a particular case of a linear recurrence of a 2nd degree with both coefficients equal to 1. The matrix exponentiation solution can be used in solving any linear recurrence problems. For example if we had to solve:

xn=6xn112xn2+8xn3

then we can build the matrix:

[  6,  -12,  8  ]   [ Xn-1 ]   [ Xn   ]
[  1,   0,    0 ] x [ Xn-2 ] = [ Xn-1 ]
[  0,   1,    0 ]   [ Xn-3 ]   [ Xn-2 ]

For a recurrence of k-th degree the matrix multiplication takes O(k^3) and the exponentiation takes O(logN) time, therefore we can solve the general problem in O(k^3 * logN) time.

## Note

The logarithmic solution is only viable when we need to compute a single value for a given n. If, for example, we are asked to compute all the Fibonacci numbers up to and including n, then the linear solution is the obvious right choice.