Haskell Fibonacci seems slow

7
votes

I'm learning 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 ok, and loading this script into the GHCI REPL I could mess around with a few numbers. I tried 

fib 33

and was surprised that it took about 4 seconds to give the result. (Sorry I don't know how to time a function in Haskell yet, so counted myself).

Fib 33 isn't particularly taxing. The answer is less than 4 million. So I'm assuming my code is not very well written or there is some issue with the way I am doing recursion perhaps (well, it isn't well written in that it doesn't take into account negative integers). The question is, why is it slow? Any help appreciated.

4
haskellfibonacci
This question seems to be a good one for CodeReview. – Alexander
When looking at your code, just imagine how often for example fib(5) is calculated. Every iteration, you calculate all "inner" fibonacci numbers again. – WeSt
You should use the classic lazy infinite list version: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) with fib n = fibs!!n. See the haskell wiki about the Fibonacci sequence. It's amusing that Fibonacci is famous for this sequence, which was just a little exercise in the book he should be famous for, which introduced place value to Western Europe. – AndrewC

4 Answers

10
votes

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

6
votes

Did you compare that time to other languages?

This is recursive algorithm that has O(2^n) complexity. At n=33 that gives a staggering amount of calls. If you count how many miliseconds or nanoseconds there were per such call you are left with a very remarkable answer as to the actual performance.

Remember, that some compilers/execution environment might cache function return values (Frerich had better memory to how it is called: memoization), which improves performance in case of this algorithm greatly. In this case it doesn't happen, so all those 2^n recursive calls do happen.

4
votes

Your algorithm is not very good. You can improve it a little bit using memoization, up to O(n). Using divide and conquer, you can get up 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 braces on 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 already has this implemented in its default library for (^).

This works indeed:

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]
0
votes

Here is an optimized version with a helper function. Still slower than lazy infinite list given above, but much more straightforward for newbies 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' a b i n = if i > n then b else fib' b (a + b) (i + 1) n

P.S: works with positive numbers only