What is the optimal way to implement a small cache in C# to store factorial values?

Question

Hi there,

Here's the code I have:

===========================

public class Foo
{
    //Class field to store factorial values as those are calculated
    private static Dictionary<uint, double> _factorialCache;

    public Foo()
    {
        _factorialCache = new Dictionary<uint, double>();
    }

    public double Factorial(uint inputValue)
    {
        if (inputValue < 2) return 1;

        if (_factorialCache.ContainsKey(inputValue))
            return _factorialCache[inputValue];

        _factorialCache.Add(inputValue, (double)inputValue * Factorial(inputValue - 1));

        return _factorialCache[inputValue];
    }        
}

===========================

Mathematically speaking, this works. One interesting thing is that, if factorial of 5 (for example) is the first value calculated, the cache stores factorial of 2, 3, 4 and 5 (i.e. it stores all the "intermediate" factorials) during this calculation. In my case, there would never be more than one instance of the Foo class alive at the same time, but I decided to declare the dictionary as static in this example to also cover the case in which multiple instances of Foo could exist at the same time.

My questions are:

• Is this the best way to avoid recalculation of factorial for the same values from a technical perspective (e.g. thread safety or similar)?

• Is there any other approach (e.g. something related to lazy evaluation or similar) that would avoid the need of a (static) class-scope variable to store values previously calculated?

All suggestions welcome.

Thanks,

d.

Answer 1

Your code looks fine but it is not thread safe, as the static Dictionary you are using to cache previously calculated values is not thread safe. You need to use proper locking mechanisms when you perform read/write operations on it. Other than that you might find function Memoization an interesting technique.

Answer 2

You are looking for memoization.

There are many different ways to achieve this in c#.

Answer 3

Hi again,

Thanks a lot for your answers. Just a quick note to share my findings while investigating your suggestions (I'm not a professional programmer):

So, I checked memoization (a concept I wasn't aware of) but found out that it's not thread-safe "per se" either (i.e. one has to take care of this separately) and, from what I've seen, it has some other implications when implementing it.

So, I decided to continue with my first approach and see if I could make it thread-safe. Luckily enough, I found this "ConcurrentDictionary" in .NET 4.0:

http://msdn.microsoft.com/en-us/library/dd287191%28VS.100%29.aspx

[There are other concurrent containers in 4.0 too.]

So, I came up with this modified version, which still relies on a (possibly static) class-scoped field for the cache, but which I think has less implementation constraints and implications than the memoized version:

public class Foo
{
    private static ConcurrentDictionary<uint, double> _factorialCache;

    public Foo()
    {            
        if (_factorialCache == null)
            _factorialCache = new ConcurrentDictionary<uint, double>();
    }

    public double Factorial(uint inputValue)
    {
        double returnValue = 0;

        if (inputValue < 2) return 1;

        if (_factorialCache.TryGetValue(inputValue, out returnValue))
            return returnValue;

        returnValue = inputValue * Factorial(inputValue - 1);

        if (!_factorialCache.TryAdd(inputValue, returnValue))
            throw new Exception("Failed to add factorial value to the factorial cache.");

        return returnValue;
    }
}

I'm pretty happy with this version now, but any suggestions for improvement are most welcome.

Thanks a lot,

d.

PS - How do I mark the question as "resolved"?