Project Euler: Problem 2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
The basic steps we have to take
- generate the Fibonacci sequence
- take all elements which are less than or equal to 4000000
- remove all odd items from the list
- sum up the list
Transformed from prose to Haskell it should look like the following where
fibs is assumed to be the infinite Fibonacci sequence.
euler002 :: Int euler002 = sum $ filter odd $ takeWhile (< 4000001) $ fibs
It’s compelling to translate the recursive definition of the Fibonacci sequence directly into Haskell since its so trivial.
fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) fibs :: [Int] fibs = map fib [0..]
But its horribly inefficient since we call
fib repetitively with the same parameter over and over again.
We could use memoization to save us from recalculating the same expression over and over again. Let’s try that by storing all calculated numbers in a list and use this list as a lookup table.
memo_fib :: Int -> Int memo_fib = (map fib [0..] !!) where fib 0 = 0 fib 1 = 1 fib n = memo_fib (n - 1) + memo_fib (n - 2) fibs' :: [Int] fibs' = map memo_fib [0..]
Normally you would prefer a data structure with a \(O(1)\) lookup behavior but you get the idea.
A much neater way is to use Haskell’s laziness to compute the first \(n\) numbers with \(O(n)\) additions.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Looks good, but we can optimize further if we dig deeper into the numbers.
If we replace all odd numbers with an \(O\) and all even numbers with an \(E\) we see a serial pattern.
We can use these information to create a function which generates a list featuring only the even numbers. We define a recursive function which takes the two odd numbers, creates the even number and calls itself again with the next two odd numbers.
For a better unterstanding lets rewrite the pattern \(O,O,E,O,O\) by assuming \(a\) as the first odd number and \(b\) as the second odd number.
That’s all we need to know to define a function which uses this pattern and generates a list covering only the even numbers.
evenFibs = evenFibs' 1 1 where evenFibs' a b = (a + b) : evenFibs' (a + 2*b) (2*a + 3*b)
Finally we just sum up all numbers less then or equal to 4000000 and we are done.
euler002' :: Int euler002' = sum $ takeWhile (< 4000001) $ evenFibs' 1 1 where evenFibs' a b = (a + b) : evenFibs' (a + 2*b) (2*a + 3*b)