First we implement a function for computing terms of the Fibonacci sequence.
let rec fib n = if (n = 1 || n = 0) then 1 else fib(n-1) + fib(n-2)
We pipe that into a sequence generator, taking all even terms not exceeding four million, and then sum them.
let problem2a = fib |> Seq.initInfinite |> Seq.takeWhile (fun i -> i <= 4000000) |> Seq.filter (fun i -> i % 2 = 0) |> Seq.sum
Here's another solution which is about 40 times faster. On my computer it takes 3ms instead of 117ms.
ReplyDelete(0,1)
|> Seq.unfold (fun (a,b) -> Some(a+b,(b,a+b)))
|> Seq.takeWhile (fun i -> i <= 4000000)
|> Seq.sumBy (fun i -> if i%2 = 0 then i else 0)
The standard recursive function for calculating Fibonacci numbers is great for calculating individual elements of the sequence but poor for creating a complete sequence. That's because it creates each number from scratch. An unfold solution like the one above is far superior, as it builds directly on the two previous numbers, thus avoiding any redundant looping.
Seq.unfold is both elegant and efficient here!
ReplyDelete