JavaScript 中最快的阶乘函数是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3959211/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the fastest factorial function in JavaScript?
提问by Ken
Looking for a really fast implementation of factorialfunction in JavaScript. Any suggests?
在 JavaScript 中寻找阶乘函数的真正快速实现。有什么建议吗？
回答by Margus
You can search for (1...100)! on WolframAlphato pre-calculate the factorial sequence.
您可以搜索 (1...100)！在 WolframAlpha上预先计算阶乘序列。
The first 100 numbers are:
前 100 个数字是：
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:
如果您仍想自己计算值，可以使用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
编辑：21.08.2014
Solution 2
解决方案2
I thought it would be useful to add a working example of lazyiterativefactorial functionthat uses big numbersto get exactresult with memoizationand cacheas 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 closureto limit variable name visibility.
我假设您会使用某种闭包来限制变量名的可见性。
回答by Gabriele Petrioli
You should use a loop.
您应该使用循环。
Here are two versions benchmarked by calculating the factorial of 100 for 10.000 times.
这是通过计算 100 的阶乘 10.000 次进行基准测试的两个版本。
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/
直播地址：http: //jsfiddle.net/xMpTv/
My results show:
- Recursive~ 150 milliseconds
- Iterative~ 5 milliseconds..
我的结果显示：
-递归~ 150 毫秒
-迭代~ 5 毫秒..
回答by Waleed Amjad
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.
我仍然认为 Margus 的答案是最好的。但是，如果您还想计算 0 到 1 范围内数字的阶乘（即伽马函数），则不能使用该方法，因为查找表必须包含无限值。
However, you canapproximate 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
一种很好的近似方法是 Lanczos 的方法
Here is an implementation in JavaScript (ported from a calculator I wrote months ago):
这是 JavaScript 中的一个实现（从我几个月前写的一个计算器移植过来）：
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.
你现在可以做一些很酷的事情，比如factorial(0.41)，等等，但准确度可能有点偏差，毕竟，它是结果的近似值。
回答by xPheRe
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.
您可以预先计算一些值以加快速度。
回答by António Almeida
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):
编辑：
如果你真的想保存一些字符，你可以使用箭头函数（21 字节）：
f=n=>(n<2)?1:f(n-1)*n
回答by Abdennour TOUMI
Just One line with ES6
仅一行 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>回答by oezi
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.
对于非常大的 n，您可以使用斯特林近似- 但这只会给您一个近似值。
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):
EDIT2：这将是使用循环的解决方案（这将是更好的选择）：
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 approximationfor larger values (assumed you have to be realy fastand don't have to be thatexact on such big numbers).
我认为最好的解决办法是使用缓存的值，如Margus提及并使用斯特灵公式为较大的值（假设你要真的快，不必须是准确的对这么大的数字）。
回答by Phil H
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.
看哪，记忆器，它接受任何单参数函数并将其记忆。结果证明比@xPheRe 的解决方案略快，包括对缓存大小的限制和相关检查，因为我使用了短路等等。
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.
在我的 Chrome 机器上，它比递归版本快大约 25 倍，比 xPheRe 快 10%。
回答by Roland Bouman
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:
我偶然发现了这个帖子。受到这里所有贡献的启发，我想出了我自己的版本，它有两个我以前从未见过的功能：1) 检查以确保参数是非负整数 2) 从缓存中制作一个单元和使其成为一个自包含代码的函数。为了好玩，我试图让它尽可能紧凑。有些人可能会觉得这很优雅，有些人可能会认为它非常晦涩难懂。无论如何，这里是：
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.
您可以预先填充缓存，也可以允许在调用进行时填充缓存。但是初始元素（对于 fact(0) 必须存在，否则它将中断。
Enjoy :)
享受 ：）
回答by tfmontague
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`,
// was 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
forloops andwhileloops have similar performance, aforloop without an initialization-expression and final-expression looks odd; probably better to writefor(; n > 0;)aswhile(n > 0) - Only two parameters
nandrare used, so in theory less parameters means less time spent allocating memory - Uses a decremented loop which checks if
nis zero - I've heard theories that computers are better at checking binary numbers (0 and 1) than they are at checking other integers
- 递归函数，即使有记忆，也有函数调用的开销（基本上是将函数推入堆栈），其性能不如使用循环
- 虽然
for循环和while循环具有相似的性能，for但没有初始化表达式和最终表达式的循环看起来很奇怪；可能更好地写for(; n > 0;)为while(n > 0) - 只使用了两个参数
nandr，所以理论上参数越少，分配内存的时间就越少 - 使用递减循环来检查是否
n为零 - 我听说计算机在检查二进制数（0 和 1）方面比在检查其他整数方面更好的理论
