Was ist die schnellste Fakultätsfunktion in JavaScript? [geschlossen]

94

Auf der Suche nach einer wirklich schnellen Implementierung der Fakultätsfunktion in JavaScript. Irgendwelche Vorschläge?

Ken
quelle
8
Was ist der mögliche Bereich von Argumenten?
Nikita Rybak
5
Haben Sie darüber nachgedacht, Fakultäten vorab zu berechnen und die Werte in einer Nachschlagetabelle zu speichern?
Waleed Amjad
2
Was ist die Anwendung einer solchen Funktion? Mit anderen Worten, wofür werden Sie es verwenden?
Pointy
@ Nikita Rybak, nur 1 Agrument (n). Wenn (n> 170) e = Unendlichkeit
Ken
@ Pointy, noch ein Mathe-Rechner-Service.
Ken

Antworten:

110

Sie können nach (1 ... 100) suchen! auf WolframAlpha , um die faktorielle Sequenz vorab zu berechnen.

Die ersten 100 Zahlen sind:

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

Wenn Sie die Werte dennoch selbst berechnen möchten, können Sie Memoization verwenden :

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

Bearbeiten: 21.08.2014

Lösung 2

Ich dachte, es wäre nützlich, ein funktionierendes Beispiel für eine faule iterative Fakultätsfunktion hinzuzufügen , die große Zahlen verwendet , um ein genaues Ergebnis mit Memoisierung und Cache als Vergleich zu erhalten

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

Ich gehe davon aus, dass Sie eine Art Verschluss verwenden würden , um die Sichtbarkeit von Variablennamen einzuschränken.

Ref : BigNumber Sandbox : JsFiddle

Margus
quelle
Werte nach 6402373705728000 werden abgeschnitten. Wenn Sie diesen Ansatz verwenden, stellen Sie sicher, dass Sie in Exponential konvertieren, bevor Sie die oben genannte Tabelle verwenden.
David Scott Kirby
1
@DavidScottKirby Javascript konvertiert diese Zahlen automatisch in die nächste 64-Bit-Float-Darstellung. Der eigentliche Vorteil, wenn der Code nicht die Zahlen mit voller Genauigkeit enthält, ist die geringere Dateigröße.
Le_m
Ihre zweite Lösung könnte vereinfacht werden, um function factorial (n) { for (var i = f.length; i <= n; i++) f.push(f[i - 1].multiply(i.toString())); return f[n]; }auch meine Antwort zu sehen , bei der die neuere integrierte Version BigIntanstelle einer Bibliothek eines Drittanbieters verwendet wird.
Patrick Roberts
95

Sie sollten eine Schleife verwenden.

Hier sind zwei Versionen, die durch 10.000-malige Berechnung der Fakultät 100 verglichen werden.

Rekursiv

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

Iterativ

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

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

Meine Ergebnisse zeigen:
- Rekursiv ~ 150 Millisekunden
- Iterativ ~ 5 Millisekunden ..

Gabriele Petrioli
quelle
+1 Tolle Antwort! Obwohl das Auswendiglernen bei mehreren Aufrufen zur Berechnung der Fakultäten für größere Zahlen sinnvoll sein kann.
Tadeck
@ Tadeck, danke. In der Tat ist das Auswendiglernen in diesem Fall sehr nützlich, und deshalb wird die Antwort von Margus als die richtige ausgewählt :)
Gabriele Petrioli
Eine 1-zeilige Version von rekursiv: Funktion Fakultät (num) {return (num == 1)? num: num * argument.callee (num-1); }
jbyrd
2
@HWTech, Sie rufen die Methoden nie auf. Ihr Test vergleicht die Geschwindigkeit der Definition der beiden Methoden .. nicht die Zeit, die sie für die Ausführung benötigen .. Dies ist ein besserer Test (versucht nur die Fakultät von 15)
Gabriele Petrioli
3
Stattdessen rval = rval * i;könnten Sie schreibenrval *= i;
Ryan
29

Ich denke immer noch, dass Margus 'Antwort die beste ist. Wenn Sie jedoch auch die Fakultäten von Zahlen im Bereich von 0 bis 1 (dh die Gammafunktion) berechnen möchten, können Sie diesen Ansatz nicht verwenden, da die Nachschlagetabelle unendliche Werte enthalten muss.

Sie können jedoch die Werte der Fakultäten approximieren, und dies ist ziemlich schnell, schneller als sich selbst rekursiv aufzurufen oder zumindest zu schleifen (insbesondere, wenn die Werte größer werden).

Eine gute Näherungsmethode ist die von Lanczos

Hier ist eine Implementierung in JavaScript (portiert von einem Taschenrechner, den ich vor Monaten geschrieben habe):

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

Sie können jetzt coole Sachen wie factorial(0.41)usw. machen, aber die Genauigkeit kann ein wenig abweichen, schließlich ist es eine Annäherung an das Ergebnis.

Waleed Amjad
quelle
ziemlich interessanter Ansatz, danke.
Ken
Ich habe mir gerade eine
Menge
Ich empfehle, den Teil unterhalb der for-Schleife auf zu ändern var d3d4 = Math.exp((z + 0.5) * Math.log(z + 5.5) - z - 5.5); return d1 * d2 * d3d4;. Auf diese Weise können Sie Fakultäten bis zu 169 berechnen! statt derzeit nur 140!. Dies ist ziemlich nahe an der maximal darstellbaren Fakultät unter Verwendung des NumberDatentyps, der 170! Ist.
le_m
18

Die Nachschlagetabelle ist der naheliegende Weg, wenn Sie mit natürlichen Zahlen arbeiten. Um eine Fakultät in Echtzeit zu berechnen, können Sie sie mit einem Cache beschleunigen und die zuvor berechneten Zahlen speichern. Etwas wie:

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

Sie können einige Werte vorberechnen, um sie noch schneller zu machen.

xPheRe
quelle
3
Basierend auf dieser Antwort habe ich für jede Funktion einen Auto-Memoizer erstellt (auch etwas schneller :)), der auch eine Begrenzung der Cache-Größe enthält. stackoverflow.com/a/10031674/36537
Phil H
16

Hier ist meine Lösung:

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

Es ist der einfachste Weg (weniger Zeichen / Zeilen), den ich gefunden habe, nur eine Funktion mit einer Codezeile.


Bearbeiten:
Wenn Sie wirklich einige Zeichen speichern möchten, können Sie eine Pfeilfunktion (21 Byte) verwenden :

f=n=>(n<2)?1:f(n-1)*n
António Almeida
quelle
7
Sparen Sie noch mehr mit f=n=>n?f(n-1)*n:1...
le_m
Leider ist dies der langsamste Weg, auch wenn es schön zu sehen und kurz ist .
Zibri
11

Nur eine Zeile mit ES6

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

Abdennour TOUMI
quelle
factorial = n => n <= 1 ? 1 : factorial(n - 1) * n
Naramsim
10

kurze und einfache rekursive Funktion (Sie könnten dies auch mit einer Schleife tun, aber ich denke nicht, dass dies einen Unterschied in der Leistung bewirken würde):

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

Für ein sehr großes n könnten Sie die Stirlings-Näherung verwenden - aber das gibt Ihnen nur einen ungefähren Wert.

EDIT: Ein Kommentar, warum ich dafür eine Abwertung bekomme, wäre schön gewesen ...

EDIT2: Dies wäre die Soulution mit einer Schleife (was die bessere Wahl wäre):

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

Ich denke , die beste Lösung , um die im Cache gespeicherten Werte zu verwenden wäre, als Margus und die Verwendung erwähnte Stirlings Näherung für größere Werte (vorausgesetzt man muss wirklich schnell und muß nicht sein , dass genau auf so großen Zahlen).

oezi
quelle
3
In Sprachen ohne Tail-Call-Optimierung (dh den am häufigsten verwendeten Sprachen) ist es besser, eine nicht rekursive Implementierung zu verwenden, wenn dies einfach ist, obwohl es verschiedene Möglichkeiten gibt: paulbarry.com/articles/2009/08/30 / Tail-Call-Optimierung
Daniel Earwicker
Das ist in der Tat definitiv nicht so schnell, da es nicht einmal TCO verwenden würde, wenn es implementiert würde. Aber es ist einfach und ich würde es nicht ablehnen. Es ist sicher nicht das schnellste.
Haylem
Die Tail-Call-Optimierung ist für diese Funktion nicht einmal möglich, da sich der rekursive Aufruf nicht in der Tail-Position befindet.
Fred Foo
3
@ Josh, ( nicht der Downvoter ) am schnellsten ist die Schleife mit Abstand.
Gabriele Petrioli
7

Siehe, der Memoizer, der jede einzelne Argumentfunktion übernimmt und sie auswendig lernt. Es stellt sich heraus, dass es geringfügig schneller ist als die Lösung von @ xPheRe , einschließlich der Begrenzung der Größe des Caches und der damit verbundenen Überprüfung, da ich Kurzschlüsse usw. verwende.

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

Ungefähr 25x schneller auf meinem Computer in Chrome als in der rekursiven Version und 10% schneller als bei xPheRe.

Phil H.
quelle
5

Ich bin auf diesen Beitrag gestoßen. Inspiriert von allen Beiträgen hier habe ich meine eigene Version entwickelt, die zwei Funktionen enthält, die ich zuvor noch nicht besprochen habe: 1) Eine Überprüfung, um sicherzustellen, dass das Argument eine nicht negative Ganzzahl ist. 2) Eine Einheit aus dem Cache erstellen und die Funktion, es zu einem eigenständigen Codebit zu machen. Zum Spaß habe ich versucht, es so kompakt wie möglich zu machen. Einige mögen das elegant finden, andere mögen es für schrecklich dunkel halten. Wie auch immer, hier ist es:

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

Sie können den Cache entweder vorab füllen oder ihn im Laufe der Anrufe füllen lassen. Aber das Anfangselement (für Tatsache (0) muss vorhanden sein, sonst wird es brechen.

Genießen :)

Roland Bouman
quelle
5

Schnellste Fakultätsfunktion

Ich denke, dass diese schleifenbasierte Version die schnellste Fakultätsfunktion sein könnte.

function factorial(n, r = 1) {
  while (n > 0) r *= n--;
  return r;
}

// Default parameters `r = 1`,
//   was introduced in ES6

Und hier ist meine Argumentation:

  • Rekursive Funktionen haben selbst bei Memoisierung den Overhead eines Funktionsaufrufs (im Grunde genommen das Verschieben von Funktionen auf den Stapel), der weniger performant ist als die Verwendung einer Schleife
  • Während forSchleifen und whileSchleifen eine ähnliche Leistung haben, forsieht eine Schleife ohne Initialisierungsausdruck und Endausdruck seltsam aus. wahrscheinlich besser zu schreiben for(; n > 0;)alswhile(n > 0)
  • Nur zwei Parameter nund rverwendet werden, so in der Theorie weniger Parameter bedeuten weniger Zeit damit verbracht das Zuweisen von Speicher
  • Verwendet eine dekrementierte Schleife, die prüft, ob nNull ist. Ich habe Theorien gehört, dass Computer Binärzahlen (0 und 1) besser prüfen können als andere Ganzzahlen
tfmontague
quelle
4

Mit ES6 ist das sehr einfach

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

Sehen Sie ein Beispiel hier

joseluiscc
quelle
4

Hier ist eine Lösung:

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

Mit ES6 können Sie es schnell und kurz erreichen:

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

Der Code zur Berechnung der Fakultät hängt von Ihren Anforderungen ab.

  1. Sind Sie besorgt über Überlauf?
  2. Welchen Eingangsbereich haben Sie?
  3. Ist es für Sie wichtiger, Größe oder Zeit zu minimieren?
  4. Was machst du mit der Fakultät?

In Bezug auf die Punkte 1 und 4 ist es oft nützlicher, eine Funktion zum direkten Auswerten des Protokolls der Fakultät zu haben, als eine Funktion zum Auswerten der Fakultät selbst.

Hier ist ein Blog-Beitrag , in dem diese Probleme behandelt werden. Hier ist ein C # -Code für die Berechnung der Protokollfaktor , der für die Portierung auf JavaScript trivial wäre. Abhängig von Ihren Antworten auf die obigen Fragen ist es möglicherweise nicht das Beste für Ihre Bedürfnisse.

John D. Cook
quelle
Nummerierte Liste sollte wahrscheinlich in Kommentaren sein. Alles, was übrig bleibt, sind zwei Links, und von Antworten nur auf Links wird abgeraten.
Barett
3

Dies ist eine kompakte schleifenbasierte Version

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

Oder Sie überschreiben das Math-Objekt (rekursive Version):

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

Oder verbinden Sie beide Ansätze ...

Sandro Rosa
quelle
1
Ich habe es im obigen Code behoben. Danke dir!
Sandro Rosa
3

Unter Ausnutzung der Tatsache Number.MAX_VALUE < 171!können wir einfach eine vollständige Nachschlagetabelle verwenden, die aus nur 171 kompakten Array-Elementen besteht, die weniger als 1,4 Kilobyte Speicher belegen.

Eine schnelle Suchfunktion mit Laufzeitkomplexität O (1) und minimalem Array-Zugriffsaufwand würde dann wie folgt aussehen:

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

Dies ist so präzise und schnell, wie es mit dem NumberDatentyp möglich ist. Das Berechnen der Nachschlagetabelle in Javascript verringert - wie einige andere Antworten vermuten lassen - die Genauigkeit, wenn n! > Number.MAX_SAFE_INTEGER.

Durch das Komprimieren der Laufzeittabelle über gzip wird die Größe der Festplatte von etwa 3,6 auf 1,8 Kilobyte reduziert.

le_m
quelle
3

Einzeilige Antwort:

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

timgfx
quelle
3

Iterative Fakultät mit BigIntaus Sicherheitsgründen

Die Lösung verwendet BigInteine ES 2018 + / 2019-Funktion.

Dies ist ein funktionierendes Beispiel BigInt, da viele Antworten hier Numberfast sofort der sicheren Grenze von (MDN) entgehen . Es ist nicht das schnellste, aber es ist einfach und somit klarer für die Anpassung anderer Optimierungen (wie ein Cache der ersten 100 Zahlen).

function factorial(nat) {
   let p = BigInt(1)
   let i = BigInt(nat)

   while (1 < i--) p *= i

   return p
}

Beispiel Verwendung

// 9.332621544394415e+157
Number(factorial(100))

// "933262154439441526816992388562667004907159682643816214685929638952175999
//  932299156089414639761565182862536979208272237582511852109168640000000000
//  00000000000000"
String(factorial(100))

// 9332621544394415268169923885626670049071596826438162146859296389521759999
// 3229915608941463976156518286253697920827223758251185210916864000000000000
// 000000000000n
factorial(100)
  • Das nam Ende eines numerischen Literals wie 1303nzeigt an, dass es sich um einen BigIntTyp handelt.
  • Denken Sie daran , dass Sie nicht mischen sollte BigIntmit , Numberwenn Sie sie ausdrücklich zwingen, und dass damit ein Verlust an Genauigkeit führen könnte.
Miau
quelle
3

Kann mit ES6-Funktionen Code in EINE Zeile und ohne Rekursion schreiben :

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

Abdennour TOUMI
quelle
2

Der Vollständigkeit halber ist hier eine rekursive Version, die eine Tail-Call-Optimierung ermöglichen würde. Ich bin mir nicht sicher, ob Tail-Call-Optimierungen in JavaScript durchgeführt werden.

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

Um es zu nennen:

rFact(x, 1);
Robert Jeppesen
quelle
ES6 unterstützt TCO, aber afaik diese Funktion ist standardmäßig noch in keiner größeren Engine aktiv
le_m
2

Dies ist eine iterative Lösung, die weniger Stapelspeicherplatz benötigt und zuvor berechnete Werte auf selbstmerkende Weise speichert:

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

Beachten Sie auch, dass ich dies dem Math-Objekt hinzufüge, das ein Objektliteral ist, sodass es keinen Prototyp gibt. Binden Sie diese einfach direkt an die Funktion.

bh-
quelle
Dies nutzt die Memoisierung für Teilprobleme nicht wirklich aus - Math.factorial(100); Math.factorial(500);berechnet beispielsweise die 1..100-Multiplikation zweimal.
Barett
2

Ich glaube, das Folgende ist der nachhaltigste und effizienteste Code aus den obigen Kommentaren. Sie können dies in Ihrer globalen Anwendungsarchitektur verwenden ... und sich keine Sorgen machen, es in mehrere Namespaces zu schreiben (da es sich um eine Aufgabe handelt, die wahrscheinlich nicht viel erweitert werden muss). Ich habe 2 Methodennamen (je nach Präferenz) eingefügt, aber beide können verwendet werden, da sie nur Referenzen sind.

Math.factorial = Math.fact = function(n) {
    if (isNaN(n)||n<0) return undefined;
    var f = 1; while (n > 1) {
        f *= n--;
    } return f;
};
Joe Johnson
quelle
Wenn Sie Ihre Multiplikation mit n * (n-1) * (n-2) * ... * 1statt umgekehrt beginnen, verlieren Sie bis zu 4 Stellen Genauigkeit für n >> 20.
le_m
2
// 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

Dadurch werden die ersten 100 Werte im laufenden Betrieb zwischengespeichert, und es wird keine externe Variable in den Bereich für den Cache eingefügt. Dabei werden die Werte als Eigenschaften des Funktionsobjekts selbst gespeichert. Wenn Sie also wissen, dass factorial(n)sie bereits berechnet wurden, können Sie dies bezeichnen Sie es einfach als factorial[n], was etwas effizienter ist. Das Ausführen dieser ersten 100 Werte dauert in modernen Browsern weniger als eine Millisekunde.

Scott Sauyet
quelle
Das habe ich nach 21 herausgefunden! Die Zahlen sind nicht zuverlässig.
AutoSponge
@AutoSponge Das liegt daran 21! > Number.MAX_SAFE_INTEGER, dass es daher nicht sicher als 64-Bit-Float dargestellt werden kann.
Le_m
2

Hier ist eine Implementierung, die sowohl positive als auch negative Fakultäten berechnet. Es ist schnell und einfach.

var factorial = function(n) {
  return n > 1
    ? n * factorial(n - 1)
    : n < 0
        ? n * factorial(n + 1)
        : 1;
}
Ilia Bykow
quelle
Normalerweise n! für n <0 ist nicht definiert. Siehe mathoverflow.net/questions/10124/the-factorial-of-1-2-3
le_m
2

Hier ist eine, die ich selbst gemacht habe. Verwenden Sie keine Zahlen über 170 oder unter 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;
}
TheBestGuest
quelle
Wenn Sie Ihre Multiplikation mit n * (n-1) * (n-2) * ... * 1 anstatt umgekehrt beginnen, verlieren Sie bis zu 4 Stellen Genauigkeit für n >> 20. Außerdem wird eine unerwünschte erzeugt globale Variable iund führt viel zu viele NumberKonvertierungen durch und gibt falsche Ergebnisse für 0! (Wie Sie sagten, aber warum?).
le_m
2

Hier ist mein Code

function factorial(num){
    var result = num;
    for(i=num;i>=2;i--){
        result = result * (i-1);
    }
    return result;
}
cse031sust02
quelle
1
Wenn (n> 170) e = Unendlichkeit. Und Ihr Code wird eine große Anzahl generieren. Wird es keine Überläufe geben?
Prime
Falsches Ergebnis für factorial(0). Wenn Sie Ihre Multiplikation mit n * (n-1) * (n-2) * ... * 1 anstatt umgekehrt beginnen, verlieren Sie bis zu 4 Stellen Genauigkeit für n >> 20. @prime: 170! > Number.MAX_VALUEund ist am besten vertreten mit Infinity.
le_m
2

Die zwischengespeicherte Schleife sollte am schnellsten sein (zumindest bei mehrmaligem Aufruf).

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;
  }
})();
Сухой27
quelle
2
function isNumeric(n) {
    return !isNaN(parseFloat(n)) && isFinite(n)
}

Wird von http://javascript.info/tutorial/number-math bereitgestellt, um auf einfache Weise zu bewerten, ob ein Objekt eine geeignete Ganzzahl für die Berechnung ist.

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

Ein einfacher Satz von gespeicherten Fakultäten, die redundante Berechnungen erfordern, kann mit "mit 1 multiplizieren" verarbeitet werden oder ist eine Ziffer, die eine einfache Gleichung ist, die es nicht wert ist, live verarbeitet zu werden.

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

Nachdem ich die Eingaben anderer Mitglieder überprüft hatte (mit Ausnahme der Protokollempfehlungen, obwohl ich diese möglicherweise später implementieren werde), habe ich ein Skript zusammengestellt, das ziemlich einfach ist. Ich begann mit einem einfachen ungebildeten JavaScript-OOP-Beispiel und baute eine kleine Klasse für den Umgang mit Fakultäten auf. Ich habe dann meine Version der oben vorgeschlagenen Memoization implementiert. Ich habe auch die Kurzfaktor-Faktorisierung implementiert, jedoch eine kleine Fehleranpassung vorgenommen. Ich habe "n <2" in "n <3" geändert. "n <2" würde immer noch n = 2 verarbeiten, was eine Verschwendung wäre, da Sie für 2 * 1 = 2 iterieren würden; Dies ist meiner Meinung nach eine Verschwendung. Ich habe es in "n <3" geändert; denn wenn n 1 oder 2 ist, gibt es einfach n zurück, wenn es 3 oder mehr ist, wird es normal ausgewertet. Da die Regeln gelten, habe ich meine Funktionen natürlich in absteigender Reihenfolge der angenommenen Ausführung angeordnet. Ich habe die Option bool (true | false) hinzugefügt, um einen schnellen Wechsel zwischen gespeicherter und normaler Ausführung zu ermöglichen (Sie wissen nur nie, wann Sie auf Ihrer Seite wechseln möchten, ohne den "Stil" ändern zu müssen) Die Variable für gespeicherte Fakultäten wird mit den 3 Startpositionen festgelegt, wobei 4 Zeichen verwendet werden und verschwenderische Berechnungen minimiert werden. Alles nach der dritten Iteration, mit der Sie zweistellige Mathematik plus verarbeiten. Ich denke, wenn Sie ein Stickler genug wären, würden Sie auf einer Fakultätstabelle (wie implementiert) laufen. Nehmen Sie 4 Zeichen und minimieren Sie verschwenderische Berechnungen. Alles nach der dritten Iteration, mit der Sie zweistellige Mathematik plus verarbeiten. Ich denke, wenn Sie ein Stickler genug wären, würden Sie auf einer Fakultätstabelle (wie implementiert) laufen. Nehmen Sie 4 Zeichen und minimieren Sie verschwenderische Berechnungen. Alles nach der dritten Iteration, mit der Sie zweistellige Mathematik plus verarbeiten. Ich denke, wenn Sie ein Stickler genug wären, würden Sie auf einer Fakultätstabelle (wie implementiert) laufen.

Was habe ich danach geplant? lokaler & | Sitzungsspeicher, um einen fallweisen Cache der erforderlichen Iterationen zu ermöglichen, wobei im Wesentlichen das oben erwähnte "Tabellen" -Problem behandelt wird. Dies würde auch massiv datenbank- und serverseitigen Speicherplatz sparen. Wenn Sie sich jedoch für localStorage entscheiden, würden Sie im Wesentlichen Speicherplatz auf dem Computer Ihres Benutzers beanspruchen, um einfach eine Liste von Zahlen zu speichern und den Bildschirm schneller aussehen zu lassen. Über einen langen Zeitraum mit einem immensen Bedarf wäre dies jedoch langsam. Ich denke, sessionStorage (Löschen nach Tab-Blättern) wäre eine viel bessere Route. Kombinieren Sie dies möglicherweise mit einem selbstausgleichenden Server / lokal abhängigen Cache? Benutzer A benötigt X Iterationen. Benutzer B benötigt Y-Iterationen. X + Y / 2 = Erforderlich lokal zwischengespeicherter Betrag. Dann erkennen Sie einfach die Benchmarks für Ladezeit und Ausführungszeit und spielen mit ihnen, bis sie sich an die Optimierung für die Site selbst anpassen. Vielen Dank!

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

Diese Bearbeitung implementiert einen weiteren Stack-Vorschlag und ermöglicht es mir, die Funktion als Fakultät (true) (5) zu bezeichnen, was eines meiner Ziele war. : 3 Ich habe auch einige unnötige Zuweisungen entfernt und einige nicht öffentliche Variablennamen kurzgeschrieben.

Sir Christopher Michael-Don Ro
quelle
Rückgabe undefinedfür 0!. ES6 ermöglicht das Ersetzen isNumericdurch Number.isInteger. Zeilen wie factorials[0][factorials[1]]=factorials[0][factorial_index]*(factorials[1]+1);sind völlig unlesbar.
le_m
2

Hier ist eine, die neuere Javascript-Funktionen zum Füllen , Zuordnen , Reduzieren und Konstruieren (und zur Fettpfeilsyntax) verwendet:

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

Bearbeiten: aktualisiert, um n === 0 zu behandeln

Ashley Coolman
quelle
2
Das ist eine ernsthaft hässliche unlesbare Codezeile.
Jungledev
1
Das ist eine nette Idee. Anstatt die Länge zweimal zu durchlaufen, können Sie die gesamte Logik in die Reduzierungsfunktion konvertieren und ihren Anfangswert verwenden, um den Kantenfall zu behandeln n === 0. Math.factorial = n => Array.from({ length: n }).reduce((product, _, i) => product * (i + 1), 1)
AlexSashaRegan
2
function computeFactorialOfN(n) {
  var output=1;
  for(i=1; i<=n; i++){
    output*=i;
  } return output;
}
computeFactorialOfN(5);
Odiljon Djamalov
quelle
2
Willkommen bei StackOverflow und vielen Dank für Ihre Hilfe. Vielleicht möchten Sie Ihre Antwort noch besser machen, indem Sie eine Erklärung hinzufügen.
Elias MP