Bill Blogs in C#

Discussion on Project Euler Problem 2

The second Euler problem asks you to find the sum of all even valued terms in the Fibonacci sequence which do not exceed 4,000,000.

Let's look at the solution from the outside in. Here's the query that finds the answer:

var EvenFibNumbers = (from n in Enumerable.Range(1, MAX)
                      let value = FibonacciSequence.Fibonacci(n)
                      where value % 2 == 0
                      select value).TakeWhile(n => n < MAX);

var answer = EvenFibNumbers.Sum();

There are a couple notes on the performance metrics used here:

The TakeWhile() method call does short circuit the query so that it does not continue calculating unneeded numbers. I could optimize this by trying to be very careful about which Fibonacci numbers I calculate, but it really doesn't matter. TakeWhile means I don't calculate them anyway. (Well, to be strictly accurate, I do calculate one more than I need, but that's no big.

Next, note the "let" statement in the query. I use that to avoid calculating the Nth Fibonacci number more than once. It just introduces a new local variable (value) and assigns it to the result of Fibonacci(n).

On this algorithm, there are some other interesting changes you could make. If you examine the Fibonacci sequence carefully, you'd see that every 3^rd Fibonacci number is even. You could, possibly, save some work by using that fact. Because of how the Fibonacci sequence is calculated, I don't think it matters. (Comment if you have a way to optimize it that I'm not seeing).

What's more interesting, to me, is how I wrote the Fibonacci sequence. I used a mix of Functional and Object Oriented techniques. (For a more functional approach, read Dustin Campbell's article on memorization: http://diditwith.net/PermaLink,guid,7191176b-c72a-49db-986e-466845665fa1.aspx)

public static class FibonacciSequence
{
    // Store all Nth Fibonacci numbers that have been calculated.
    private static Dictionary<int, long> FibnocciNumbers = new Dictionary<int, long>();

    // Return the Nth Fibonacci number.
    public static long Fibonacci(int n)
    {
        long answer;
        // If it's already been calculated, just return it.
        if (FibnocciNumbers.TryGetValue(n, out answer))
            return answer;

        // The first and 2nd numbers are 1.
        if (n < 2)
            answer = n;
        else
            // It's the sum of the previous two numbers.
            answer = Fibonacci(n - 1) + Fibonacci(n - 2);
        // Store...
        FibnocciNumbers.Add(n, answer);
        // return
        return answer;
    }
}

			

You'll note that this class uses a recursive method to calculate the Nth Fibonacci number. However, it will only calculate each number in the sequence at most once. Once a calculation has been performed, the answer is stored in a private dictionary for later use. Rather than try and twist your brain around many of the more advanced Functional programming concepts, using C# 3.0, you can mix good old fashioned oo programming with good old fashioned functional programming. Cool!

Stay tuned for more on Friday, when I write up the notes on problem 3.