template <class T> class Cache
{
public:
Cache()
{
data = NULL;
size = 0;
}
T* data;
int size;
};
Cache<ullong> factorial_cache;
bool factorial_overflow(int n)
{
double sum = 0;
for(double i = 1; i <=n; i++)
sum += log(i); //this is in base e
sum /= log(2.0); //shift into base 2
return (unsigned(sum + 1.0) > sizeof(ullong) * CHAR_BIT); //not sure if this is slight off or not
}
ullong factorial(int n)
{
if (n == 0 || n == 1) return 1;
try
{
if (factorial_overflow(n)) throw "Integer oveflow. Cannot compute factorial of ";
}
catch (const char* msg)
{
cout << msg << n << ".\n";
return 0;
}
if (n >= factorial_cache.size)
{
factorial_cache.data[n] = n * factorial(n - 1);
factorial_cache.size = n;
}
return factorial_cache.data[n];
}