A look at algorithm time complexity
I recently was asked to write a function in Elixir to generate a list Fibonacci numbers. I had forgotten the typical implementation of the algorithm for generating Fibonacci numbers but since my function was returning a list I knew I could just add the two previous numbers in the list to compute the next number. I quickly threw together an simple 8 line function and that took a number and returned a list with that many of first Fibonacci numbers in it. After writing it and testing it out I realized my function was somewhat different from the implementations I had seen. My code looked like this:
defmodule Fibonacci do
def fibonacci(number) do
Enum.reverse(fibonacci_do(number))
end
def fibonacci_do(1), do: [0]
def fibonacci_do(2), do: [1|fibonacci_do(1)]
def fibonacci_do(number) when number > 2 do
[x, y|_] = all = fibonacci_do(number-1)
[x + y|all]
end
end
With my implementation we have a function called fibonacci_do/1 with three clauses, the first two are for the first and second Fibonacci numbers and the third generates all the rest of the numbers in the sequence by adding the previous two numbers in the list and returning a list with the new number added. The function actually generates a list with the numbers in reverse order, so I defined the fibonacci/1 function to reverse the list. This function can generate the first 100,000 Fibonacci numbers in less that a second. Not too bad I thought.
Common Fibonacci in Elixir
After doing this I went and looked at the other Elixir implementations. Here are two of them:
Rosetta Code algorithm:
defmodule Fibonacci do
def fib(0), do: 0
def fib(1), do: 1
def fib(n), do: fib(0, 1, n-2)
def fib(_, prv, -1), do: prv
def fib(prvprv, prv, n) do
next = prv + prvprv
fib(prv, next, n-1)
end
end
IO.inspect Enum.map(0..10, fn i-> Fibonacci.fib(i) end)
From a gist by Dave Thomas, most of the Elixir implementations followed this pattern:
def fib(0), do: 0
def fib(1), do: 1
def fib(n), do: fib(n-1) + fib(n-2)
Now this variation is by far the most common. I’ve seen this implementation in several slide decks at Elixir conferences, and I’ve seen it used as example code many times, so I’m unsure of its origin. Dave Thomas presented this implementation at the first ElixirConf because it mirrored the mathematical formula for generating Fibonacci numbers. In this blog post I’ll call this the Dave Thomas implementation. If you were to naively use this function to generate a list of Fibonacci numbers you’d most likely do something just like the Enum.map/2 call in the Rosetta Code example above:
IO.inspect Enum.map(0..10, fn i-> fib(i) end)
Which function generates a list of Fibonacci numbers the fastest?
Looking at these three algorithms it’s clear they are have some similarities. All of them are recursive functions that start with the base cases for first Fibonacci numbers, 0 and 1. All of them take a single argument, the number in the Fibonacci sequence to generate.
But these algorithms have some key differences as well.
My function calls itself recursively and builds up a list of numbers in the sequence and returns the list directly.
The Rosetta Code function also recursively calls itself once until it has generated a number. Since it only generates a single number it must be executed multiple times to generate a list of numbers in the sequence.
The Dave Thomas algorithm differs from the two others in that it recursively calls itself not once but twice. Just like the Rosetta Code algorithm it also must be executed multiple times to generate a list of numbers in the sequence. At only 4 lines it’s by far the most succinct of the three.
Benchmarking
I opted to do simple benchmarking of these three algorithms. The benchmark script feeds the function a number N and expects the function to return a list containing the first N numbers of the first Fibonacci sequence. Only my algorithm returned a list directly, so for the other two algorithms I created a function that would map over the range and repeatedly call the fibonacci function:
def fibonacci(number) do
Enum.map(0..number, fn(n) -> fib(n) end)
end
Results
I ran the benchmark against each algorithm four times. The average run times are shown in the table below in microseconds.
| List Size | Rosetta Code | Dave Thomas | Mine |
|---|---|---|---|
| 3 | 4 | 543 | 1 |
| 5 | 2 | 3 | 0 |
| 10 | 8 | 11 | 0 |
| 20 | 5 | 880 | 4 |
| 30 | 8 | 97500 | 1 |
| 45 | 17 | 131900822 | 2 |
I’m not sure why the Dave Thomas algorithm was so slow at computing a list of the first 3 Fibonacci numbers. My guess is that CPU core was busy with something else when that number was benchmarked and it skewed the results.
As you can see these three algorithms perform very differently as the length of the list they must generate grows. Up to around 10 items the Rosetta Code algorithm and Dave Thomas algorithm perform about the same. After 10 items the run time for the Dave Thomas algorithm quickly climbs, for a list of 30 it takes nearly 1/10 a second, and for a list of 45 it takes over two minutes. The Rosetta Code algorithm performs much better. Only taking around 17 microseconds to compute a list of the first 45 Fibonacci numbers. My algorithm appears to have similar performance characteristics to the Rosetta Code algorithm, but with times that averaged less than a quarter the run time of the of the Rosetta Code algorithm. Note that the timing code was rounding to the nearest microsecond, so some computations took less than half a microsecond for my algorithm.
I decided to do a little more benchmarking of my algorithm and the Rosetta code algorithm. Since both algorithms seemed pretty fast I tried using them to generate much larger lists of Fibonacci numbers. The results are shown in the table below. Again, time is in microseconds.
| List Size | Rosetta Code | Mine |
|---|---|---|
| 100 | 76 | 5 |
| 500 | 2892 | 36 |
| 1000 | 15058 | 78 |
| 5000 | 631680 | 870 |
| 10000 | 4152261 | 4767 |
| 100000 | > 5 minutes (never returned) | 1195938 |
Clearly my algorithm performs better as it doesn’t have to generate each number from scratch each time it computes a new number in the resulting list. As the list it must generate grows in size the Rosetta Code algorithm’s run time grows exponentially. For generating a list of Fibonacci numbers it’s clear my algorithm performs the best.
Conclusion
Clearly these three algorithms have very different performance characteristics. For generating a single Fibonacci number the Rosetta Code function will work fine. My function will also work fine for generating a single Fibonacci number, but will use more memory due to the list that it builds. The Dave Thomas algorithm performs poorly for anything beyond the first 30 Fibonacci numbers and probably shouldn’t be used for anything other than exercises like this.
My algorithm, which was designed to generate a list of Fibonacci numbers, turns out to be the best algorithm for generating a list of Fibonacci numbers. Looping over the Fibonacci functions for the other algorithms greatly degrades their performance. It’s better to design a new Fibonacci function that generates the full list in one recursive call rather than reusing an existing Fibonacci function that only generates one number at a time to build the list.
Resources
- fib.ex
- https://rosettacode.org/wiki/Fibonacci_sequence#Elixir
- https://gist.github.com/pragdave/f8c7684b69d235269139bad0a2419273
- https://www.stridenyc.com/blog/tail-call-optimization-with-fibonacci-in-elixir
- https://elixirforum.com/t/pragdave-fibonacci-solution/11174/8
- https://www.nayuki.io/page/fast-fibonacci-algorithms