# Even Fibonacci numbers

This is a solution for Even Fibonacci numbers.

``````fibonacci 0 = 1
fibonacci 1 = 1
fibonacci p = (fibonacci (p-1)) + (fibonacci (p-2))

-- fs is all even fibonacci number below 4000000
fs = [ fibonacci n | n <- [0..], fibonacci n < 4000000, even (fibonacci n) ]

-- get the sum of all these values
main = print \$ sum fs

-- Notes:

-- test by showing the 5 first values of fs
-- main = print \$ take 5 fs

-- even and sum is part of haskell
-- my_even and my_sum are re-implementations as an example

my_even n = n `mod` 2 == 0

my_sum [] = 0
``````

This is obviously not a good solution, because it doesn't finish. For some reason haskell is not able to keep the previous calculations of `fibonacci n` in memory when the next is calculated so the performace is exponentially slow for higher numbers of fibonacci.

According to The Fibonacci sequence the naive implementation requires `fib n` additions. But I don't understand why results cannot be kept to limit number of additions to `n`.

A simplified variant do finish, but its not fast either.

``````fibonacci 0 = 1
fibonacci 1 = 1
fibonacci p = (fibonacci (p-1)) + (fibonacci (p-2))

-- get the sum of all these values
main = print \$ sum \$ filter (even) \$ takeWhile (< 4000000) \$ [ fibonacci  n | n <- [0..33] ]
``````

Compile with optimization and it will work

``````ghc -O euler2.hs
./euler2
``````

Another more direct iterative solution is much more performant which results in 4613732.

``````-- add the next fibonacci number to an existing sequence
nextfib :: [Integer] -> [Integer]
nextfib []         = 
nextfib (a:[])     = [1,1]
nextfib (a:b:tail) = (a+b):a:b:tail

fastfib :: Integer -> [Integer]
fastfib n = foldl (\s _ -> nextfib s) [] [1..n]

-- get the sum of the even fibonacci numbers below 4000000 among the first 50
main = print \$ sum \$ filter even \$ takeWhile (< 4000000)  \$ reverse \$ fastfib 50
``````

This one can calculate arbitrary size.