Memoizing functions in c++

I was thinking about memoization, and how I'd not yet used it. I thought this was a bad thing simply because not using it might lead to me forget about it. So I'm putting together this blog post to help me solidify the concept.

A long while a go I realised a simple fact about square numbers: x² = (x-1)² + (x-1) + x, x ∈ N. I.e. for any positive integer its square is the square of the previous integer plus the previous integer plus itself. (e.g. 17*17 = 16*16 + 16 + 17)

This is something that is unlikely to be interesting or useful, except that I can use it to demonstrate memoization.

From the above formula you can write a recursive function:

int square(int n)
{
    if(1 == n)
    {
        return 1;
    }
    return (square(n - 1) + (n - 1) + n);
}

As you can see this is a very long winded way to get the square of a number, and not a function that would ever be used in reality, but it is a good candidate for memoization.

Memoization in this instance is very easy. Simply add in a static map<int, int> and update it for each number you haven't calculated yet:

int square(int n)
{
 static std::map<int, int> results;
 if(1==n)
 {
  return 1;
 }
 if(0 == results[n])
 {
  results[n] = square(n-1) + n-1 + n;
 }
 return results[n];
}

It might be that you'll want to make the results variable on the heap with some sort of smart pointer, so that it automatically deletes itself, but other than that this second version should give a performance increase over the original.

I carried out some simple timing tests with std:clock(). The programme had to calculate the squares from 1 to 32767 using the memoized and non memoized functions, in a loop:

toggle test code

#include <map>
#include <ostream>
#include <ctime>

int calcSqr(int);
int calcSqrSlow(int);

int main()
{
 clock_t start1 = std::clock();
 for(int i = 1; i <= 32767; ++i)
 {
  calcSqrSlow(i);
 }
 clock_t start2 = std::clock();
 std::cout << "Ticks taken (slow): " << start2 - start1 << std::endl;
 clock_t start3 = std::clock();
 for(int i = 1; i <= 32767; ++i)
 {
  calcSqr(i);
 }
 clock_t start4 = std::clock();
 std::cout << "Ticks taken (memo): " << start4 - start3 << std::endl;
 return 0;
}

int calcSqrSlow(int n)
{
 if(1 == n)
 {
  return 1;
 }
 
 return (calcSqrSlow(n - 1) + (n - 1) + n);
}

int calcSqr(int n)
{
 static std::map<int, int> results;
 
 if(1==n)
 {
  return 1;
 }
 
 if(0 == results[n])
 {
  results[n] = calcSqr(n-1) + n-1 + n;
 }
 
 return results[n];
}

Ticks taken for the normal function: 3120
Ticks taken for the memoized function: 78

Obviously this test was biased towards the memoized function, but I really did it to show the potential benefits of memoizing a function where the results can be reused.