Solving Project Euler Problem October, 2009
Project Euler rocks! I think it's an especially good way to learn another programming language. I'm planning to try to solve the problems in 2 ways. First, if possible, the brute force method (Which I think helps you to learn the language better) and second, if possible, the formula method (Which I think helps you learn the mathematical concepts better).
Problem #2 states:
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, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
So the first approach is using the brute force method where we iterate through all the numbers and determine the next Fibonacci number by adding the last two. I used the Seq.unfold method to do this (Which I discuss further here). Short and sweet:
let max = 4000000 let fib = Seq.unfold (fun (last, current) -> Some (last, (current, current + last))) (1, 1) let Run1 _ = fib |> Seq.takeWhile (fun i -> i <= max) |> Seq.filter (fun i -> i % 2 = 0) |> Seq.fold(fun state item -> state + item) 0 |> Display.PrintInteger
The second approach actually calculates each Fibonacci number using the Binet formula. Now this is still pretty much brute force in that we still have to iterate from 0 to the max and include only the positive values, but at least we're using a formula that doesn't require knowledge of the previous values in the sequence. Ron Knott has a nice page on calculating Fibonacci numbers and a "reduced" Binet for calculating positive integers. The reduced Binet formula is round(φn / √5). The rounding is required because of the irrational numbers in the equation. Theoretically the result would be an integer but because of limits on the number of digits we can calculate, the result will be slightly off and the rounding fixes this. I discuss calculating φ (Or the Golden Ratio) in my last post. Check that out to get a better understanding of how we calculate it.
let max = 4000000 let sqrt5 = sqrt 5.0 let Phi = (1.0 + sqrt5) / 2.0 let fibn n = Phi ** float n / sqrt5 |> round |> int let fib2 = Seq.unfold (fun index -> Some (fibn index,index + 1)) 1 let Run2 _ = fib2 |> Seq.takeWhile (fun i -> i <= max) |> Seq.filter (fun i -> i % 2 = 0) |> Seq.fold(fun state item -> state + item) 0 |> Display.PrintInteger
EDIT: After the fact I realized that my original results were skewed by the JIT compiler. Anyways, made some modifications to take this out of the equation and got more accurate results. As you can see in this case that the heavier calculations in solution 2 don't buy us any performance since we have to iterate through and find the positive numbers starting from 0 anyways. So solution 1 was the best solution in this case. However if we needed to target a specific range of Fibonacci numbers (Especially a high range) the second solution would most definitely win out.