Fastest factorial function

I think that this loop-based version might be the fastest factorial function.

function factorial(n, r = 1) {
  while (n > 0) r *= n--;
  return r;
}

// Default parameters `r = 1`,
//   were introduced in ES6

And here is my reasoning:

• Recursive functions, even with memoization, have the overhead of a function call (basically pushing functions onto the stack) which is less performant than using a loop
• While for loops and while loops have similar performance, a for loop without an initialization-expression and final-expression looks odd; probably better to write for(; n > 0;) as while(n > 0)
• Only two parameters n and r are used, so in theory less parameters means less time spent allocating memory
• Uses a decremented loop which checks if n is zero - I've heard theories that computers are better at checking binary numbers (0 and 1) than they are at checking other integers

Behold, the memoizer, which takes any single-argument function and memoizes it. Turns out to be marginally faster than @xPheRe's solution, including the limit on the size of the cache and associated checking, because I use shortcircuiting and so on.

function memoize(func, max) {
    max = max || 5000;
    return (function() {
        var cache = {};
        var remaining = max;
        function fn(n) {
            return (cache[n] || (remaining-- >0 ? (cache[n]=func(n)) : func(n)));
        }
        return fn;
    }());
}

function fact(n) {
    return n<2 ? 1: n*fact(n-1);
}

// construct memoized version
var memfact = memoize(fact,170);

// xPheRe's solution
var factorial = (function() {
    var cache = {},
        fn = function(n) {
            if (n === 0) {
                return 1;
            } else if (cache[n]) {
                return cache[n];
            }
            return cache[n] = n * fn(n -1);
        };
    return fn;
}());

Approximately 25x faster on my machine in Chrome than the recursive version, and 10% faster than xPheRe's.

I came across this post. Inspired by all contributions here I came up with my own version, which has two features that I haven't seen discussed before: 1) A check to ensure the argument is a non-negative integer 2) Making a unit out of the cache and the function to make it one self contained bit of code. For fun, I tried to make it as compact as possible. Some may find that elegant, others may think it terribly obscure. Anyway, here it is:

var fact;
(fact = function(n){
    if ((n = parseInt(n)) < 0 || isNaN(n)) throw "Must be non-negative number";
    var cache = fact.cache, i = cache.length - 1;
    while (i < n) cache.push(cache[i++] * i);
    return cache[n];
}).cache = [1];

You can either pre fill the cache, or allow it to be filled as the calls go by. But the initial element (for fact(0) must be present or it will break.

Enjoy :)

Here is one solution:

function factorial(number) {
  total = 1
  while (number > 0) {
    total *= number
    number = number - 1
  }
  return total
}

One line answer:

const factorial = (num, accumulator) => num <= 1 ? accumulator || 1 : factorial(--num, num * (accumulator || num + 1));

factorial(5); // 120
factorial(10); // 3628800
factorial(3); // 6
factorial(7); // 5040
// et cetera

Iterative factorial with BigInt for safety

Solution uses BigInt, an ES 2018+/2019 feature.

This is working example uses BigInt, because many answers here all escape the safe boundary of Number (MDN) almost right away. It's not the fastest but it's simple and thus clearer for adapting other optimizations (like a cache of the first 100 numbers).

function factorial(nat:number) {
   let p = BigInt(1)
   for (let i = BigInt(nat); i > 0; i--) p *= i
   return p
}

Example Usage

// 9.332621544394415e+157
Number(factorial(100))

// "933262154439441526816992388562667004907159682643816214685929638952175999
//  932299156089414639761565182862536979208272237582511852109168640000000000
//  00000000000000"
String(factorial(100))

// 9332621544394415268169923885626670049071596826438162146859296389521759999
// 3229915608941463976156518286253697920827223758251185210916864000000000000
// 000000000000n
factorial(100)

• The n at the end of a numeric literal like 1303n indicates it's a BigInt type.
• Remember that you shouldn't mix BigInt with Number unless you explicitly coerce them, and that doing so could cause a loss in accuracy.

This is an iterative solution that uses less stack space and save previously computed values in a self-memoizing way:

Math.factorial = function(n){
    if(this.factorials[n]){ // memoized
        return this.factorials[n];
    }
    var total=1;
    for(var i=n; i>0; i--){
        total*=i;
    }
    this.factorials[n] = total; // save
    return total;
};
Math.factorials={}; // store

Also note that I am adding this to the Math object which is an object literal so there is no prototype. Rather just binding these to the function directly.

I believe the following is the most sustainable and efficient piece of code from the comments above. You can use this in your global application js architecture... and, not worry about writing it in multiple namespaces (since its a task which probably doesn't need much augmenting). I've included 2 method names (based on preference) but both can be used as they're just references.

Math.factorial = Math.fact = function(n) {
    if (isNaN(n)||n<0) return undefined;
    var f = 1; while (n > 1) {
        f *= n--;
    } return f;
};

// if you don't want to update the Math object, use `var factorial = ...`
Math.factorial = (function() {
    var f = function(n) {
        if (n < 1) {return 1;}  // no real error checking, could add type-check
        return (f[n] > 0) ? f[n] : f[n] = n * f(n -1);
    }
    for (i = 0; i < 101; i++) {f(i);} // precalculate some values
    return f;
}());

factorial(6); // 720, initially cached
factorial[6]; // 720, same thing, slightly faster access, 
              // but fails above current cache limit of 100
factorial(100); // 9.33262154439441e+157, called, but pulled from cache
factorial(142); // 2.6953641378881614e+245, called
factorial[141]; // 1.89814375907617e+243, now cached

This does the caching of the first 100 values on the fly, and does not introduce an external variable into scope for the cache, storing the values as properties of the function object itself, which means that if you know factorial(n) has already been calculated, you can simply refer to it as factorial[n], which is slightly more efficient. Running these first 100 values will take sub-millisecond time in modern browsers.

According to Wolfram MathWorld:

The factorial n! is defined for a positive integer n as

Therefore, you can use the following method to obtain the factorial of a number:

const factorial = n => +!n || n * factorial(--n);

factorial(4) // 4! = 4 * 3 * 2 * 1 = 24

Here's an approach that hasn't been provided yet. Using BigInt and memoization, we can get accurate results and skip computation for values that have already been calculated:

// using let and const, block scope can be used instead of IIFE for closure
{
  const lut = [1n, 1n];
  
  // returns factorial as BigInt instead of Number
  function factorial (n) {
    for (let i = lut.length; i <= n; i++) {
      lut.push(BigInt(i) * lut[i - 1]);
    }

    return lut[n];
  }
}

console.log('starting');
// first time will require computation
console.log(factorial(10000).toString());
// second time will return result from cache
console.log(factorial(10000).toString());

div.as-console-wrapper { overflow-x: scroll; }

Well this question has more than enough answers, but just to post a readable, fast and short solution for factorial and reverse factorial.

{
    const cache = [1, 1];
    let i = 2;

    function factorial(n) {
        if (!isFinite(n = parseInt(n)) || n < 0)
            throw new Error('argument for factorial has to be a positive finite integer but was ' + n);

        for (; i <= n; i++)
            cache[i] = cache[i - 1] * i;

        return cache[n];
    }

    function reverseFactorial(n) {
        if (!isFinite(n = parseFloat(n)) || n < 0)
            throw new Error('argument for reverseFactorial has to be a positive finite floatingpoint number but was ' + n);

        let f = 1;

        while (true)
            if (factorial(++f) >= n)
                return f - 1; // lower bound (f! which will fit in the given n, for upper bound just return f)

    }
}

reverseFactorial will return an k which is the biggest k! which fits in the given n.

Both functions profit of the cache build by factorial.

If you want to test it a little:

for (let i = 0; i < 10; i++) {
    let random = Math.random() * 100;
    random = factorial(random) * Math.random() * random;

    const reverse = reverseFactorial(random);
    const resultOfReverse = factorial(reverse);

    function expo(x) {
        return x.toExponential(2);
    }

    console.log('%s fits %d! which is %s (upper bound %d! is %s)', expo(random), reverse, expo(resultOfReverse), reverse + 1, expo(factorial(reverse + 1)));
}

One line solution for Iterative and Recursive options;

const rf = n => 1 === n ? 1 : rf( n - 1 ) * n;

const sf = n => {for (var i = n, c = 1; i > 1; i --) c *= i; return c;}

Iterative:

Math.factorial=n=>{for(var o=n;n>1;)o*=--n;return o};

Recursive:

Math.factorial=n=>n>1?n--*Math.fac(n):1;

Precalculated:

(_=>{let f=[],i=0;for(;i<171;i++)f[i]=(n=>{for(var o=n;n>1;)o*=--n;return o})(i);Math.factorial=n=>{n=Math.round(n);return n<171?f[n]:Infinity}})();

https://code.sololearn.com/Wj4rlA27C9fD. Here I might post more solutions.

Her is my solution using IIFy function and recursion:

console.log((function factorial(n){return (n>1)?n*factorial(n-1):1;})(10))

This is an optimal solution for getting the output of factorial in a single line of code.