Haskell Fibonacci seems slow

Question

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.

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, Dec 17 '14 at 16:01
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](https://www.haskell.org/haskellwiki/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, Dec 17 '14 at 17:23

score 10 · Accepted Answer · edited May 23 '17 at 11:50

10

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.

edited May 23 '17 at 11:50

Community

1
1

answered Dec 17 '14 at 15:59

Frerich Raabe

90,689
19
115
207

The memoization link explained the issue very well. – Dec 17 '14 at 16:06
Both questions and their answers are rather esoteric. What about *the* textbook metod? – n. m. could be an AI Dec 17 '14 at 16:07
@n.m. Depending on what textbook you're used to you may find that the haskellwiki link shows 'the textbook method' (in the section 'Memoization with recursion'). – Frerich Raabe Dec 17 '14 at 16:09
3

I don't know how one could miss `fib=0:1:zipWith (+) fib (tail fib)` en route to higher-order enlighenment. It's *the* textbook example of *everything*. I can type it on my phone without looking (I just did). – n. m. could be an AI Dec 17 '14 at 16:21
@n.m. To begin with, your definition doesn't typecheck `fib :: Int -> Int`. That aside, feel free to add your favorite `fib` definition(s) in a separate answer if you feel like they add something - [this Wikipedia page](http://en.wikipedia.org/wiki/Haskell_%28programming_language%29#Code_examples) has some inspiration. ;-) – Frerich Raabe Dec 17 '14 at 16:27
1

How this answer could get so many upvotes in such a short time is beyond me. It's very close to being a link-only answer... – jub0bs Dec 17 '14 at 16:39
1

It's not of that type. It is used [like this](http://ideone.com/3ZqMgC). I'm not sure whether it's a good candidate for an answer though. – n. m. could be an AI Dec 17 '14 at 16:44

score 6 · Answer 2 · answered Dec 17 '14 at 16:00

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.

Technically, its complexity is `O(fib n)` hence roughly `O(1.68^n)`, which is slightly better than `O(2^n)`. This does not affect your point, though: its complexity is still exponential so the amount of recursive calls quickly becomes unpractical. — chi, Dec 17 '14 at 16:11

score 4 · Answer 3 · answered Dec 17 '14 at 17:02

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]

score 0 · Answer 4 · answered Dec 19 '18 at 19:36

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

Haskell Fibonacci seems slow

4 Answers4