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

## Monday, 8. December 2008

### Project Euler in F# – Problem 53 – Memoization

Filed under: F#,Theoretische — Steffen Forkmann at 17:16 Uhr

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
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