A simple performant factorial function

Question

I am new to algorithm and data structure. After a little introduction to the topic, I have decided to implement a function called calculateFactorial, which takes an integer and calculates its factorial. The function should hopefully run efficiently for calculating a very large number's factorial. The way that I thought to do it is by store each calculated factorial in an object. In every itteration, if the factorial for the current calculating number is found in the object, it'll return it, otherwise, it will calculate it. Because factorial can also be calculated like this: 10ドル! = 10*9!,ドル the function will try to find any factorial that is part of the actual wanted factorial and calculates the result without wasting any more itterations, thus improves performance. Here is my implementation:

let memos = {};
function calculateFactorial(num) {
 let result = 1;
 if(num === 0) return 1;
 if(memos[num]) return memos[num];
 for(let i = num; i >= 1; i--) {
 const memoValue = memos[i];
 if(memoValue) {
 memos[num] = result * memoValue;
 return memos[num];
 }
 result *= i;
 }
 memos[num] = result;
 return result;
}

I am not sure if my code is up to the quality of a good programmer. I also know that there isn't much to review, since the code is quite short. However, my code does work and if any helpful comment/suggestions are available, I would greatly appreciate it.

Answer 1

The function should hopefully run efficiently for calculating a very large number's factorial.

Perhaps, but: you can take the factorial of 170, but after that the party is over, calculateFactorial(171) = Infinity. It's not possible to calculate the factorial of a very large number this way, you would just get Infinity.

So realistically the loop will run up to 170 iterations and after that it may as well stop, and you can enforce that (to prevent needlessly looping thousands, millions, or even billions of times or however much num is) without changing the result by adding this at the start of the function:

if (num > 170)
 return Infinity;

Given that limit, I don't think that memos is doing much of the work here, not usually, and if it is (perhaps if you calculate lots of factorials in a loop, in a setting where you cannot incrementally calculate each factorial from the previous one, which you can often do when you need a bunch of factorials) then you could also precalculate all possible values in an array, which would be simpler than some memoization scheme. The cost of precalculating that array is essentially trivial, 170 multiplications done once in the lifetime of an app / pageview / whatever, that's nothing.

None of this is to say that the code is bad, I don't think it's bad, but it makes me question what context it could make sense in.

If you need the factorial of a large number, there are basically two main contexts that I know of:

• A BigInt context in which the factorial needs to be exact, and will be physically large (ie consume a bunch of memory). There are more-efficient-than-naive ways to calculate it if you really must, for example see Borweins "On the Complexity of Calculating Factorials". I'd also be tempted to ask whether you can avoid calculating the factorial: many mathematical expressions that are written with a factorial (written that way for exposition, not computation) can be implemented less-naively without an explicit factorial.
• A context where you can work with a finite-precision approximation of the logarithm of the factorial. For example multiplying a tiny probability (perhaps too tiny to represent in a Number) by a huge factorial (perhaps too large to represent in a Number) turns into adding the logarithm of the probability and the logarithm of the factorial (each of which are more "workable" numbers). You can borrow an implementation of LnGamma from somewhere (or figure out how to compute it but it's not simple).

• Napoleon Bonaparte: Can you provide some links to some of your references?

Answer 2

Performance.

Your code is using a map in a very inefficient way.

Poor use of a Map

You have the line

if(memos[num]) return memos[num];

This requires the calculation of a hash to index into the map menos . If the index is empty, and because you use an object as a map, the JS engine will first search up the prototype tree for a match before returning undefined

This is the worst way to use a map.

• Searching for undefined properties should be avoided in performance code.

If the value is not undefined, ie the factorial has been seen before, you force the JS engine to calculate the hash a second time.

Array rather than Map

Rather than use a Map use an Array and fill it with zeros

• Note: Do not use an empty array, because adding items out of sequence forces the array to become a sparse array which can be just as slow as a map

const memos = new Array(170).fill(0);

Adding a guard for inputs > 170 and you don't need to change your function.

Cache

If caching why not cache the whole set of 171 known values. Seams rather wasteful to fill the memos array as you use the function.

You can take the worst case hit on the first call and then all other calls are a simple array lookup.

var factorial = (num) => {
 const INF = Infinity, facs = [1];
 (()=>{
 var i, fac = 1;
 for (i = 1; i < 171; i++) { facs[i] = fac = fac * i } 
 })();
 return (factorial = num => num > 170 ? INF : facs[num])(num);
}

In the worst case the above is about the same performance as your original functions worst case.

On average it is at least 2 times quicker than your functions average (even when all inputs have been memorized)

• Note: For some reason returning Infinity in the code above really slows the function down (on V8). Returning the constant INF does not impact the performance.