Project Euler Problem 2

 •  • 

Lately I’ve been exploring Project Euler as a way to get started with Clojure. This post will feature solutions to Project Euler Problem 2 in C# and Clojure, so if you’re trying to avoid spoilers then now’s your chance to look at puppies instead. Problem 2 is defined as:

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.

I like to start out with the simplest approach I can find. A plain old loop should do the trick:

public static void Problem2_Loop()
{
  var sum = 0;
  var x = 0;
  var y = 1;
  int nextFib;
  do
  {
      nextFib = x + y;
      if (nextFib % 2 == 0)
          sum += nextFib;

      x = y;
      y = nextFib;
  } while (nextFib < 4000000);

  Console.WriteLine(sum);
}

This seems pretty efficient. I wanted to give recursion a shot, though, just for comparison’s sake:

public static void Problem2_Recursive()
{
  Console.WriteLine(EvenFibonacciToLimit(4000000).Sum());
}

private static IEnumerable<int> EvenFibonacciToLimit(int limit)
{
    var tester = new Func<int, bool>((item) => item % 2 == 0);
    return FibonacciToLimit(limit, null, tester);
}

private static IEnumerable<int> FibonacciToLimit(int limit, List<int> sequence = null, Func<int, bool> tester = null, List<int> filteredSequence = null)
{
    if (sequence == null)
        sequence = new List<int> { 0, 1 };

    var nextFib = sequence[sequence.Count - 1] + sequence[sequence.Count - 2];
    if (nextFib >= limit)
        return tester == null ? sequence : filteredSequence;

    sequence.Add(nextFib);
    if (tester != null && tester(nextFib))
    {
        if (filteredSequence == null)
            filteredSequence = new List<int>();

        filteredSequence.Add(nextFib);
    }

    return FibonacciToLimit(limit, sequence, tester, filteredSequence);
}

How do the two stack up? The loop is faster, averaging <1ms per 1000 calls, while the recursive solution takes ~1ms. This makes sense given that the recursive solution has the List overhead. We could strip those out in favor of ints to speed it up, as I do in my Clojure solution. As always, you can plug this into the online REPL to verify it:

(defn fib-even [limit]
  (loop [x 0 y 1 acc 0]
   (let [term (+ x y)]
    (if (< y limit)
     (recur y term (if (even? term) (+ acc term) acc))
     acc))))

(println (fib-even 4000000))

This averages 1.2μs per call and seems pretty clean to me. Note that the benchmarks aren’t comparable between languages as they’re running on totally different machine configurations. Do you have a better solution? Let me know on Twitter!