Fibonacci Sequence

As The Book of F# is nearing completion I’ve suddenly found myself with a bit of something people like to call spare time. This concept has been pretty foreign to me over the past nine months so as a way to fill that time I started looking at the Project Euler problems. I’m not far along yet (my math skills have gotten rusty over the years) but so far it has been a fun exercise.

Problem 2, involves calculating the sum of the even Fibonacci numbers less than 4,000,000. In the spirit of the project, I won’t divulge my entire solution (though it won’t be hard to fill in the gaps), but I thought the algorithm for generating Fibonacci numbers was interesting so I wanted to explore it a bit along with some interesting ways we can use it to create sequences in F#.

My earliest memories of the Fibonacci sequence are from the Mathnet segment of the excellent Square One Television program on PBS. This show had such an impact on me that to this day, whenever I hear about Fibonacci I hear a parrot saying “1 – 1 – 2 – 3 – 5 – Eureka!” (The Case of the Willing Parrot conclusion & recap: Part 1 | Part 2) Since school though, I haven’t really had to do anything with the sequence. As I was relearning the math behind it, I learned that there’s a simple algorithm, called Binet’s formula, that uses the golden ratio to find the Fibonacci number at any particular index.

Binet’s formula is easily expressed in F# but to use it we first need to define the golden ratio. We could use a literal value but for more accurate calculations, particularly for larger indices, we’ll simply calculate it as follows:

let phi = (1. + sqrt 5.) / 2.

Now that we’ve defined the golden ratio as phi to be consistent with the customary mathematical notation, we can express Binet’s formula with the following function:

let getFibonacciNumber ix =
  let n = float ix
  (((phi ** n)) - ((-phi) ** -n)) / sqrt 5. |> int64

Here, the getFibonacciNumber function accepts an integer, ix, which it converts to float for use as an exponent in Binet’s formula. This is all we need to find a particular Fibonacci number. Of course, Fibonacci numbers belong to a sequence so there are a few ways to construct sequences with this function.

First is the typical comprehension syntax:

[ for i in 1..50 -> getFibonacciNumber i ]

The comprehension syntax is convenient when we know how many items we need ahead of time but, as a list comprehension, it computes every number in the range whether it’s needed or not. There are also clearly more than fifty items in the sequence so it might be more convenient to define it as an infinite sequence, instead. One approach would be to use the Seq.initInfinite function, like this:

Seq.initInfinite getFibonacciNumber

Creating an infinite sequence is convenient when you want an arbitrary number of items but it doesn’t cache results so multiple iterations means multiple calculations. Also, if you’re not careful, when you try to get values from the sequence you’ll end up stuck in an infinite loop while the internal enumerator continues applying the getFibonacciNumber function to the next index.

Using the comprehension and an infinite sequence are both pretty standard approaches so I thought it would be a bit more fun to implement Fibonacci sequence creation as a computation expression. What would be even more fun though, would be a computation expression that internally uses memoization to cache each value as it’s calculated. This is a bare-bones approach, implementing only the For and Yield methods but a more robust builder would probably also implement the While method.

open System.Threading

type CachingFibonacciSequenceBuilder() =
  let cache = System.Collections.Generic.Dictionary<int, int64>()
  let cacheLock = new ReaderWriterLockSlim()
  let getElementAt ix =
    let result =
      match cache.TryGetValue ix with
      | true, fib -> fib
      | _ -> cacheLock.EnterWriteLock()
             let fib =
               match cache.TryGetValue ix with
               | true, fib -> fib
               | _ -> let f = getFibonacciNumber ix
                      cache.[ix] <- f
  member this.For(s, f) = f s
  member this.Yield(v) = getElementAt v

Caching is done simply by using a dictionary keyed on the sequence index. I opted for a dictionary instead of ResizeArray (the standard .NET List) because the ranges used in the computation expression can be arbitrary rather than starting at zero. For locking, I thought that ReaderWriterLockSlim would be more helpful than a standard lock for controlling access to the dictionary.

In order to use the builder class effectively, we need an instance of the builder class so the compiler knows what to look for:

let fibonacci = CachingFibonacciSequenceBuilder()

With the builder class in place and instantiated, we’re now free to use them to create Fibonacci sequences in a manner that looks like natural F#, like this:

fibonacci { for i in 0..50 -> i }
|> Seq.iter (printfn "%O")

With the Fibonacci computation expression, you can easily and efficiently create multiple Fibonacci sequences, resting assured that each value will only be calculated once.

About these ads

One comment

Comments are closed.