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
my_sum [head:tail] = head + sum tail
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 [] = [1]
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.