What is the fastest factorial function in JavaScript? [closed]

Question

Looking for a really fast implementation of the factorial function in JavaScript. Any suggestions?

Epilimnion

What's the possible range of arguments? – Underweight

Have you considered pre-calculating factorials and storing the values in a lookup table? – Mohamedmohammad

What's the application of such a function? In other words, what are you going to use it for? – Propose

@Nikita Rybak, only 1 agrument (n). If (n > 170) e = Infinity – Epilimnion

@ Pointy, yet another math calculator service. – Epilimnion

@Epilimnion I was asking for possible values of this argument (how large can it be). Others already noted that caching should work if it's not too big. And if it is, then it's not clear what you need such huge number for (factorial grows very fast). – Underweight

@Epilimnion Nikita is right, 1m! has over 5.5 million digits, and even Mathematica crunched those numbers a min or few. – Spell

You should use an gamma function, not a naive implementation that uses loops or recursion. You should memoize, too. – Dialectic

Answer 1

You can search for (1...100)! on Wolfram|Alpha to pre-calculate the factorial sequence.

The first 100 numbers are:

1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000, 1124000727777607680000, 25852016738884976640000, 620448401733239439360000, 15511210043330985984000000, 403291461126605635584000000, 10888869450418352160768000000, 304888344611713860501504000000, 8841761993739701954543616000000, 265252859812191058636308480000000, 8222838654177922817725562880000000, 263130836933693530167218012160000000, 8683317618811886495518194401280000000, 295232799039604140847618609643520000000, 10333147966386144929666651337523200000000, 371993326789901217467999448150835200000000, 13763753091226345046315979581580902400000000, 523022617466601111760007224100074291200000000, 20397882081197443358640281739902897356800000000, 815915283247897734345611269596115894272000000000, 33452526613163807108170062053440751665152000000000, 1405006117752879898543142606244511569936384000000000, 60415263063373835637355132068513997507264512000000000, 2658271574788448768043625811014615890319638528000000000, 119622220865480194561963161495657715064383733760000000000, 5502622159812088949850305428800254892961651752960000000000, 258623241511168180642964355153611979969197632389120000000000, 12413915592536072670862289047373375038521486354677760000000000, 608281864034267560872252163321295376887552831379210240000000000, 30414093201713378043612608166064768844377641568960512000000000000, 1551118753287382280224243016469303211063259720016986112000000000000, 80658175170943878571660636856403766975289505440883277824000000000000, 4274883284060025564298013753389399649690343788366813724672000000000000, 230843697339241380472092742683027581083278564571807941132288000000000000, 12696403353658275925965100847566516959580321051449436762275840000000000000, 710998587804863451854045647463724949736497978881168458687447040000000000000, 40526919504877216755680601905432322134980384796226602145184481280000000000000, 2350561331282878571829474910515074683828862318181142924420699914240000000000000, 138683118545689835737939019720389406345902876772687432540821294940160000000000000, 8320987112741390144276341183223364380754172606361245952449277696409600000000000000, 507580213877224798800856812176625227226004528988036003099405939480985600000000000000, 31469973260387937525653122354950764088012280797258232192163168247821107200000000000000, 1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000, 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000, 8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000, 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000, 36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000, 2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000, 171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000, 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000, 850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000, 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000, 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000, 330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000, 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000, 1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000, 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000, 11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000, 894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000, 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000, 5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000, 475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000, 39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000, 3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000, 281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000, 24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000, 2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000, 185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000, 16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000, 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000, 135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000, 12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000, 1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000, 108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000, 10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000, 991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000, 96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000, 9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000, 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

If you still want to calculate the values yourself, you can use memoization:

var f = [];
function factorial (n) {
  if (n == 0 || n == 1)
    return 1;
  if (f[n] > 0)
    return f[n];
  return f[n] = factorial(n-1) * n;
}

Edit: 21.08.2014

Solution 2

I thought it would be useful to add a working example of lazy iterative factorial function that uses big numbers to get exact result with memoization and cache as comparison

var f = [new BigNumber("1"), new BigNumber("1")];
var i = 2;
function factorial(n)
{
  if (typeof f[n] != 'undefined')
    return f[n];
  var result = f[i-1];
  for (; i <= n; i++)
      f[i] = result = result.multiply(i.toString());
  return result;
}
var cache = 100;
// Due to memoization, following line will cache first 100 elements.
factorial(cache);

I assume you would use some kind of closure to limit variable name visibility.

Ref: BigNumber Sandbox: JsFiddle

Spell

Values past 6402373705728000 will be truncated so if you're going to use this approach make sure to convert to exponential before using the aforementioned table. – Betwixt

@DavidScottKirby Javascript automatically converts these numbers to their closest 64-bit float representation. The real benefit of not having the full precision numbers in the code is reduced file size. – Rattler

Your second solution could be simplified to function factorial (n) { for (var i = f.length; i <= n; i++) f.push(f[i - 1].multiply(i.toString())); return f[n]; } Also see my answer which uses the more recent builtin BigInt rather than a third-party library. – Hebraic

so, the 100th number has 158 chars long – Araby

Answer 2

You should use a loop.

Here are two versions benchmarked by calculating the factorial of 100 for 10.000 times.

Recursive

function rFact(num)
{
    if (num === 0)
      { return 1; }
    else
      { return num * rFact( num - 1 ); }
}

Iterative

function sFact(num)
{
    var rval=1;
    for (var i = 2; i <= num; i++)
        rval = rval * i;
    return rval;
}

Live at : http://jsfiddle.net/xMpTv/

My results show:
- Recursive ~ 150 milliseconds
- Iterative ~ 5 milliseconds..

Corelative

+1 Great answer! Although memoization may be reasonable when there are multiple calls to calculate factorials for bigger numbers. – Especial

@Tadeck, thanks. Indeed memoization is very useful in this case and that is why Margus answer is picked as the correct one :) – Corelative

A 1-line version of recursive: function factorial(num) { return (num == 1) ? num : num * arguments.callee(num-1); } – Pau

jsperf.com/factorial-test-1111 – Patman

@HWTech, you are never calling the methods. Your test compares the speed of defining the two methods.. not the time they take to execute.. This is a better test (trying only the factorial of 15) – Corelative

Instead of rval = rval * i; you could write rval *= i; – Pasteup

The recursive formula has an unnecessary else statement. – Pictor

The OP question is "Looking for a really fast implementation" and then you show that the recursive method, presented first, is substantially slower than the iterative method. I suggest that your answer would be better if it was edited to put the fastest method first, with a note about the recursive method being useful only as a teaching example for recursion. – Stopped

alternative version of the same thing: const factorial = number => { for (let i = n = 1; i <= number; i++) { n = n * i } return n; } – Malcommalcontent

Answer 3

I still think Margus's answer is the best one. However if you want to calculate the factorials of numbers within the range 0 to 1 (ie the gamma function) as well, then you cannot use that approach because the lookup table will have to contain infinite values.

However, you can approximate the values of the factorials, and it's pretty fast, faster than recursively calling itself or looping it at least (especially when values start to get bigger).

A good approximation method is Lanczos's one

Here is an implementation in JavaScript (ported from a calculator I wrote months ago):

function factorial(op) {
 // Lanczos Approximation of the Gamma Function
 // As described in Numerical Recipes in C (2nd ed. Cambridge University Press, 1992)
 var z = op + 1;
 var p = [1.000000000190015, 76.18009172947146, -86.50532032941677, 24.01409824083091, -1.231739572450155, 1.208650973866179E-3, -5.395239384953E-6];

 var d1 = Math.sqrt(2 * Math.PI) / z;
 var d2 = p[0];

 for (var i = 1; i <= 6; ++i)
  d2 += p[i] / (z + i);

 var d3 = Math.pow((z + 5.5), (z + 0.5));
 var d4 = Math.exp(-(z + 5.5));

 d = d1 * d2 * d3 * d4;

 return d;
}

You can now do cool stuff like factorial(0.41), etc however accuracy might be a little off, after all, it is an approximation of the result.

Mohamedmohammad

quite interesting approach, thanks. – Epilimnion

I recommend changing the part below the for-loop to var d3d4 = Math.exp((z + 0.5) * Math.log(z + 5.5) - z - 5.5); return d1 * d2 * d3d4;. This allows you to compute factorials up to 169! instead of currently only 140!. This is pretty close to the maximum representable factorial using the Number datatype, which is 170!. – Rattler

Answer 4

Here is my solution:

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

It's the simplest way (less characters / lines) I've found, only a function with one code line.

---

Edit:
If you really want to save some chars you can go with an Arrow Function (21 bytes):

f=n=>(n<2)?1:f(n-1)*n

Healey

Save even more with f=n=>n?f(n-1)*n:1... – Rattler

unfortunately even if it's nice to see and short in form, this is the slowest way to do it. – Sherrard

Answer 5

Just One line with ES6

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

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


function print(value) {
  document.querySelector('.result').innerHTML = value;
}

.result {
  margin-left: 10px;
}

<input onkeyup="print(factorial(this.value))" type="number"/>

<span class="result">......</span>

Chaker

factorial = n => n <= 1 ? 1 : factorial(n - 1) * n – Copt

Answer 6

Lookup table is the obvious way to go, if you're working with natural numbers. To calculate any factorial in real-time, you can speed it with a cache, saving the numbers you've calculated before. Something like:

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;
})();

You can precalculate some values in order to speed it even more.

Cotillion

I've created an auto-memoizer for any given function based on this answer (also slightly faster :)), also including a limit on the cache size. https://mcmap.net/q/186635/-what-is-the-fastest-factorial-function-in-javascript-closed – Moina

Answer 7

short and easy recursive function (you could do it with a loop, too, but I don't think that would make any difference in performance):

function factorial (n){
  if (n==0 || n==1){
    return 1;
  }
  return factorial(n-1)*n;
} 

for a very large n, you could use the stirlings approximation - but that will only give you an approximate value.

EDIT: a comment on why I'm getting a downvote for this would have been nice...

EDIT2: this would be the soulution using a loop (which would be the better choice):

function factorial (n){
  j = 1;
  for(i=1;i<=n;i++){
    j = j*i;
  }
  return j;
}

I think the best solution would be to use the cached values, as Margus mentioned and use the stirlings approximation for larger values (assumed you have to be realy fast and don't have to be that exact on such big numbers).

Walloon

In languages without tail call optimisation (i.e. most widely-used languages) it is better to use a non-recursive implementation where it is easy to do so, though there are ways around it: paulbarry.com/articles/2009/08/30/tail-call-optimization – Bieber

that's indeed definitely not that fastest, as it wouldn't even use TCO, if it were implemented. But it is simple and I wouldn't downvote it. It's not the fastest for sure. – Baram

Tail call optimization isn't even possible for this function, as the recursive call is not in tail position. – Scat

@Josh, (not the downvoter) fastest is the loop by quite a margin .. – Corelative

in the first example, you don't need to put a special condition for n=1, because the return of factorial(n-1)*n will always be 1 when n = 1 – Melan

Answer 8

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

Dubbin

Answer 9

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.

Moina

Answer 10

It is very simple using ES6

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

See an example here

Minstrelsy

Answer 11

Exploiting the fact that Number.MAX_VALUE < 171!, we can simply use a complete lookup table consisting of just 171 compact array elements taking up less than 1.4 kilobytes of memory.

A fast lookup function with runtime complexity O(1) and minimal array access overhead would then look as follows:

// Lookup table for n! for 0 <= n <= 170:
const factorials = [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368e3,20922789888e3,355687428096e3,6402373705728e3,121645100408832e3,243290200817664e4,5109094217170944e4,1.1240007277776077e21,2.585201673888498e22,6.204484017332394e23,1.5511210043330986e25,4.0329146112660565e26,1.0888869450418352e28,3.0488834461171387e29,8.841761993739702e30,2.6525285981219107e32,8.222838654177922e33,2.631308369336935e35,8.683317618811886e36,2.9523279903960416e38,1.0333147966386145e40,3.7199332678990125e41,1.3763753091226346e43,5.230226174666011e44,2.0397882081197444e46,8.159152832478977e47,3.345252661316381e49,1.40500611775288e51,6.041526306337383e52,2.658271574788449e54,1.1962222086548019e56,5.502622159812089e57,2.5862324151116818e59,1.2413915592536073e61,6.082818640342675e62,3.0414093201713376e64,1.5511187532873822e66,8.065817517094388e67,4.2748832840600255e69,2.308436973392414e71,1.2696403353658276e73,7.109985878048635e74,4.0526919504877214e76,2.3505613312828785e78,1.3868311854568984e80,8.32098711274139e81,5.075802138772248e83,3.146997326038794e85,1.98260831540444e87,1.2688693218588417e89,8.247650592082472e90,5.443449390774431e92,3.647111091818868e94,2.4800355424368305e96,1.711224524281413e98,1.1978571669969892e100,8.504785885678623e101,6.1234458376886085e103,4.4701154615126844e105,3.307885441519386e107,2.48091408113954e109,1.8854947016660504e111,1.4518309202828587e113,1.1324281178206297e115,8.946182130782976e116,7.156945704626381e118,5.797126020747368e120,4.753643337012842e122,3.945523969720659e124,3.314240134565353e126,2.81710411438055e128,2.4227095383672734e130,2.107757298379528e132,1.8548264225739844e134,1.650795516090846e136,1.4857159644817615e138,1.352001527678403e140,1.2438414054641308e142,1.1567725070816416e144,1.087366156656743e146,1.032997848823906e148,9.916779348709496e149,9.619275968248212e151,9.426890448883248e153,9.332621544394415e155,9.332621544394415e157,9.42594775983836e159,9.614466715035127e161,9.90290071648618e163,1.0299016745145628e166,1.081396758240291e168,1.1462805637347084e170,1.226520203196138e172,1.324641819451829e174,1.4438595832024937e176,1.588245541522743e178,1.7629525510902446e180,1.974506857221074e182,2.2311927486598138e184,2.5435597334721877e186,2.925093693493016e188,3.393108684451898e190,3.969937160808721e192,4.684525849754291e194,5.574585761207606e196,6.689502913449127e198,8.094298525273444e200,9.875044200833601e202,1.214630436702533e205,1.506141741511141e207,1.882677176888926e209,2.372173242880047e211,3.0126600184576594e213,3.856204823625804e215,4.974504222477287e217,6.466855489220474e219,8.47158069087882e221,1.1182486511960043e224,1.4872707060906857e226,1.9929427461615188e228,2.6904727073180504e230,3.659042881952549e232,5.012888748274992e234,6.917786472619489e236,9.615723196941089e238,1.3462012475717526e241,1.898143759076171e243,2.695364137888163e245,3.854370717180073e247,5.5502938327393044e249,8.047926057471992e251,1.1749972043909107e254,1.727245890454639e256,2.5563239178728654e258,3.80892263763057e260,5.713383956445855e262,8.62720977423324e264,1.3113358856834524e267,2.0063439050956823e269,3.0897696138473508e271,4.789142901463394e273,7.471062926282894e275,1.1729568794264145e278,1.853271869493735e280,2.9467022724950384e282,4.7147236359920616e284,7.590705053947219e286,1.2296942187394494e289,2.0044015765453026e291,3.287218585534296e293,5.423910666131589e295,9.003691705778438e297,1.503616514864999e300,2.5260757449731984e302,4.269068009004705e304,7.257415615307999e306];

// Lookup function:
function factorial(n) {
  return factorials[n] || (n > 170 ? Infinity : NaN);
}

// Test cases:
console.log(factorial(NaN));       // NaN
console.log(factorial(-Infinity)); // NaN
console.log(factorial(-1));        // NaN
console.log(factorial(0));         // 1
console.log(factorial(170));       // 7.257415615307999e+306 < Number.MAX_VALUE
console.log(factorial(171));       // Infinity > Number.MAX_VALUE
console.log(factorial(Infinity));  // Infinity

This is as precise and as fast as it gets using the Number datatype. Computing the lookup table in Javascript - as some other answers suggest - will reduce precision when n! > Number.MAX_SAFE_INTEGER.

Compressing the runtime table via gzip reduces its size on disk from about 3.6 to 1.8 kilobytes.

Rattler

Answer 12

Using ES6 you can achieve it both fast and short:

const factorial = n => [...Array(n + 1).keys()].slice(1).reduce((acc, cur) => acc * cur, 1)

Wist

Answer 13

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 :)

Failure

Answer 14

Here is one solution:

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

Gian

Answer 15

The code to calculate factorial depends on your requirements.

1. Are you concerned about overflow?
2. What range of inputs will you have?
3. Is it more important for you to minimize size or time?
4. What are you going to do with the factorial?

Regarding points 1 and 4, it is often more useful to have a function to evaluate the log of the factorial directly rather than to have a function to evaluate factorial itself.

Here's a blog post that discusses these issues. Here is some C# code for computing log factorial that would be trivial to port to JavaScript. But it may not be best for your needs depending on your answers to the questions above.

Twigg

Numbered list probably should be in comments. All that's left is two links, and link-only answers are discouraged. – Casandra

Answer 16

This is a compact loop-based version

function factorial( _n )
{
    var _p = 1 ;
    while( _n > 0 ) { _p *= _n-- ; }
    return _p ;
}

Or you might override Math object (recursive version):

Math.factorial = function( _x )  { return _x <= 1 ? 1 : _x * Math.factorial( --_x ) ; }

Or join both approaches ...

Sewing

I fixed it inside the above code. Thank you! – Sewing

Answer 17

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

Jewish

Answer 18

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(n) {
   let p = BigInt(1)
   for (let i = BigInt(n); 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.

Lyons

Answer 19

Just for completeness, here is a recursive version that would allow tail call optimization. I'm not sure if tail call optimizations are performed in JavaScript though..

function rFact(n, acc)
{
    if (n == 0 || n == 1) return acc; 
    else return rFact(n-1, acc*n); 
}

To call it:

rFact(x, 1);

Othello

ES6 supports TCO, but afaik this feature isn't active per default in any major engine yet – Rattler

Answer 20

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.

Leisaleiser

This doesn't really take full advantage of the memoization for subproblems - for example, Math.factorial(100); Math.factorial(500); will calculate the 1..100 multiplication twice. – Casandra

Answer 21

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;
};

Cacology

By starting your multiplication with n * (n-1) * (n-2) * ... * 1 instead of the other way round, you loose up to 4 digits in precision for n >> 20. – Rattler

Answer 22

// 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.

Isometric

I figured out that after 21! the numbers are not reliable. – Anode

@Anode That's because 21! > Number.MAX_SAFE_INTEGER, thus cannot safely be represented as a 64-bit float. – Rattler

Answer 23

Here is an implementation which calculates both positive and negative factorials. It's fast and simple.

var factorial = function(n) {
  return n > 1
    ? n * factorial(n - 1)
    : n < 0
        ? n * factorial(n + 1)
        : 1;
}

Playtime

Usually, n! for n < 0 is not defined. See mathoverflow.net/questions/10124/the-factorial-of-1-2-3 – Rattler

Answer 24

Here's one I made myself, don't use numbers over 170 or under 2.

function factorial(x){
 if((!(isNaN(Number(x)))) && (Number(x)<=170) && (Number(x)>=2)){
  x=Number(x);for(i=x-(1);i>=1;--i){
   x*=i;
  }
 }return x;
}

Gondar

By starting your multiplication with n * (n-1) * (n-2) * ... * 1 instead of the other way round, you loose up to 4 digits in precision for n >> 20. Also, creates an unwanted global variable i and performs way too many Number conversions and gives incorrect results for 0! (as you stated, but why?). – Rattler

Answer 25

Here is my code

function factorial(num){
    var result = num;
    for(i=num;i>=2;i--){
        result = result * (i-1);
    }
    return result;
}

Motorbus

If (n > 170) e = Infinity . And your code will generate a huge number. wont there be any overflows ? – Lithiasis

Incorrect result for factorial(0). Also, by starting your multiplication with n * (n-1) * (n-2) * ... * 1 instead of the other way round, you loose up to 4 digits in precision for n >> 20. @prime: 170! > Number.MAX_VALUE and is best represented with Infinity. – Rattler

Answer 26

Cached loop should be fastest (at least when called multiple times)

var factorial = (function() {
  var x =[];

  return function (num) {
    if (x[num] >0) return x[num];
    var rval=1;
    for (var i = 2; i <= num; i++) {
        rval = rval * i;
        x[i] = rval;
    }
    return rval;
  }
})();

Prothesis

Answer 27

Here is one using newer javascript functions fill, map, reduce and constructor (and fat arrow syntax):

Math.factorial = n => n === 0 ? 1 : Array(n).fill(null).map((e,i)=>i+1).reduce((p,c)=>p*c)

Edit: updated to handle n === 0

Capture

That is one seriously ugly unreadable line of code. – Main

That's a neat idea. Rather than traversing the length twice, why not convert all the logic to the reduce function and use it's initial value to handle edge case n === 0? Math.factorial = n => Array.from({ length: n }).reduce((product, _, i) => product * (i + 1), 1) – Merchantman

Answer 28

function isNumeric(n) {
    return !isNaN(parseFloat(n)) && isFinite(n)
}

Provided by http://javascript.info/tutorial/number-math as a simple way to evaluate if an object is a proper integer for calculation.

var factorials=[[1,2,6],3];

A simple set of Memoized factorials that require redundant calculations, may be processed with "multiply by 1", or are one digit that is a simple equation not worth processing live.

var factorial = (function(memo,n) {
    this.memomize = (function(n) {
        var ni=n-1;
        if(factorials[1]<n) {
            factorials[0][ni]=0;
            for(var factorial_index=factorials[1]-1;factorials[1]<n;factorial_index++) {
                factorials[0][factorials[1]]=factorials[0][factorial_index]*(factorials[1]+1);
                factorials[1]++;
            }
        }
    });
    this.factorialize = (function(n) {
        return (n<3)?n:(factorialize(n-1)*n);
    });
    if(isNumeric(n)) {
        if(memo===true) {
            this.memomize(n);
            return factorials[0][n-1];
        }
        return this.factorialize(n);
    }
    return factorials;
});

After reviewing the input from other members (excluding the Log advice, although I may implement that later) I went ahead and threw together a script that is fairly simple. I started with a simple uneducated JavaScript OOP example and built a little class to handle factorials. I then implemented my version of the Memoization that was suggested above. I also implemented the shorthand Factorialization however I made a small error adjustment; I changed the "n<2" to "n<3". "n<2" would still process n=2 which would be a waste, because you would iterate for a 2*1=2; this is a waste in my opinion. I altered it to "n<3"; because if n is 1 or 2 it will simply return n, if it is 3 or more it will evaluate normally. Of course as rules apply, I placed my functions in descending order of assumed execution. I added in the bool(true|false) option to allow quick altering between memo'ed and normal execution (You just never know when you want to swap around on your page without needing to change the "style") As I said before the memoized factorials variable is set with the 3 starting positions, taking 4 characters, and minimizing wasteful calculations. Everything past the third iteration you are handling double digit math plus. I figure if you where a stickler enough about it you would run on a factorial table (as implemented).

What have I planned after this? local&|session storage to allow for a case by case cache of needed iterations, essentially handling the "table" issue spoken above. This would also massively save database and server side space. However, if you go with localStorage you would essentially be sucking up space on your users computer simply to store a list of numbers and make their screen LOOK faster, however over a long period of time with an immense need this would be slow. I am thinking sessionStorage (clearing after Tab leaves) would be a much better route. Possibly combine this with a self balancing server/local dependent cache? User A needs X iterations. User B need Y iterations. X+Y/2=Amount needed locally cached. Then just detect and fiddle with load-time and execute-time benchmarks live for every user until it adjusts itself to optimization for the site itself. Thanks!

Edit 3:

var f=[1,2,6];
var fc=3;
var factorial = (function(memo) {
    this.memomize = (function(n) {
        var ni=n-1;
        if(fc<n) {
            for(var fi=fc-1;fc<n;fi++) {
                f[fc]=f[fi]*(fc+1);
                fc++;
            }
        }
        return f[ni];
    });

    this.factorialize = (function(n) {
        return (n<3)?n:(factorialize(n-1)*n);
    });

    this.fractal = (function (functio) {
        return function(n) {
            if(isNumeric(n)) {
                return functio(n);
            }
            return NaN;
        }
    });

    if(memo===true) {
        return this.fractal(memomize);
    }
    return this.fractal(factorialize);
});

This edit implements another Stack suggestion and allows me to call the function as factorial(true)(5), which was one of my goals setting out. :3 I also removed some needless assigning, and shorthanded some non-public variable names.

Edenedens

Returns undefined for 0!. ES6 allows to replace isNumeric with Number.isInteger. Lines like factorials[0][factorials[1]]=factorials[0][factorial_index]*(factorials[1]+1); are totally unreadable. – Rattler

Answer 29

Using ES6 features, can write code on ONE line & without recursion :

var factorial=(n)=>Array.from({length: n},(v, k) => k+1).reduce((a, b) => a*b, 1)

var factorial=(n)=>Array.from(
       {length: n}, (v, k) => k+1)   /*Generate Array [1, 2, .., n -1, n]*/
     .reduce(
       (a, b) => a*b, 1 /*Multiply all aarray items; one with the next*/
     ); 
     

var n = prompt('Give us "n", we will calculate "n!" ?');

if (n) {
  alert(`${n}! = ${factorial(n)}`)
}

Chaker

I doubt this code would be faster than a standard iterative solution but, it has some other issues as well. For one, you are allocating an entire array just so you can calculate n!. While maybe this function is short, it wastes memory. Allocation of that a lot of elements could be expensive in terms of time. Another thing is that this way of writing a function is, in my opinion, not that readable, which should usually be considered. That's my opinion anyway, I'll happy to hear your input. – Laskowski

Answer 30

function computeFactorialOfN(n) {
  var output=1;
  for(i=1; i<=n; i++){
    output*=i;
  } return output;
}
computeFactorialOfN(5);

Endosmosis

Welcome to StackOverflow and thanks for your help. You might want to make your answer even better by adding some explanation. – Sponger

Answer 31

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

Rabbin

Answer 32

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; }

Hebraic

Answer 33

This will return the factorial of n

function f(n) {
    var e = n;
    if (e == 1 | e == 0) return 1;
    while (n--) {
        if (n < 1)
            break;
        e *= n;
    }
    return e
}

Preamplifier

By starting your multiplication with n * (n-1) * (n-2) * ... * 1 instead of the other way round, you loose up to 4 digits in precision for n >> 20. Also, you probably do want to write || instead of |. – Rattler

Answer 34

var factorial = (function() {
    var cache = [1];
    return function(value) {
        for (var index = cache.length; index <= value; index++) {
            cache[index] = index * cache[index - 1]
        }
        return cache[value];
    }
})();

I find this useful in same cases:

function factorialDivision(n, d) {
    var value = 1;
    for (d++ < n) {
        value *= d;
    }
    return value;
}

Disject

Answer 35

Since a factorial is simply degenerative multiplication from the number given down to 1, it would indeed be easier to just loop through the multiplication:

Math.factorial = function(n) {

  if (n === 0||n === 1) {

    return 1;

  } else {

    for(var i = n; i > 0; --i) { //always make sure to decrement the value BEFORE it's tacked onto the original as a product
      n *= i;
    }

    return n;

  }

}

Operculum

Your function does not compute n! but n * n!. Using prefix --i versus postfix i-- makes no difference regarding the value of i in the loop body or the number of iterations. – Rattler

Answer 36

 used closure  for this with the helper (getFact) , I think this approach is neat hope this helps  


    factorial of n : using closures*/

    function getFact(num) {

        if (num > 1)
            return num * getFact(num - 1);
        else
            return 1;

    }


    function makeFact(fn) {
        return function(num) {
            return fn(num);
        }


    }

   makeFact(getFact)(5) //120

Calcite

Answer 37

var factorial = function(numToBeFactored)
    {
        if (numToBeFactored == 0)
                return 1;
            var numLength = 0;
            var numBeingFactored = 1;
        /*goes through the loop numToBeFactored times and each time multiplies numBeingFactored by one less than the last loop*/
            for (numLength = 0; numLength < numToBeFactored; numLength++)
            {
                numBeingFactored *= (numToBeFactored - numLength);
            }
            return numBeingFactored;
    };

Geraldo

By starting your multiplication with n * (n-1) * (n-2) * ... * 1 instead of the other way round, you loose up to 4 digits in precision for n >> 20. – Rattler

Answer 38

It would be probably very simple at first and maybe from this short code you would set it more better depend of your needs :

<body>

    <button  onclick="fact()">Open the Prompt</button>
    <h2 id="output"></h2>

    <script>

    function fact(){ 
        var enter=prompt("Enter You Factorial Number Bellow :","");
        var Num_enter=Number(enter);

        for (var i=1,FactNumber=1;i<=Num_enter;i++){

        FactNumber=FactNumber*i;
        }

        if(Num_enter){ 
           document.getElementById("output").textContent="the factorial of "+ Num_enter + " is: "+Num_enter+"!= "+ FactNumber;
        }


     }

   </script>


 </body>

Cecilia

Answer 39

    function factorial(num){    
        var num=Number(num);
        if (num < 0){
            return "this is not a positive number";
        }
        else{

        for (i=2 , f=1 ; i<=num;i++){

        f=f*i;

        }

    return f;
    }
    }
    // the function assumes that a number < 0 is null and factorial of any word is considerate as factorial of 0 //

    console.log("-5! ="+factorial(-1));
    console.log("something ="+factorial("something"));
    console.log("15! ="+factorial(15));
    console.log("20! ="+factorial(20));

Cecilia

Answer 40

var factorial = function() {
    var memo = [1];
    var facto = function (n) {
        var result = memo[n];
    if (typeof result !== 'number'){
        result = facto(n-1)*n;
    }
        return result;
    };
    return facto;
}();

To compute the factorial of a number using memoization, call with factorial(n).

Gardener

Welcome to Stack Overflow! Please consider editing your post to add more explanation about what your code does and why it will solve the problem. An answer that mostly just contains code (even if it's working) usually wont help the OP to understand their problem. – Smoothspoken

Answer 41

While all the above ones are good, but they all seem too long for me, so I made my own.

function factorial(n) {              //"n" is the number used in the factorial

    var ans = 1,                     //define the base variables
        neg = false,
        n = Math.round(n);

    if (n<0 || !n) neg = true;       //check if the number is negative or if the number doesn't exist

    for (var i=1;i<=n;i++) ans *= i; //the actual repeating code, won't run if the number is less than or equal to 0

    return neg ? NaN : ans;          //return the answer if the original was positive

}

The way the for loop works will automatically not do anything to any number below 1. So basically "if (The Number) is less than or equal to 0, then return 1.

The lines if (n<0 || !n) neg = true; and return neg ? NaN : ans; work together to say "If the number is a negative, then return NaN(Not a Number)". These also check to see if the number even exists, and will return the NaN(Not a Number) if the number doesn't exist.

Note

At least on Chrome v50.0.2661.86 (64-bit), it has a max of 170. So if you run this function on a number higher than 170 (171 for example), it will return infinity.

Divide

Returns NaN for factorial(0). Also, since 171! > Number.MAX_VALUE, it cannot be represented by JavaScript's Number datatype, no matter which platform you use. – Rattler

Answer 42

This is the simplest way I know of to make a factorial function

function factorial(num) {

    var result = 1;
    for(var i = 2; i<= num; i++) {
        result *= i;
    }
    return result;
}

Entrechat

Answer 43

You can use

function factorial(n) {
    return [...Array(n+1).keys()].slice(1).reduce( (a,b) => a * b, 1 );
}

Stifle

Answer 44

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)));
}

Marvel

Answer 45

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;}

Cuttlebone

Answer 46

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.

Passageway

Answer 47

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.

Divaricate

Answer 48

    var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    numbers.reduce(function factorial(previous, current) {
      return previous * current;
      });

   console.log(numbers);

Rutledge

OP asks for a fast factorial function, not a hardcoded computation of 10!. Just generalize your code to n! and wrap it in a function and you are good to go. – Rattler

Answer 49

Old question but i find this approach quite readable and straightforward

function factorialize(num) {
  var arr = [];
  var result;
  if ( num === 0 || num === 1 ) {
    return 1;
  } else {
    for (var i = num; i > 0; i--) {
      arr.push(i);
      result = arr.reduce(function(previousVal, nextVal){
                return previousVal * nextVal;
              });
    }
    return result;
  }
}

Mario

The array arr is superfluous and causes an extremely bad runtime complexity of O(n²). Also, by starting your multiplication with num * (num-1) * (num-2) * ... * 1 instead of the other way round, you loose up to 4 digits in precision for num >> 20. – Rattler

Hey, thanks for the comment. Could you please share an example with the 4 digits precision issue? – Mario

Your factorialize(170) returns 7.257415615308004e+306 while e.g. f = n => n ? n * f(n-1) : 1; returns 7.257415615307994e+306. The real value is 7.2574156153079989...e306. JavaScript's Number datatype is backed by an IEEE double which rounds big numbers up to their closest possible representation in memory. Thus, starting your multiplication chain with the biggest numbers having big rounding errors multiplies this error n times. – Rattler