Digging in the depth of Fibonacci

Not so long ago, I read an article on fibonacci. I suggested a more elegant solution to my eyes, but the problem kept bogging me. Let's get into it!

The naïve recursive approach

The first implementation, which reads like the mathematical formula, looks like this:

def fib(0), do: 1
def fib(1), do: 1
def fib(n), do: fib(n-1) + fib(n-2)

The main issue with this implementation is that the bigger the index you calculate, the exponentially bigger is number of operation needed. To show how, let's look at the following graph of calls of the fib(5):

Recursive Fibonacci implementation function call graph
Fig 1: Recursive Fibonacci implementation function call graph

As you can see fib(2) is calculated 3 times, which is a inefficient. The number of recursive calls of fib will grow exponentially as we advance in the sequence. My computer start having big problems when attempting to calculate fib(35). You could even get the result before you computer, which is a pretty bad sign! Let's find another way to remove most of that calculation.

Enters memoization

Memoization is an optimisation technique that speeds up algorithm by saving intermediate function calls which are used multiple times. In our case, if we calculate fib(n), we'll save every fib(i) with i < n.

Elixir is not designed to tackle this kind of optimisation, but you can find a javascript implementation here

Although this technique will yield much better results at a benchmark, it is not yet an optimized version of the algorithm.

Dynamic programming

The last algorithm optimization available is called dynamic programming. It seems like a complex word, and it covers a lot of techniques but in the case of Fibonacci, the algorithm is elegant and intuitive.

The first thing you have to ask yourself is: "How would I calculate fib(5)?" Let's try to make it step by step:

fib(2) = fib(1) + fib(0) = 1 + 1 = 2
fib(3) = fib(2) + fib(1) = 2 + 1 = 3
fib(4) = fib(3) + fib(2) = 3 + 2 = 5
fib(5) = fib(4) + fib(3) = 5 + 3 = 8

For each step you only used 3 explicit variables, i, fib(i), fib(i - 1), fib(i - 2) and an implicite one, the sequence number we calculate n (5 in this case). It's pretty simple to implement a function which will replicate this behavior:

def fib(0), do: 1
def fib(1), do: 1
def fib(n), do: dyna_fib(1, 1, n)

def fib_step(result, _, 1), do: result
def fib_step(fib_i_minus_one, fib_i_minus_two, i) do
	fib_step(fib_i_minus_one + fib_i_minus_two, last, i - 1)

It's a very fast implementation, it's complexity drops to O(n). This version calculates very easily the millionth element of the Fibonacci sequence!

Using Maths at our advantage

As you might know, the Fibonacci sequence is a mathematical object. Maybe maths have some interesting formulas, you can find the most interesting formula in the end of this chapter

Fib(2n - 1) = F(n)² + F(n - 1)²

Fib(2n) = (2 * F(n - 1) + F(n)) * F(n)

Those formulas are a huge improvement! They would allow to jump indices of the sequence by a factor of 2! This will allow to reduce the complexity to O(log(n)), which is quite impressive. The implementation is straight forward:

def log_fib(0), do: 0
def log_fib(1), do: 1
def log_fib(2), do: 1
def log_fib(n) when rem(n, 2) == 1 do
  # Fib(2n - 1) = F(n)² + F(n - 1)²
  i = div((n + 1), 2)
  first = log_fib(i)
  second = log_fib(i - 1)
  first * first + second * second
def log_fib(n) when rem(n, 2) == 0 do
  # Fib(2n) = (2 * F(n - 1) + F(n)) * F(n)
  i = div(n, 2)
  first = log_fib(i)
  (2 * log_fib(i - 1) + first) * first

Using a library

Instead of getting all the problems with implementing an optimized version, you should use a library that does the job for you. Gnu MP is, as far as I know, the most optimized version of Fibonacci and uses a memoized version of the O(log(n)) recursive algorithm.

I didn't think I would get so deep when starting the article. I wanted to show off with dynamic programming, but in this case it's not even the optimized version. The lesson of this article should be: always doubt on an opinion you have on a subject you don't know well. We tend to take our opinions for truth, but if we confront them to a methodological and rigorous research process, they always prove to be, at best, misleading.