Slow Haskell and Python code with Project Euler #2

Question

I was practicing a bit with Haskell to get to know the language (It's amazing) so I went to project euler and did problem #2 which took quite a while (~ 30-40s I don't know how long exactly) to finish. I wondered why it took so long so I tried the same with F#, C# Javascript and Python. F# and C# took a couple of ms to finish as well as javascript but python took more time than Haskell did. Why is that? These are my implementations

Haskell

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

genFibs n maxVal = 
if fib n < maxVal then 
    fib(n):(genFibs (n+1) maxVal) 
else []

totalSum = sum (filter even (genFibs 1 4000000))

main = print totalSum

F#

let rec fib n = 
    match n with
    | n when n < 2 -> 1
    | n -> fib (n-1) + fib (n-2)

let rec genFibos n max = 
    match fib(n) < max with
    | true -> fib(n)::(genFibos (n + 1) max)
    | false -> []

genFibos 1 4000000
|> Seq.where (fun n -> n % 2 = 0)
|> Seq.sum

C#

static int Fib(int n)
{
    return n < 2 ? 1 : Fib(n - 1) + Fib(n - 2);
}

public static int EvenFibs()
{
    var n = 1;
    var totalSum = 0;
    var num = 1;
    while(num < 4000000)
    {
        num = Fib(n);
        if (num % 2 == 0) totalSum += num;
        n += 1;
    }
    return totalSum;
}

Python

knownVals = { }
def fib(n):
if n not in knownVals:
   knownVals[n] = 1 if n < 2 else fib(n-1) + fib(n-2)
return knownVals[n]

n = 1
stillCounting = True
totalSum = 0

while stillCounting: 
    num = fib(n)
    if num > 4000000:
        stillCounting = False
    else:
        if num % 2 == 0:
            totalSum += num
        n += 1

print(totalSum)

Javascript

(function () {

function fib(n) {
    return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}

var totalSum = 0;
var num = 1;
var n = 1;

while(num < 4000000)
{
    num = fib(n);
    if (num % 2 == 0) totalSum += num;
    n += 1;
}

alert(totalSum);

})();

So can someone explain why Haskell and Python were slow and the F# and C# were fast on this and how I can enhance it? Any help would be appreciated!

EDIT: Haskell code corrected, Python better implementation using memoization

Answer 1

Your Haskell implementation is simply wrong: it never completes because:

fib n = (fib n - 1) + (fib n - 2)

is the same as:

fib n = (fib n) - 1 + ((fib n) - 2)

which diverges.

The correct implementation:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

genFibs n maxVal
  | fib n < maxVal = fib n : genFibs (n+1) maxVal
  | otherwise = []

totalSum = sum $ filter even $ genFibs 1 4000000

main = print totalSum

Runs in about 1 second on my machine:

$time ./fibo 
4613732

real    0m1.334s
user    0m1.324s
sys     0m0.009s

The problem with the python solution is that the interpreter isn't introducing any kind of optimization or memoization for the double recursive call. This means that the algorithm takes exponential time to compute the answer. It's pretty easy to come up with a polynomial time algorithm:

def fibo(n):
    prev, cur = 0, 1
    for i in range(n):
        prev, cur = cur, prev + cur
    return cur

Which results in:

In [8]: %%timeit
   ...: tot = 0
   ...: n = 0
   ...: while True:
   ...:     num = fibo(n)
   ...:     if num > 4000000:
   ...:         break
   ...:     elif num % 2 == 0:
   ...:         tot += num
   ...:     n += 1
   ...:     
10000 loops, best of 3: 54.8 µs per loop

My guess for the speed of F# and C# is that the compiler is introducing some form of memoization to avoid exponential growth. Although the problem may still be too small to notice the exponential growth in function calls. If you try to increase the 4000000 to 400 hundred millions or more, you can definitely check if this is true.

Answer 2

try memoizing it

known_fibs={}
def fib(n):
    if n not in known_fibs:
        known_fibs[n] = 1 if n < 2 else fib(n-1) + fib(n-2)
    return known_fibs[n]

Answer 3

You want to find out where all the time is going, right? Don't think of it as measuring time. Think of it as finding lines of code that are on the stack a large fraction of the time, regardless of the total. Here's an example: How to improve performance of this code?

Many profilers fall into the gprof traps, including ignoring blocked time, thinking that lines of code don't matter, thinking that "self time" does, and thinking that measurement has to be accurate

Answer 4

The recursive definition of the Fibonacci function is a terrible way to solve this problem. Here's a JavaScript implementation that runs essentially instantaneously:

function evenFibSum(limit) {
  var
    pf, f, t, sum;

  for (pf = 1, f = 2, sum = 0; f <= limit; t = f, f += pf, pf = t)
    if (!(f & 1)) sum += f;

  return sum;
}
console.log(evenFibSum(4000000));

Recursively generating each value as you work through the whole list is doing way too much work, and it's extremely simple to iteratively compute the values. Memoizing the recursive definition helps but it seems needlessly complicated to me.