Szukasz naprawdę szybkiej implementacji funkcji silni w JavaScript. Jakieś sugestie?

Możesz wyszukać (1 ... 100)! na Wolfram | Alpha, aby wstępnie obliczyć sekwencję silni.

Pierwsze 100 liczb to:

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

Jeśli nadal chcesz samodzielnie obliczyć wartości, możesz skorzystać z zapamiętywania :

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

Edycja: 21.08.2014

Rozwiązanie 2

Pomyślałem, że warto byłoby dodać działający przykład leniwej iteracyjnej funkcji silni, która używa dużych liczb, aby uzyskać dokładny wynik z zapamiętywaniem i pamięcią podręczną jako porównaniem

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

Zakładam, że użyłbyś jakiegoś rodzaju domknięcia, aby ograniczyć widoczność nazw zmiennych.

Ref : BigNumber Sandbox : JsFiddle

Powinieneś użyć pętli.

Oto dwie wersje porównane przez obliczenie silni 100 dla 10.000 razy.

Rekursywne

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

Wielokrotny

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

Na żywo pod adresem: http://jsfiddle.net/xMpTv/

Moje wyniki pokazują:
- rekurencyjne ~ 150 milisekund
- iteracyjne ~ 5 milisekund.

Nadal uważam, że odpowiedź Margusa jest najlepsza. Jeśli jednak chcesz obliczyć silnie liczb z zakresu od 0 do 1 (tj. Funkcję gamma), nie możesz użyć tego podejścia, ponieważ tabela przeglądowa będzie musiała zawierać nieskończone wartości.

Możesz jednak przybliżyć wartości silni i jest to dość szybkie, szybsze niż rekurencyjne wywoływanie siebie lub przynajmniej zapętlanie (zwłaszcza gdy wartości zaczynają się zwiększać).

Dobrą metodą aproksymacji jest metoda Lanczosa

Oto implementacja w JavaScript (przeniesiona z kalkulatora, który napisałem kilka miesięcy temu):

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

Możesz teraz robić fajne rzeczy, takie jak factorial(0.41)itp., Jednak dokładność może być trochę mniejsza, w końcu jest to przybliżenie wyniku.

Tablica przeglądowa jest oczywistym sposobem, jeśli pracujesz z liczbami naturalnymi. Aby obliczyć dowolną silnię w czasie rzeczywistym, możesz ją przyspieszyć za pomocą pamięci podręcznej, zapisując liczby, które obliczałeś wcześniej. Coś jak:

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

Możesz wstępnie obliczyć niektóre wartości, aby jeszcze bardziej przyspieszyć.

Oto moje rozwiązanie:

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

To najprostszy sposób (mniej znaków / linii) , jaki znalazłem, tylko funkcja z jedną linią kodu.

Edycja:
Jeśli naprawdę chcesz zapisać kilka znaków, możesz skorzystać z funkcji strzałki (21 bajtów) :

f=n=>(n<2)?1:f(n-1)*n

Tylko jedna linia z 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>

krótka i łatwa funkcja rekurencyjna (można by to również zrobić za pomocą pętli, ale nie sądzę, żeby to miało wpływ na wydajność):

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

dla bardzo dużego n można użyć przybliżenia Stirlingsa - ale to da tylko przybliżoną wartość.

EDYCJA: komentarz na temat tego, dlaczego otrzymuję za to głos przeciw, byłby miły ...

EDIT2: to byłoby soulution wykorzystujące pętlę (co byłoby lepszym wyborem):

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

Myślę, że najlepszym rozwiązaniem byłoby użycie wartości z pamięci podręcznej, jak wspomniał Margus, i użycie przybliżenia Stirlingsa dla większych wartości (zakładając, że musisz być naprawdę szybki i nie musisz być tak dokładny na tak dużych liczbach).

Oto memoizer, który przyjmuje dowolną funkcję jednoargumentową i zapamiętuje ją. Okazuje się, że jest nieznacznie szybszy niż rozwiązanie @ xPheRe , w tym ograniczenie rozmiaru pamięci podręcznej i związane z tym sprawdzanie, ponieważ używam shortcircuiting i tak dalej.

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

Około 25x szybciej na moim komputerze w Chrome niż wersja rekurencyjna i 10% szybciej niż xPheRe.

Najszybsza funkcja silni

Myślę, że ta wersja oparta na pętli może być najszybszą funkcją silni.

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

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

A oto moje rozumowanie:

• Funkcje rekurencyjne, nawet z zapamiętywaniem, mają narzut wywołania funkcji (w zasadzie wypychanie funkcji na stos), który jest mniej wydajny niż użycie pętli
• Podczas gdy forpętle i whilepętle mają podobną wydajność, forpętla bez wyrażenia inicjalizującego i wyrażenia końcowego wygląda dziwnie; chyba lepiej pisaćfor(; n > 0;) jakowhile(n > 0)
• Tylko dwa parametry nir są wykorzystywane, więc teoretycznie mniej parametrów oznacza krótszy czas spędzony przydzielania pamięci
• Używa zmniejszonej pętli, która sprawdza, czy nwynosi zero - słyszałem teorie, że komputery lepiej sprawdzają liczby binarne (0 i 1) niż inne liczby całkowite

Trafiłem na ten post. Zainspirowany wszystkimi opisami tutaj, wymyśliłem własną wersję, która ma dwie funkcje, których wcześniej nie widziałem: 1) Sprawdzenie, czy argument jest nieujemną liczbą całkowitą 2) Wyciągnięcie jednostki z pamięci podręcznej i funkcja, aby uczynić go jednym samodzielnym bitem kodu. Dla zabawy starałem się, aby był jak najmniejszy. Niektórym może się to wydawać eleganckie, innym może wydawać się to strasznie niejasne. Tak czy inaczej, oto jest:

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

Możesz albo wstępnie wypełnić pamięć podręczną, albo zezwolić na jej wypełnianie w trakcie połączeń. Ale element początkowy (dla faktu (0) musi być obecny, w przeciwnym razie się zepsuje.

Cieszyć się :)

Używanie ES6 jest bardzo proste

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

Zobacz przykład tutaj

Oto jedno rozwiązanie:

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

Używając ES6 możesz to osiągnąć szybko i krótko:

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

Kod do obliczenia silni zależy od Twoich wymagań.

1. Martwisz się przepełnieniem?
2. Jaki zakres danych wejściowych będziesz mieć?
3. Czy ważniejsze jest zminimalizowanie rozmiaru lub czasu?
4. Co zamierzasz zrobić z silnią?

Jeśli chodzi o punkty 1 i 4, często bardziej przydatne jest posiadanie funkcji bezpośredniej oceny logarytmu silni niż funkcji oceny samej silni.

Oto post na blogu omawiający te kwestie. Oto kod C # do obliczania silni dziennika , którego przeniesienie do JavaScript byłoby trywialne. Jednak w zależności od odpowiedzi na powyższe pytania może nie odpowiadać Twoim potrzebom.

To jest kompaktowa wersja oparta na pętli

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

Lub możesz nadpisać obiekt Math (wersja rekurencyjna):

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

Lub połącz oba podejścia ...

Wykorzystując fakt Number.MAX_VALUE < 171!, że możemy po prostu użyć pełnej tabeli przeglądowej składającej się z zaledwie 171 kompaktowych elementów tablicy, zajmujących mniej niż 1,4 kilobajta pamięci.

Funkcja szybkiego wyszukiwania ze złożonością środowiska wykonawczego O (1) i minimalnym narzutem na dostęp do tablicy wyglądałaby wówczas następująco:

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

Jest to tak precyzyjne i tak szybkie, jak przy użyciu Numbertypu danych. Obliczanie tabeli przeglądowej w JavaScript - jak sugerują inne odpowiedzi - zmniejszy dokładność, kiedy n! > Number.MAX_SAFE_INTEGER.

Kompresja tabeli środowiska uruchomieniowego za pomocą programu gzip zmniejsza jej rozmiar na dysku z około 3,6 do 1,8 kilobajta.

Jedna linia odpowiedzi:

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

Silnia iteracyjna BigIntdla bezpieczeństwa

Rozwiązanie wykorzystuje BigIntfunkcję ES 2018 + / 2019.

To jest działający przykład użycia BigInt, ponieważ wiele odpowiedzi tutaj Numberprawie od razu wymyka się bezpiecznej granicy (MDN). Nie jest najszybszy, ale jest prosty, a przez to bardziej przejrzysty w dostosowywaniu innych optymalizacji (takich jak pamięć podręczna pierwszych 100 liczb).

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

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

   return p
}

Przykładowe użycie

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

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

// 9332621544394415268169923885626670049071596826438162146859296389521759999
// 3229915608941463976156518286253697920827223758251185210916864000000000000
// 000000000000n
factorial(100)

• Na nkońcu literału numerycznego, takiego jak, 1303nwskazuje, że jest to BigInttyp.
• Pamiętaj, że nie powinieneś mieszać się BigIntz Numbernimi, chyba że wyraźnie je wymuszasz, a to może spowodować utratę dokładności.

Korzystając z funkcji ES6, można pisać kod w JEDNEJ linii i bez rekursji :

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

var factorial=(n)=>Array.from(
       {length: n}, (v, k) => k+1)   /*Generate Array [1, 2, .., n -1, n]*/
     .reduce(
       (a, b) => a*b, 1 /*Multiply all aarray items; one with the next*/
     ); 
     

var n = prompt('Give us "n", we will calculate "n!" ?');

if (n) {
  alert(`${n}! = ${factorial(n)}`)
}

Dla kompletności, oto wersja rekurencyjna, która pozwoliłaby na optymalizację wywołań ogonowych. Nie jestem jednak pewien, czy optymalizacje wywołań ogonowych są wykonywane w JavaScript ..

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

Aby to nazwać:

rFact(x, 1);

Jest to rozwiązanie iteracyjne, które wykorzystuje mniej miejsca na stosie i zapisuje wcześniej obliczone wartości w sposób samozapamiętujący:

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

Zauważ również, że dodam to do obiektu Math, który jest literałem obiektu, więc nie ma prototypu. Raczej po prostu wiążąc je bezpośrednio z funkcją.

Uważam, że poniższy fragment kodu jest najbardziej zrównoważonym i wydajnym z powyższych komentarzy. Możesz użyć tego w swojej globalnej architekturze js aplikacji ... i nie martw się o pisanie jej w wielu przestrzeniach nazw (ponieważ jest to zadanie, które prawdopodobnie nie wymaga dużego rozszerzenia). Dołączyłem 2 nazwy metod (na podstawie preferencji), ale obie mogą być używane, ponieważ są tylko referencjami.

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

Powoduje to buforowanie pierwszych 100 wartości w locie i nie wprowadza zewnętrznej zmiennej do zakresu pamięci podręcznej, przechowując wartości jako właściwości samego obiektu funkcji, co oznacza, że ​​jeśli wiesz, że factorial(n)zostało już obliczone, możesz po prostu nazywaj go factorial[n], co jest nieco bardziej wydajne. Uruchomienie tych pierwszych 100 wartości zajmie mniej niż milisekundę w nowoczesnych przeglądarkach.

Oto implementacja, która oblicza zarówno dodatnie, jak i ujemne silnie. To szybkie i proste.

var factorial = function(n) {
  return n > 1
    ? n * factorial(n - 1)
    : n < 0
        ? n * factorial(n + 1)
        : 1;
}

Oto jeden, który sam stworzyłem, nie używaj liczb powyżej 170 ani poniżej 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;
}

Oto mój kod

function factorial(num){
    var result = num;
    for(i=num;i>=2;i--){
        result = result * (i-1);
    }
    return result;
}

Pętla w pamięci podręcznej powinna być najszybsza (przynajmniej w przypadku wielokrotnego wywołania)

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

function isNumeric(n) {
    return !isNaN(parseFloat(n)) && isFinite(n)
}

Udostępnione przez http://javascript.info/tutorial/number-math jako prosty sposób oceny, czy obiekt jest prawidłową liczbą całkowitą do obliczenia.

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

Prosty zestaw zapamiętanych silni, które wymagają zbędnych obliczeń, mogą być przetwarzane przez „pomnożenie przez 1” lub stanowić jedną cyfrę, która jest prostym równaniem, którego nie warto przetwarzać na żywo.

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

Po przejrzeniu danych wejściowych od innych członków (z wyjątkiem porady dziennika, chociaż mogę to zaimplementować później) poszedłem do przodu i wrzuciłem razem skrypt, który jest dość prosty. Zacząłem od prostego, niewykształconego przykładu OOP JavaScript i zbudowałem małą klasę do obsługi silni. Następnie wdrożyłem moją wersję Memoization, która została zasugerowana powyżej. Zaimplementowałem również skrótową faktoryzację, jednak dokonałem niewielkiej korekty błędu; Zmieniłem „n <2” na „n <3”. „n <2” nadal przetworzyłoby n = 2, co byłoby marnotrawstwem, ponieważ wykonałbyś iterację dla 2 * 1 = 2; moim zdaniem jest to strata. Zmieniłem to na „n <3”; ponieważ jeśli n wynosi 1 lub 2, zwróci po prostu n, a jeśli będzie równe 3 lub więcej, oszacuje normalnie. Oczywiście zgodnie z regułami umieściłem moje funkcje w porządku malejącym według zakładanego wykonania. Dodałem opcję bool (true | false), aby umożliwić szybkie przełączanie między wykonywaniem zapamiętanym a normalnym (po prostu nigdy nie wiesz, kiedy chcesz zamienić się na swojej stronie bez konieczności zmiany „stylu”). Jak powiedziałem wcześniej, Zmienna zapamiętana silnia jest ustawiana z 3 pozycjami początkowymi, przyjmuje 4 znaki i minimalizuje marnotrawstwo obliczeń. Wszystko poza trzecią iteracją masz do czynienia z dwucyfrową matematyką plus. Wydaje mi się, że gdybyś był wystarczająco pedantem, działałbyś na silniowej tabeli (jak zaimplementowano). biorąc 4 znaki i minimalizując zbędne obliczenia. Wszystko poza trzecią iteracją masz do czynienia z dwucyfrową matematyką plus. Wydaje mi się, że gdybyś był wystarczająco pedantem, działałbyś na silniowej tabeli (jak zaimplementowano). biorąc 4 znaki i minimalizując zbędne obliczenia. Wszystko poza trzecią iteracją masz do czynienia z dwucyfrową matematyką plus. Wydaje mi się, że gdybyś był wystarczająco pedantem, działałbyś na silniowej tabeli (jak zaimplementowano).

Co po tym zaplanowałem? lokalna & | pamięć sesji, aby umożliwić przechowywanie pojedynczych przypadków w pamięci podręcznej potrzebnych iteracji, zasadniczo obsługując omówiony powyżej problem „tabeli”. Pozwoliłoby to również znacznie zaoszczędzić miejsce po stronie bazy danych i serwera. Jeśli jednak korzystasz z localStorage, zasadniczo zajmujesz miejsce na komputerze użytkownika, aby zapisać listę liczb i sprawić, by ich ekran WYGLĄDAŁ szybciej, jednak przez długi okres czasu z ogromną potrzebą byłoby to powolne. Myślę, że sessionStorage (czyszczenie po opuszczeniu karty) byłaby znacznie lepszą trasą. Ewentualnie połączyć to z samobalansującym serwerem / zależną lokalną pamięcią podręczną? Użytkownik A potrzebuje X iteracji. Użytkownik B potrzebuje Y iteracji. X + Y / 2 = Kwota wymagana lokalnie w pamięci podręcznej. Następnie po prostu wykrywaj testy porównawcze czasu wczytywania i wykonywania na żywo dla każdego użytkownika i baw się nimi, dopóki sam nie dostosuje się do optymalizacji pod kątem samej witryny. Dzięki!

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

Ta edycja implementuje kolejną sugestię stosu i pozwala mi nazwać funkcję silnią (prawda) (5), co było jednym z moich celów, które wyznaczyłem. : 3 Usunąłem też trochę niepotrzebnego przypisywania i skróciłem niektóre niepubliczne nazwy zmiennych.

Oto jeden z nowszymi funkcjami javascript fill , map , redukuj i konstruktor (oraz składnia grubych strzałek):

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

Edycja: zaktualizowano do obsługi n === 0

function computeFactorialOfN(n) {
  var output=1;
  for(i=1; i<=n; i++){
    output*=i;
  } return output;
}
computeFactorialOfN(5);