JavaScript 中最快的阶乘函数是什么?

IT技术 javascript math factorial
2021-01-23 08:40:55

在 JavaScript 中寻找阶乘函数的真正快速实现有什么建议吗?

6个回答

您可以搜索 (1...100)!在 Wolfram|Alpha上预先计算阶乘序列。

前 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

如果您仍想自己计算值,可以使用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;
}

编辑:21.08.2014

解决方案2

我认为添加一个延迟 迭代 阶乘函数的工作示例会很有用,该示例使用大数字通过记忆缓存作为比较来获得精确结果

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

我假设您会使用某种闭包来限制变量名的可见性。

参考BigNumber 沙箱JsFiddle

您的第二个解决方案可以简化为function factorial (n) { for (var i = f.length; i <= n; i++) f.push(f[i - 1].multiply(i.toString())); return f[n]; }另请参阅我的答案,该答案使用更新的内置BigInt库而不是第三方库。
2021-03-20 08:40:55
所以,第 100 个数字有 158 个字符长
2021-03-20 08:40:55
超过 6402373705728000 的值将被截断,因此如果您打算使用这种方法,请确保在使用上述表格之前转换为指数。
2021-03-24 08:40:55
@DavidScottKirby Javascript 会自动将这些数字转换为最接近的 64 位浮点数表示。代码中没有完整精度数字的真正好处是减小了文件大小。
2021-04-08 08:40:55

您应该使用循环。

这是通过计算 100 的阶乘 10.000 次进行基准测试的两个版本。

递归

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

迭代

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

直播地址:http : //jsfiddle.net/xMpTv/

我的结果显示:
-递归~ 150 毫秒
-迭代~ 5 毫秒..

@Tadeck,谢谢。在这种情况下,记忆确实非常有用,这就是为什么Margus 的答案被选为正确答案的原因:)
2021-03-22 08:40:55
@HWTech,您永远不会调用这些方法。您的测试比较了定义两种方法的速度..而不是它们执行所需的时间..这是一个更好的测试(仅尝试 15 的阶乘)
2021-03-22 08:40:55
而不是rval = rval * i;你可以写rval *= i;
2021-03-27 08:40:55
递归的 1 行版本:function factorial(num) { return (num == 1) ? num : num * arguments.callee(num-1); }
2021-04-06 08:40:55
+1 很好的答案!尽管当有多个调用来计算更大数字的阶乘时,记忆可能是合理的。
2021-04-09 08:40:55

我仍然认为 Margus 的答案是最好的。但是,如果您还想计算 0 到 1 范围内数字的阶乘(即伽马函数),则不能使用该方法,因为查找表必须包含无限值。

但是,您可以近似阶乘的值,而且它非常快,至少比递归调用自身或循环它更快(尤其是当值开始变大时)。

一种很好的近似方法是 Lanczos 的方法

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

你现在可以做一些很酷的事情,比如factorial(0.41),等等,但是准确度可能有点偏差,毕竟,它是结果的近似值。

我建议将 for 循环下方的部分更改为var d3d4 = Math.exp((z + 0.5) * Math.log(z + 5.5) - z - 5.5); return d1 * d2 * d3d4;. 这允许您计算高达 169 的阶乘!而不是目前只有 140!。这非常接近使用Number数据类型的最大可表示阶乘,即 170!。
2021-03-21 08:40:55
刚刚为我节省了大量时间,非常感谢:)
2021-04-10 08:40:55
非常有趣的方法,谢谢。
2021-04-11 08:40:55

如果您使用自然数,查找表是显而易见的方法。要实时计算任何阶乘,您可以使用缓存加速它,保存您之前计算过的数字。就像是:

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

您可以预先计算一些值以加快速度。

我已经根据这个答案为任何给定的函数创建了一个自动记忆器(也稍微快了 :)),还包括对缓存大小的限制。stackoverflow.com/a/10031674/36537
2021-03-31 08:40:55

这是我的解决方案:

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

这是我发现的最简单的方法(更少的字符/行),只有一个代码行的函数。


编辑:
如果你真的想保存一些字符,你可以使用箭头函数 (21 字节)

f=n=>(n<2)?1:f(n-1)*n
不幸的是,即使很高兴看到并且形式简短,这也是最慢的方法。
2021-03-19 08:40:55
节省更多f=n=>n?f(n-1)*n:1...
2021-03-25 08:40:55