Rash thoughts about .NET, C#, F# and Dynamics NAV.

Last time I showed how one can solve the Euler Project – problem 53 with the help of Dynamic Programming and a two-dimensional array. This time I will use another technique called (automatic) memoization.

First of all I need a memoization-function. There are two different approaches, one with a System.Collections.Generic.Dictionary and one with an immutable Map. You can read Don Syme’s blog posting to get more information about the differences.

let memoizeWithMap f =
  let cache = ref Map.empty
  fun x ->
    match (!cache).TryFind(x) with
      | Some res -> res
      | None ->
           let res = f x
           cache := (!cache).Add(x,res)
           res

open System.Collections.Generic

let memoizeWithDictionary f =
  let cache = Dictionary<_, _>()
  fun x ->
    let (found,result) = cache.TryGetValue(x)
    if found then
      result
    else
      let res = f x
      cache.[x] <- res
      res

With the help of one of this generic memoization-functions I can create a recursive function for the binomial coefficients, which memoizes intermediate data:

let rec binomial =
  let f (n,k) =
    if k = 0I || n = k then
      1I
    else
      binomial(n - 1I,k) + binomial(n - 1I,k - 1I)
  f |> memoizeWithDictionary

let answer =
      seq { for n in 2I .. 100I do
              for k in 2I .. n -> n,k }
       |> Seq.filter (fun (a,b) -> binomial (a,b) > 1000000I )
       |> Seq.length

answer |> printf "Answer: %A"

It turns out that memoizeWithDictionary is much faster for this problem. But with 160ms it is still slower than the comparable version with a two-dimensional array (45ms).