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):
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)
end
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
end
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
end
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.