JavaScript中的快速因子函数
在JavaScript中寻找一个真正的快速实现阶乘函数。 有什么build议？
你可以search（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 如果您仍想自己计算这些值，则可以使用记忆法 ：
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
解决scheme2
我认为这将是有益的，添加一个惰性 迭代 阶乘函数的工作示例，使用大数字来获得准确的结果与记忆和caching作为比较
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);
我假设你会使用某种封闭来限制variables名称的可见性。
Ref ： BigNumber Sandbox ： JsFiddle
你应该使用一个循环。
这里有两个版本，通过计算10.000倍的100的阶乘为基准。
recursion
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/
我的结果显示：
– recursion约150毫秒
– 迭代〜5毫秒
我仍然认为玛格斯的答案是最好的。 但是，如果要计算0到1范围内的数字阶乘（即伽马函数），则不能使用该方法，因为查找表必须包含无限值。
但是，您可以近似估计阶乘的值，而且速度相当快，比recursion调用本身或至less循环它快（特别是当值开始变大时）。
一个很好的近似方法是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)等等，但是准确性可能有点偏离，毕竟这是近似的结果。
查找表是显而易见的方式，如果你正在使用自然数。 要实时计算任何阶乘，可以使用caching加速，保存之前计算的数字。 就像是：
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; })();
您可以预先计算一些数值，以加快速度。
这是我的解决scheme：
function fac(n){ return(n<2)?1:fac(n-1)*n; }
这是我find的最简单的方法（less字符/行） ，只有一个代码行的function。
编辑：
如果你真的想保存一些字符，你可以使用箭头function （21字节） ：
f=n=>(n<2)?1:f(n-1)*n
简单而又简单的recursion函数（你也可以用一个循环来实现，但是我不认为这会对性能产生任何影响）：
function factorial (n){ if (n==0 || n==1){ return 1; } return factorial(n-1)*n; }
对于一个非常大的n，你可以使用斯特林近似 – 但这只会给你一个近似值。
编辑：评论为什么我得到一个downvote这将是不错的…
编辑2：这将是使用循环（这将是更好的select）的营养：
function factorial (n){ j = 1; for(i=1;i<=n;i++){ j = j*i; } return j; }
我认为最好的解决scheme是使用caching的值，正如Margus所说的那样，并且使用更大值的斯特林近似 （假设你必须快速且不必如此大的数字）。
看哪，记忆者，它采取任何单一的参数function，并记住它。 结果比@ xPheRe的解决scheme稍微快一些，包括caching大小的限制和相关的检查，因为我使用了短路等等。
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中我的机器上的速度比recursion版本快大约25倍，比xPheRe快10％。
我遇到这个post。 受到这里所有贡献的启发，我想出了自己的版本，它有两个我以前没有看过的function：1）检查以确保参数是一个非负整数2）使单元退出caching使其成为一个独立的代码位的function。 为了好玩，我试图尽可能的简洁。 有些人可能会觉得优雅，其他人可能会认为这是非常模糊的。 无论如何，这里是：
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];
您可以预先填充caching，也可以在通话过程中填充caching。 但是最初的元素（对于事实（0））必须存在，否则将会中断。
请享用 ：）
使用ES6非常简单
const factorial = n => n ? (n * factorial(n-1)) : 1;
在这里看到一个例子
计算阶乘的代码取决于您的要求。
- 你担心溢出吗？
- 你有什么样的投入？
- 减less规模或时间对你来说更重要吗？
- 你用什么来处理阶乘？
关于第1点和第4点，直接用函数来评估阶乘的日志通常更有用，而不是有一个函数来评估阶乘本身。
这里有一个博客文章 ，讨论这些问题。 这里有一些计算对数因子的C＃代码 ，这对于移植到JavaScript来说是微不足道的。 但是根据你对上述问题的回答，这可能不是最好的。
为了完整起见，这里是一个recursion的版本，可以调用tail调用。 我不知道如果尾巴调用优化是在JavaScript中执行..
function rFact(n, acc) { if (n == 0 || n == 1) return acc; else return rFact(n-1, acc*n); }
调用它：
rFact(x, 1);
这是一个迭代解决scheme，它使用更less的堆栈空间，并以自我记忆的方式保存以前计算的值：
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
另外请注意，我将这个添加到Math对象是一个对象文字，所以没有原型。 而只是直接绑定这些函数。
我相信以下是上述评论中最具可持续性和最有效率的一段代码。 你可以在你的全局应用程序js体系结构中使用它…并且不用担心把它写在多个命名空间中（因为它可能不需要太多的扩展）。 我已经包含了2个方法名（基于首选项），但都可以使用，因为它们只是引用。
Math.factorial = Math.fact = function(n) { if (isNaN(n)||n<0) return undefined; var f = 1; while (n > 1) { f *= n--; } return f; };
// if you don't want to update the Math object, use `var factorial = ...` Math.factorial = (function() { var f = function(n) { if (n < 1) {return 1;} // no real error checking, could add type-check return (f[n] > 0) ? f[n] : f[n] = n * f(n -1); } for (i = 0; i < 101; i++) {f(i);} // precalculate some values return f; }()); factorial(6); // 720, initially cached factorial[6]; // 720, same thing, slightly faster access, // but fails above current cache limit of 100 factorial(100); // 9.33262154439441e+157, called, but pulled from cache factorial(142); // 2.6953641378881614e+245, called factorial[141]; // 1.89814375907617e+243, now cached
这样可以实时caching前100个值，并且不会将外部variables引入到caching的作用域中，并将值存储为函数对象本身的属性，这意味着如果知道factorial(n)已经计算，你可以简单地把它称为factorial[n] ，这是稍微有效的。 运行这些前100个值将在现代浏览器中花费亚毫秒时间。
这是一个计算正面和负面因子的实现。 这是快速和简单的。
var factorial = function(n) { return n > 1 ? n * factorial(n - 1) : n < 0 ? n * factorial(n + 1) : 1; }
这是我的代码
function factorial(num){ var result = num; for(i=num;i>=2;i--){ result = result * (i-1); } return result; }
function isNumeric(n) { return !isNaN(parseFloat(n)) && isFinite(n) }
由http://javascript.info/tutorial/number-math提供，作为评估对象是否为适当计算的整数的简单方法。;
var factorials=[[1,2,6],3];
需要冗余计算的一组简单因子可以用“乘以1”来处理，或者是一个数字，这是一个不值得现场处理的简单方程。
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; });
在审查了其他成员的input（不包括Log的build议，尽pipe我稍后可以实现），我继续前进，把一个相当简单的脚本扔在一起。 我从一个简单的未受教育的JavaScript OOP示例开始，并构build了一个小类来处理阶乘。 然后，我实现了上面提到的Memoization版本。 我也执行了速记析因，但是我做了一个小小的错误调整; 我把“n <2”改为“n <3”。 “n <2”仍然会处理n = 2，这将是一种浪费，因为您将迭代2 * 1 = 2; 这在我看来是浪费。 我把它改成了“n <3”。 因为如果n是1或2，它将简单地返回n，如果它是3或更多，它将正常评估。 当然，按照规则的规定，我按照假定执行的顺序来执行我的function。 我在bool（true | false）选项中添加了允许在备忘录和正常执行之间快速更改的function（你永远不知道什么时候想在页面上进行交换而不需要改变“样式”）正如我之前所说的记忆因子variables设置为3个起始位置，取4个字符，并最小化浪费计算。 在第三次迭代之前，你正在处理两位数的math加。 我想，如果你足够坚持，你会运行在一个阶乘表（如实施）。
我在这之后计划了什么？ 本地和会话存储以允许逐个caching需要的迭代，基本上处理上面所说的“表”问题。 这也将大量节省数据库和服务器端空间。 但是，如果你使用localStorage，你本质上就是在用户计算机上吮吸空间，只是为了存储一个数字列表，并且让他们的屏幕更快一点，但是在很长的一段时间内，这对于巨大的需求来说是很慢的。 我正在思考sessionStorage（Tab离开后清除）将是一个更好的路线。 可能结合这与自我平衡服务器/本地依赖caching？ 用户A需要X次迭代。 用户B需要Y次迭代。 X + Y / 2 =本地caching的数量。 然后，只需检测并调整每个用户的加载时间和执行时间基准，直到它自行调整为网站本身的优化。 谢谢！
编辑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); });
这个编辑实现了另一个Stackbuild议，并允许我将这个函数调用为阶乘（true）（5），这是我设定的目标之一。 ：3我也删除了一些不必要的赋值，并且删除了一些非公有的variables名。
这是一个紧凑的循环版本
function factorial( _n ) { var _p = 1 ; while( _n > 0 ) { _p *= _n-- ; } return _p ; }
或者你可以重写Math对象（recursion版本）：
Math.factorial = function( _x ) { return _x <= 1 ? 1 : _x * Math.factorial( --_x ) ; }
或者join这两种方法…
这是我自己做的一个，不要用170或者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; }
caching循环应该是最快的（至less在多次调用时）
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; } })();
这可能会很简单，也许从这个简短的代码，你可以根据你的需要更好地设置它：
<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>
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));
这将返回n的阶乘
function f(n) { var e = n; if (e == 1 | e == 0) return 1; while (n--) { if (n < 1) break; e *= n; } return e }
使用ES6function，可以在一行上编写代码， 而无需recursion ：
var factorial=(n)=>Array.from({length:n},(v,k)=>k+1).reduce((a,b)=>a*b,1)
这是我知道的一个最简单的方法来进行阶乘函数
function factorial(num) { var result = 1; for(var i = 2; i<= num; i++) { result *= i; } return result; }
这里是一个使用更新的JavaScript函数填充 ， 映射 ， 减less和构造函数 （和胖箭头语法）：
Math.factorial = n => n === 0 ? 1 : Array(n).fill(null).map((e,i)=>i+1).reduce((p,c)=>p*c)
编辑：更新以处理n === 0
因为一个因子只是从给定的数字到1的退化乘法，所以循环乘法确实更容易：
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; } }
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]; } })();
我发现这在相同的情况下有用：
function factorialDivision(n, d) { var value = 1; for (d++ < n) { value *= d; } return value; }
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
function findFact() { result = 1; //Variable declared earlier operation = " ! "; //Variable declared earlier for(var i = 0;i<x;i++) { //Variable declared earlier (x is user input) result*=(xi); } write(x.toString() + operation + " = " + result.toString()); //Function I made myself result = 0; }
我觉得这个代码很容易理解; 它运行一个for循环，乘以“结果”x（数字），然后x-1，然后x-2，依此类推。 同样，你可以使用1x2x3x4...xn而不是nxn-1x...x2x1
function findFact() { result = 1;//Variable declared earlier operation = " ! ";//Variable declared earlier for(var i = 1;i<=x;i++) {//Variable declared earlier (x is user input) result*=(xi); } write(x.toString() + operation + " = " + result.toString());//Function I made myself result = 0; }
