Problem 002: Even Fibonacci Numbers

From Project Euler:
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.
There are typically two ways to work with Fibonacci numbers. You can either use the formula to generate the nth Fibonacci number, a formula that involves taking powers of the golden ratio $\phi$; or you can just simply start from the beginning and iterate through them.
For this one, we'll iterate through and accumulate values as we go along. A simple approach here would be to generate the list of Fibonacci numbers that are less than 4 million, filter out the odd ones, then reduce the list. Something like this:
(<<- (gen-fibs-to 4000000)
     (filter even?)
     (reduce +))
This has a time complexity of O(n), but it also has a space complexity of O(n). We can do better than that. Instead of first generating all the Fibonacci numbers, we can instead just stream through, accumulating values as we need to. A common pattern to do this is to define a local function that accepts an accumulator value, and add the even numbers to it. We quit when we've passed our limit.
(defn sum-even-fibs [n]
  (letfn [(accum [a b sum n]
            (if (>= b n)
              sum  ; we've passed the limit, return the total
              (accum b (+ a b)
                     (+ sum (if (even? b) b 0))
                     n)))]
    (accum 1 2 0 n)))

(println (sum-even-fibs 4000000))
Running this program gives us the correct answer very quickly (note that on my machine the JVM takes about 1.5s to start up):
$ time clj 2.clj 
4613732

real 0m1.532s
user 0m3.136s
sys 0m0.096s

No comments:

Post a Comment