### UPDATE: 2012/07/13

It wasn’t a Haskell idiosyncrasy or my lack of Haskell skills after all (of which I have extremely little.) It was just a bug. My Haskell program had the wrong Fibonacci upper bound set at 40,000,000 instead of 4,000,000.

uber_bound = 40000000 -- OOOPS!!!! It should be 4M, not 40M.

Thanks StackOverflow. Many pair of eyes >> mine own. I leave the rest of the original post (including the bug) as it were.

### SPOILER ALERT: 2012/07/12 – Please don’t look at this if you are trying to solve Project Euler’s problem #2 on your own w/o looking at the answer.

I’ve already completed problem #2 of Project Euler (computing the sum of all even Fibonacci(n) numbers less than or equal to 4 million) – I’m using these problems to practice my C/Ada bread-n-butter skills, to revisit my Common Lisp and to learn Haskell. My typical approach (and current goal) is to do a C implementation first (brute-force if necessary) to compute the right result. Then I refine the program (step-wise refinement, nested functions, recursion, etc) into Ada, Lisp and Haskell (the later being my target of learning.)

When I’m trying to re-implement my solution in Haskell, I’m running into a problem. In classical fashion, it is calculating the wrong answer. However, I think my Haskell implementation resembles my Common Lisp one (which does produce the correct result.)

The algorithm only computes the Fibonacci number for n where n % 3 == 0. This is because we need to sum only the even-valued Fibonacci numbers F(n) <= 4M, and

Here is the Haskell implementation:

-- Created on 2012-07-12 -- 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. -- -- SOLUTION (in C): -- 1. computer the fibs(n) by brute force, starting from n=0 -- 0 1 1 2 3 5 8 13 21 34 55 89 144... -- 2. Then, notice the following: -- (n % 3 = 0 ) -> ( fibs(n) % 2 == 0 ) -- 3. By computing the fibs of only those numbers multiple of 3 -- (including 0), we reduce the number of calculations by 1/3 -- EXPECTED VALUE : 4613732 uber_bound = 40000000 -- Upper bound (exclusive) for fibonacci values expected = 4613732 -- the correct answer -- The implementation amenable for tail-recursion optimization fibonacci :: Int -> Int fibonacci n = __fibs (abs n) 0 1 where -- The auxiliary, tail-recursive fibs function __fibs :: Int -> Int -> Int -> Int __fibs 0 f1 f2 = f1 -- the stopping case __fibs n f1 f2 = __fibs (n - 1) f2 (f1 + f2) -- NOT working. It computes 19544084 when it should compute 4613732 find_solution :: Int find_solution = sum_fibs 0 where sum_fibs :: Int -> Int sum_fibs n = if fibs > uber_bound then 0 -- stopping condition else -- remember, (n % 3 == 0) <--> (fib(n) % 2 == 0) -- so, seek the next even fibs by looking at the -- the next n = n@pre + 3 fibs + sum_fibs (n + 3) where fibs = fibonacci n actual = find_solution problem_2 = (expected == actual)

The thing is printing 19544084 when the correct answer is 4613732. My Common Lisp solution (which does work) is below.

I thought my Haskell implementation would resemble it, but I’m missing something.

(set `expected 4613732) ;; the correct answer ;; very inefficient recursive implementation (defun crappy_fibonacci (x) (cond ((<= x 0) 0) ((= x 1) 1) (t (+ (fibonacci (- x 1)) (fibonacci (- x 2)) ) ) );; end cond ) ;; end naive_fibonacci ;; tail-recursive fibonacci (defun fibonacci (n) (labels ( ;; define an auxiliary fibs for tail recursion optimization (__fibs (n f1 f2) (if (<= n 0) f1 ;; the stopping condition (__fibs (- n 1) ;; decrement to ensure a stopping condition f2 (+ f1 f2)))) ) ;; end tail_rec_fibs auxiliary (__fibs n 0 1) );; end labels ) ;; end fibonacci (defun sum_fibs(seed) (let* ((f (fibonacci seed))) (if (> f 4000000) 0 ;; else (+ f (sum_fibs (+ 3 seed))) );; end if );; end of let );; end of sum-fibs (defun solution () (sum_fibs 0)) (defun problem_2 () (let ( (actual (solution)) ) (format t "expected:~d actual:~d" expected actual) (= expected actual) ) ) ;; end of problem_2 defun

#### What on Earth am I doing wrong?

Granted that I’m using a Neanderthal approach to learning Haskell (I’m currently just re-implementing my Lisp on Haskell as opposed to learning idiomatic Haskell, the coding/problem solving approach that goes with the language.)

I’ve put my question on StackOverflow. Hopefully I’ll get an answer 🙂 In the meantime, however…

Posted on July 13, 20120