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

Question

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.