Ken*_*Ken 88 javascript math factorial
在JavaScript中寻找一个非常快速的factorial函数实现.有什么建议？
Mar*_*gus 104
你可以搜索(1 ... 100)!在WolframAlpha上预先计算阶乘序列.
前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;
} ?
我认为添加一个懒惰 迭代 因子函数的工作示例是有用的,该函数使用大数字来获得具有memoization和cache的精确结果作为比较
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);
我假设您将使用某种闭包来限制变量名称可见性.
Gab*_*oli 87
你应该使用一个循环.
以下是通过计算10.00倍的阶乘100来进行基准测试的两个版本.
递归
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;
}
我的结果显示:
- 递归 ~150毫秒
- 迭代 ~5毫秒..
Wal*_*jad 29
我仍然认为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),但是精确度可能有点偏差,毕竟它是结果的近似值.
xPh*_*eRe 17
如果您使用自然数字,查找表是显而易见的方法.要实时计算任何阶乘,您可以使用缓存加速它,从而节省您之前计算过的数字.就像是:
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;
})();
您可以预先计算某些值,以便进一步加快速度.
Ant*_*ida 14
这是我的解决方案:
function fac(n){
return(n<2)?1:fac(n-1)*n;
}
这是我发现的最简单的方法(更少的字符/行),只有一个代码行的函数.
编辑:
如果你真的想保存一些字符,可以使用箭头功能 (21字节):
f=n=>(n<2)?1:f(n-1)*n
简单易用的递归函数(你也可以用循环来做,但我认为这不会对性能产生任何影响):
function factorial (n){
if (n==0 || n==1){
return 1;
}
return factorial(n-1)*n;
}
对于一个非常大的n,你可以使用斯特林近似 - 但这只会给你一个近似值.
编辑:评论为什么我得到一个downvote这将是很好的...
EDIT2:这将是使用循环的解决方案(这将是更好的选择):
function factorial (n){
j = 1;
for(i=1;i<=n;i++){
j = j*i;
}
return j;
}
我认为最好的解决方案是使用缓存值,正如Margus所提到的那样,并使用斯特林近似值来表示更大的值(假设您必须快速,并且不必在如此大的数字上那么精确).
看,这个记忆者,它采用任何单个参数函数并记住它.原来比@ 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;
}());
我的机器在Chrome中比递归版快约25倍,比xPheRe快10%.
与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>我认为这个基于循环的版本可能是最快的阶乘函数。
function factorial(n, r = 1) {
while (n > 0) r *= n--;
return r;
}
// Default parameters `r = 1`,
// was introduced in ES6
这是我的推理：
for循环和while循环具有相似的性能，for但没有初始化表达式和最终表达式的循环看起来很奇怪；可能更好地写for(; n > 0;)为while(n > 0)nand r，所以理论上参数越少，分配内存的时间就越少n为零 - 我听说计算机在检查二进制数（0 和 1）方面比在检查其他整数方面更好的理论利用这一事实Number.MAX_VALUE < 171!，我们可以简单地使用一个完整的查找表，该表仅由 171 个紧凑数组元素组成，占用内存不到 1.4 KB。
运行时复杂度为O(1)且数组访问开销最小的快速查找函数将如下所示：
// 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这与使用Number数据类型一样精确和快速。正如其他一些答案所暗示的那样，在 Javascript 中计算查找表会降低精度n! > Number.MAX_SAFE_INTEGER。
通过 gzip 压缩运行时表可将其在磁盘上的大小从大约 3.6 KB 减少到 1.8 KB。
我遇到过这篇文章.受到所有贡献的启发,我想出了我自己的版本,它有两个我以前没有见过的功能: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];
您可以预先填充缓存,也可以在调用过程中填充缓存.但是初始元素(事实(0)必须存在或者它会破裂.
请享用 :)
小智 5
这是一种解决方案：
function factorial(number) {
total = 1
while (number > 0) {
total *= number
number = number - 1
}
return total
}
使用 ES6，您可以快速和简短地实现它：
const factorial = n => [...Array(n + 1).keys()].slice(1).reduce((acc, cur) => acc * cur, 1)