Haskell Fibonacci seems slow

Question

I am studying Haskell and I wrote a simple Fibonacci function:

fib :: Int -> Int fib 1 = 1 fib 0 = 0 fib n = (fib (n-1)) + (fib (n-2)) 

It seems to compile fine, and by loading this script in the GHCI REPL, I could combine with multiple numbers. I tried

 fib 33 

and was surprised that it took about 4 seconds to get the result. (Sorry, I don’t yet know how was the time in Haskell, so I considered myself).

Fib 33 is not particularly taxed. The answer is less than 4 million. Therefore, I assume that my code is not very well written or there are some problems with the way I do recursion (well, it is not so well written that it does not take into account negative integers). The question is why is it slow? Any help was appreciated.

Answer 1

The evaluation took longer than you expected, because your function does not use memoization . See this question or this question for answers to the question of how to define the fibonacci function in Haskell using memoization.

Answer 2

Have you compared this time with other languages?

This is a recursive algorithm having complexity O (2 ^ n). With n = 33, which gives a staggering amount of calls. If you consider how many milliseconds or nanoseconds there were for such a call, you will be left with a very wonderful answer regarding the actual performance.

Remember that some compilers / runtimes can cache function return values ​​(Frerich had better memory, as it is called: memoization), which greatly improves performance in the case of this algorithm. In this case, this does not happen, so all these 2 ^ n recursive calls occur.

Answer 3

Your algorithm is not very good. You can improve it a bit using memoization, down to O (n). Using divide and conquer, you can go to O (log n):

 import Data.Matrix fib :: Integer -> Integer fib n = ((fromLists [[1,1],[1,0]]) ^ n) ! (1,2) 

The idea is that multiplication is associative, so you can put your curly braces in strategic places:

5 ^ 10 = (5 * 5 * 5 * 5 * 5) * (5 * 5 * 5 * 5 * 5) = (5 * 5 * 5 * 5 * 5) ^ 2 = ((5 * 5) * ( 5 * 5) * 5) ^ 2 = ((5 * 5) ^ 2 * 5) ^ 2 = (((5 ^ 2) ^ 2) * 5) ^ 2

The same pattern can be applied to matrix multiplication. And Haskell has already implemented this in its default library for (^) .

This really works:

 map fib [1..21] --! [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946] 

Answer 4

Here is an optimized version with an auxiliary function. Still slower than the lazy endless list above, but much easier for beginners like me!

 fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib' 0 1 2 n fib' :: Integer -> Integer -> Integer -> Integer -> Integer fib' abin = if i > n then b else fib' b (a + b) (i + 1) n 

PS: only works with positive numbers