C# and Memoization

I'm finally beginning to understand why people like C# - it's familiar for C++-programmers and it includes some of those powerful constructs from functional programming I was always missing when writing code in C++. Not having to worry about freeing memory is nice, too.

Imagine my excitement when we had to write an easy integer factorizer to simulate a workload task related to threading. I knew I could do closures, so it would be trivial to do memoization to speed up this task, too.

Let's start with the following simple function to check if a number is a prime number. Note the caching of the square root - otherwise it would calculate the square root with every loop - and that's expensive.

static bool isPrim(ulong n) {
  if (0 == (n % 2)) {
    return false;
  }
  double x = Math.Sqrt(n);
  for (ulong i = 3; i <= x; i += 2) {
    if (0 == (n % i)) {
      return false;
    }
  }
  return true;
}

We can easily transform this to a generated function - delegates are nice and timer benchmarks show no measureable performance loss. There are no changes to other code necessary.

The generated function is needed to have a closure. This means any variables inside the generator functions will be stored with the generated function and can be accessed and modified when the function is called. Imagine for instance a counter function, where this behaviour is very useful.

But for now we only rewrite the function to be generated.

static isPrimDelegate isPrim = isPrimGenerator();
delegate bool isPrimDelegate(ulong n);

static isPrimDelegate isPrimGenerator() {
  return delegate(ulong n)
  {
    if (0 == (n % 2)) {
      return false;
    }
    double x = Math.Sqrt(n);
    for (ulong i = 3; i <= x; i += 2) {
      if (0 == (n % i)) {
        return false;
      }
    }
    return true;
  };
}

We can easily see that the code could be better. It shouldn't test division for 15 for instance, because everything dividable by 15 is dividable by 3 and 5, too. We could make it faster by only checking for division by prime numbers - and that's just what memoization helps us to do.

We'll save a list with prime numbers along with the function and check only for division by these numbers. This way, we'll have the work of finding primes only once and we'll get a nice speed up.

As you see, adding the list to the function is as simple as declaring a variable in the generator function. We add the primes 2 and 3 to make the later code simpler, adding more primes up-front didn't result in any faster code for me.

Now we check for division with all primes in the list. If we reach the end of the list before we checked all primes in the range, we lazily search for the next prime. We still check for 15 when searching for primes, but this will be done only once and not every time.

static isPrimDelegate isPrim = isPrimGenerator();
delegate bool isPrimDelegate(ulong n);

static isPrimDelegate isPrimGenerator() {
  List prims = new List();
  prims.Add(2);
  prims.Add(3);
  return delegate(ulong n)
  {
    int index = 0;
    ulong m = prims[index];
    double x = Math.Sqrt(n);
    while (m <= x) {
      if (0 == (n % m)) {
        return false;
      }
      if (prims.Count == index) {
        int index2 = 0;
        bool prim = false;
        while (!prim) {
          m += 2;
          prim = true;
          double x2 = Math.Sqrt(m);
          while (prims[index2] <= x2) {
            if (0 == (m % prims[index2])) {
              prim = false;
              break;
            }
            index2++;
          }
        }
        prims.Add(m);
      } else {
        m = prims[index++];
      }
    }
    return true;
  };
}

We end up with faster code by trading memory for CPU time. In most cases it's worth it as the second call to a function will be near-instanteous, if all primes up to the square root of the parameter have already been cached.

This can also be applied to other functions, like costly data base lookups where the result doesn't change, but is needed multiple times. As it is transparent to the caller it's an obvious optimization to make, when profiling finds a function slowing down the code.