...Other Project Euler posts...
Today, my mission is to solve Project Euler Question #2:
Find the sum of all the even-valued terms in the fibonacci sequence which do not exceed four million.
The obvious solution is to use a brute force approach:
public static int Problem2() {
var fib = 0;
var sum = 0;
for (var n = 0; fib < 4000000; n++)
{
fib = Fibonacci(n);
if (fib % 2 == 0)
sum += fib;
}
return sum;
}
private static int Fibonacci(int n) {
return n < 2 ? 1 : Fibonacci(n - 2) + Fibonacci(n - 1);
}
Lazy evaluation
Slightly more elegant solutions do exist. For starters, F# allows us to use lazy evaluation to create sequences of values. This has the advantage of sequence values only being evaluated when necessary. Robert Pickering's "Foundations of F#" gives us the following example for generating fibonacci numbers using lazy evaluation. In fact, the example here is one of an infinite list.
#light
let fibs = (1, 1) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))
Initially, a pair of values (named a tuple) 1 and 1 is piped through to the Seq.unfold function. The unfold function allows us to define how we want our list to be generated. It returns a disciminated union type called Option which in this case is called with a tuple, the first value in the tuple being the value applied to the list, the second value is the accumulator. The accumulator basically allows you to pass some state into next round of calculations. Option types are there own blog post, as they are a totally awesome example of applied discriminated unions.
To put the fibs function into english: fibs takes a tuple of integers (n0, n1), and always returns the first member in the tuple, however when we evaluate the next item in the sequence, the first member of the tuple will be n1 and the second will be n0 + n1. This will go on and on even once we hit the 32bit limit and starting looking at negative integers.
Pattern matching
So how does this help us to solve question two? Using a similar approach as the C# version we could alter the way the list is generated before we summate:
#light
let summate x = x |> Seq.sumByInt (fun n -> n)
let Question2 =
(1, 1)
|> Seq.unfold(fun (n0, n1) ->
match n0 with
| n0 when n0 % 2 = 0 -> Some(n0, (n1, n0 + n1))
| n0 when n0 > 4000000 -> None
| _ -> Some(0, (n1, n0 + n1)))
|> summate
Here, I'm using simple pattern matching to do two things, make sure any numbers that arent even are mapped to 0, and also to ensure that once n0 exceeeds 4 million, we stop generating values in the list. This is the power of the unfold function at play: the ability to lazily evaluate the members of the list and also to define the condition to terminate the list.
A Mathematical approach
However, this is still a brute force approach, although dressed up a little. Since the fibonacci set is full of patterns and properties surely we can take advantage of one or three? Of course, each 3rd term in the fibonacci set happens to be even. We also have an approximate ratio between two consequetive terms: Phi. Therefore, the ratio between even terms is approximately Phi to the power of 3. Using these properties we should be able to come up with the same answer as our brute force approach:
#light
let summate x = x |> Seq.sumByFloat (fun n -> n)
let PhiCubed = ((sqrt(5.0) + 1.0) / 2.0) ** 3.0
let Question2 =
2.0
|> Seq.unfold (fun x -> match x with
| x when x < 4000000.0 -> Some(x, Math.Round(x * PhiCubed))
| _ -> None)
|> summate
So with a starting point of 2.0 I simply round the result of x * (Phi ^ 3) to yield each value in my list which is then summed. The C# interpretation as follows:
public static double Problem2() {
return EvenFibsBelowFourMillion().Sum();
}
private static IEnumerable<double> EvenFibsBelowFourMillion() {
var phiCubed = Math.Pow(((Math.Sqrt(5D) + 1D) / 2D), 3);
var fib = 2D;
do {
yield return fib;
fib = Math.Round(fib * phiCubed);
} while (fib < 4000000);
}
In Summary
C# still outperforms F# ever so slightly on my machine, C# taking an average 0.002 milliseconds, F# taking an average 0.003 milliseconds. So far I feel that F# lives up to the promise of a 'similar performance profile as C#'. I'm starting to appreciate the 'point and shoot' nature of F# syntax. Having said that, the C# solution is equally nice and easy to read. I cant wait to get into some of the meatier questions.