Why is this simple O(n) Haskell algorithm behaving more like O(2^n)? [duplicate]

Question

Haskell caches results of pure function calls, one of the many reasons for the separation between pure and impure behavior. Yet this function, which should run in O(n) where n is 50 below, runs really slowly:

lucas 1 = 1
lucas 2 = 3
lucas n = lucas (n-1) + lucas (n-2)
map (lucas) [1..50]

The first thirty terms or so together compute in under a second, then 31 takes half a second or so, 32 takes a full second, 33 takes a few seconds, 34 takes 6 seconds, 35 takes 11 seconds, 36 takes 17 seconds...

Why is this function so slow? If the GHC interactive runtime is caching results, then each call to lucas should only involve summing of the two previous cached terms. One addition operation to find term 3, one additional addition to find term 4, one additional addition to find term 5, so term 50 is reached with only 48 additions total considering caching. The function shouldn't take anywhere near a second to find at least the first few thousand terms, why is the performance so terrible?

I've been waiting for more than half an hour now for lucas 500 to compute.

Answer 1

The reason your version is very slow is that there is no memoization of the lucas (n-1) and lucas (n-2) parts - so both values will be recalculated (recursively) over and over again - which is painfully slow.

The solution is to keep the calculated values somewhere:

using list-lazyness

Here is a simple version that will do the same as your code-snippet but should be way faster - it will keep the already calculated parts in the list itself:

lucasNumbers :: [Integer]
lucasNumbers = 1:3:zipWith (+) lucasNumbers (tail lucasNumbers)

first50 :: [Integer]
first50 = take 50 lucasNumbers

the reason why this is faster is that now the lazyness of the list will help you memoize the different parts

You can learn much about this if you look for Fibonacci sequences in Haskell (it's really just the same as yours ;) )

using unfoldr

another (maybe less magic seeming) way to do this is using Data.List.unfoldr - here the already calculated parts (or those that matter - the last and second-to-last elements) will be in the state you pass around for the unfold operation:

lucasNumbers :: [Integer]
lucasNumbers = unfoldr (\ (n,n') -> Just (n, (n',n+n'))) (1,3)

---

to your comment/question:

assuming you are talking about x(n) = x(n-1)^2-2 then you can do it like this:

lucasLehmer :: [Integer]
lucasLehmer = 4 : map (\ x -> x^2-2) lucasLehmer

which will yield something like this:

λ> take 5 lucasLehmer
[4,14,194,37634,1416317954]

maybe you should try the unfoldr version yourself