Learning to Fib Correctly
I have been looking into Elixir and I am enjoying the language (mainly from both a readability standpoint, I haven't done enough to form an opinion about its performance benefits). I read the chapter on recursion and then applied it to a quick and dirty Fibonacci implementation (my favourite way to learn recursion in a new language). It is as easy ascreating a new file called fib.ex and adding the following:
# Filename: fib.ex
defmodule Fib do
def print(0) do 0 end
def print(1) do 1 end
def print(n) do
print(n-1) + print(n-2)
end
end
Then compile.
$ elixirc fib.ex
It works well and is simple to read. I then found myself searching the Internet for similar Fibonacci examples in Elixir to make sure I was writing it properly (style and such). The funny thing was, they all looked like mine. That's great and all, and it is probably enough to pass an interview question, but it's actually wrong.
The current implementation, and this is the basic way that most examples teach you to solve Fibonacci, is so horribly CPU-intensive that it'll never return if you attempt to calculate the 5000th Fibonacci number. Not only that, you will pin your CPU at 100% for the entirety of the time, unless of course the stack doesn't overflow (this will happen in languages like Python). For a novice learning Fibonacci, they'll get frustrated why their program stops working at even the smallest of numbers.
As the Fibonacci number increases, the time gets very bad. To test this out, we create a simple script that asks the module to calculate a seemingly small number.
# Filename: fibtest.exs
IO.puts Fib.print(40)
Running this on the command line we can see the it took the system a full 10 seconds to calculate the answer.
$ time elixir fibtest.exs
102334155
real 0m10.432s
user 0m10.403s
sys 0m0.122s
The reason this is happening is because the system is seeing the following if we decompose the function calls into discrete steps:
result = print(4)
result = (print(3) + print(2))
result = ( (print(2) + print(1)) ) + ( (print(1) + print(0)) )
result = ( ( (print(1) + print(0)) ) + 1 ) + ( (1 + 0 ) )
result = ( ( (1 + 0) ) + 1 ) + ( 1 )
result = ( ( 1 ) + 1 ) + ( 1 )
result = 3
You'll see that the computer is constantly asking itself to calculate other values of the Fibonacci sequence before it can continue onto the next branch. So the computer has to keep a lot of data around in its memory, and that memory is rapidly consumed the more it calculates smaller numbers. Add onto that the fact that the computer is, oftentimes, calculating the same numbers multiple times (look at how many times print(2) is calculated). A more efficient way would be for the computer should instead remember this number and save it for later. Alas, mathematical algorithms don't allow for that.
With all of this, there are few examples teaching people to properly implement Fibonacci so that it works within a computing environment and not simply a mathematical model. Enter tail recursion. This not only allows the program to lightly use CPU and memory, but it also makes Fibonacci as fast as possible (with the exception of pre-determined value lookups).
My feeling is that people learn algorithms like Fibonacci by first learning the sequence pattern, but then are told the algorithm. So people go out and implement the algorithm as it exists in the Math textbooks. Instead, people should be implementing it as if they were asked to start calculating the Fibonacci number (start at the smallest number, the sentinel, and count up until you reach the Nth number you are counting for).
Here's our second, faster implementation.
# Filename: fib.ex
defmodule Fib do
def print(n, current \\ 0, sum \\ 1)
def print(0, _, sum) do sum end
def print(n, current, sum) do
print(n-1, sum, sum + current)
end
end
Let's check the speed now. The program goes from 10 seconds to less than half a second.
$ time elixir fibtest.exs
102334155
real 0m0.386s
user 0m0.354s
sys 0m0.119s
What makes the new implementation so fast? Think of it in these set of steps:
Fib.print(40)
--> print(40, 0, 1)
--> print(39, 1, 1)
--> print(38, 1, 2)
--> print(37, 2, 3)
--> print(36, 3, 5)
--> print(35, 5, 8)
--> print(34, 8, 13)
--> print(33, 13, 21)
... and so on until ...
--> print(0, 63245986, 102334155) # 102334155 is our number
If you look at the 3rd argument, you'll see the Fibonacci sequence is being formed (1,1,2,3,5,…). The computer only needs to execute the print function n times, for the value given to Fib.print(n).
This implementation is the way that Fibonacci should be shown in examples and not the inefficient one (except in Math textbooks). The other way leads the programmer to forget about memory and CPU limits, which mathematics doesn't need to deal with. Admittedly, converting an algorithm to be tail-recursive is not at all easy. Thus, for interviewers asking for a Fibonacci algorithm, walk the candidate through the creation of the tail-recursive version and have them explain to you why it is more efficient.
Anecdotally, I still meet people who think that CPU, RAM, and disk space are limitless. To fix a long-running task, they think they can just throw more servers at a problem and it will resolve itself. A simple recursive algorithm like Fibonacci shows that this doesn't work.
What about when I mentioned that asking for the 5000th Fibonacci number with the inefficient implementation will never return? Let's test it in the new implementation. (note: line breaks have been added for clarity)
$ time elixir fibtest.exs
38789684543883256337019163083259053120821277146462451061605972
14895550139044037097010822916462210669479293452858882973813483
10200895498294036143015691147893836421656394410691021450563413
37065586562382546567007125259299038549338139288363783475189087
62970712033337052923107693008518093849801803847813996748881765
55465378829164426891298038461377896902150229308247566634622492
30718833248032803750391303529033045058427011476352422702109346
37699104006714174883298422891491273104054328753298044273676822
97724498774987455569190770388063704683279481135897373999311010
62193081490185708153978543791953056175107610530756887837660336
67355445258844886241619210553457493675897849027988234351023599
84466393485325641195222185956306047536464547076033090242080638
25849291564528762915757591423438091423029174910889841552098544
32486594079793571316841692868039545309545388698114665082066862
89742063932343848846524098874239587380197699382031717420893226
54688793640026307977800587591296713896342142525791168727556003
60311370547754724604639987588046985178408674382863125
real 0m0.401s
user 0m0.371s
sys 0m0.125s
That's a big number. There is a negligible increase in time to move from Fib(40) to Fib(5000). Pretty awesome.