As I said in my last post, I will look at generating Fibonacci numbers in Haskell. I will look at a simple but slow algorithm followed by a much faster version to highlight the importance of algorithm design.

First Attempt

1
2
3
4
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

This takes the basic definition of Fibonacci numbers and translates it into code. The first two numbers are both 1 and any following numbers are equal to the sum of the previous two numbers. As this function calls itself recursively twice, it is very slow and ends up preforming the same calculations twice if a number greater than three is passed as an argument.

An Improved Algorithm

1
2
3
4
5
6
7
8
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib2 1 1 n

fib2 :: Integer -> Integer -> Integer -> Integer
fib2 n n1 2 = n + n1
fib2 n n1 i = fib2 (n + n1) n (i - 1)

This function uses another “fib2″ to calculate numbers past the first two. This new function calls itself recursively, but keeps track of the last two numbers in the sequence in the first two arguments. This means that it only needs to perform a single call to itself, drastically reducing the time taken to calculate the values. The final argument simply counts down to let the function know when it has finished and to return the sum of the last two values.

Speed Comparison

I timed the running of both algorithms on my laptop (not the most powerful computer, but I think it still shows the speed difference). With the first algorithm, calculation of the 30th Fibonacci number took 16 seconds. With the second, it took only half a second. In fact in the time it took the first algorithm to find the 30th number, the second algorithm could compute the 120,000th number in the sequence.

These comparisons were done without compiling the code, so there would be some interpreter overheads involved, but as shown, these overheads had only a small impact on the overall run time.