Quelle est la fonction factorielle la plus rapide en JavaScript?

, Vous devez utiliser une boucle.

voici deux versions référencées en calculant le factoriel de 100 pour 10.000 fois.

Récursive

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

itératif

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

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

mes résultats montrent:

- Recursive ~ 150 millisecondes

- itératif ~ 5 millisecondes..

je pense toujours que la réponse de Margus est la meilleure. Cependant, si vous voulez calculer les facteurs de nombres dans l'intervalle 0 à 1 (c.-à-d. la fonction gamma) aussi bien, alors vous ne pouvez pas utiliser cette approche parce que la table de recherche devra contenir des valeurs infinies.

cependant, vous can se rapprochent des valeurs des facteurs, et il est assez rapide, plus rapide que récursivement se appelant ou en boucle au moins (en particulier quand les valeurs commencez à obtenir les plus grands).

une bonne méthode d'approximation est celle de Lanczos

voici une implémentation en JavaScript (adapté d'une calculatrice que j'ai écrite il y a des mois):

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

vous pouvez maintenant faire des choses fraîches comme factorial(0.41) , etc Cependant la précision pourrait être un peu off, après tout, il est une approximation du résultat.

table de recherche est la voie évidente à suivre, si vous travaillez avec des nombres naturels. Pour calculer n'importe quel factoriel en temps réel, vous pouvez l'accélérer avec un cache, sauvant les nombres que vous avez calculés avant. Quelque chose comme:

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

Vous pouvez précalculer certaines valeurs, afin d'accélérer encore plus.

voici ma solution:

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

C'est la façon la plus simple (moins de caractères / lignes) j'ai trouvé, seulement une fonction avec une ligne de code.

modifier:

Si vous voulez vraiment sauver quelques chars, vous pouvez aller avec un fonction de flèche (21 octets) :

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

fonction de récursion courte et facile (vous pourriez le faire avec une boucle, aussi, mais je ne pense pas que cela ferait une différence dans la performance):

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

pour un très grand n, Vous pouvez utiliser le approximation de stirlings - mais cela ne vous donnera qu'une valeur approximative.

EDIT: un commentaire sur pourquoi je suis un downvote pour cela aurait été sympa...

EDIT2: ce serait la solution utilisant une boucle (qui serait le meilleur choix):

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

je pense que la meilleure solution serait d'utiliser les valeurs cachées, comme Margus l'a mentionné et d'utiliser le approximation de stirlings pour des valeurs plus grandes (supposé que vous devez être really fast et ne pas avoir à être que exact sur de tels grands nombres).

voici, le memoizer, qui prend n'importe quelle fonction d'argument simple et le mémoize. Il s'avère être légèrement plus rapide que la solution de @xPheRe , y compris la limite sur la taille du cache et la vérification associée, parce que j'utilise courtcircuitation et ainsi de suite.

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

environ 25x plus rapide sur ma machine en Chrome que la version recursive, et 10% plus rapide que xPheRe.

je suis tombé sur ce post. Inspiré par toutes les contributions ici, je suis venu avec ma propre version, qui a deux caractéristiques que je n'ai pas vu discuté avant: 1) Une vérification pour s'assurer que l'argument est un entier non négatif 2) Création d'une unité à partir du cache et de la fonction pour en faire un bit de code autonome. Pour le plaisir, j'ai essayé de le rendre aussi compact que possible. Certains le trouvent élégant, d'autres le trouvent terriblement obscur. Bref, le voilà:

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

vous pouvez soit pré-remplir le cache, soit permettre qu'il soit rempli au fur et à mesure que les appels passent. Mais l'élément initial (pour les faits (0) doit être présent ou il se brisera.

Enjoy:)

une seule ligne avec 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>

il est très simple d'utiliser ES6

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

voir un exemple ici

le code pour calculer factoriel dépend de vos besoins.

1. Êtes-vous préoccupé par le débordement?
2. quelle gamme d'entrées aurez-vous?
3. est-il plus important pour vous de minimiser la taille ou le temps?
4. Qu'allez-vous faire du factoriel?

en ce qui concerne les points 1 et 4, il est souvent plus utile d'avoir une fonction d'évaluation de la log du factoriel directement plutôt que d'avoir une fonction pour évaluer le factoriel lui-même.

Voici une blog post qui traite de ces questions. Voici un certain C# code pour le calcul log factoriel qui serait trivial à port à JavaScript. Mais ce n'est peut-être pas le mieux pour vos besoins selon vos réponses aux questions ci-dessus.

C'est une version compacte en boucle

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

ou vous pourriez outrepasser L'objet mathématique (version récursive):

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

ou joindre les deux approches ...

Juste pour être complet, voici une version récursive qui permettrait optimisation de l'appel de queue. Je ne suis pas sûr que les optimisations des appels de queue soient effectuées en JavaScript..

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

pour l'appeler:

rFact(x, 1);

il s'agit d'une solution itérative qui utilise moins d'espace dans la pile et économise les valeurs calculées précédemment d'une manière auto-mémorielle:

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

notez aussi que j'ajoute ceci à l'objet mathématique qui est un objet littéral donc il n'y a pas de prototype. Il suffit plutôt de les lier directement à la fonction.

je crois que ce qui suit est le morceau de code le plus durable et efficace des commentaires ci-dessus. Vous pouvez l'utiliser dans votre architecture js d'application globale... et, ne vous inquiétez pas de l'écrire dans des espaces de noms multiples (puisque c'est une tâche qui n'a probablement pas besoin de beaucoup d'augmentation). J'ai inclus 2 noms de méthode (basé sur la préférence), mais les deux peuvent être utilisés comme ils sont juste des références.

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

Cela fait la mise en cache des 100 premières valeurs à la volée, et n'introduit pas de variable externe dans scope pour le cache, stockant les valeurs comme propriétés de l'objet de fonction lui-même, ce qui signifie que si vous savez que factorial(n) a déjà été calculé, vous pouvez simplement l'appeler factorial[n] , ce qui est légèrement plus efficace. L'exécution de ces 100 premières valeurs prendra moins de milliseconde temps dans les navigateurs modernes.

Voici une implémentation qui calcule les facteurs positifs et négatifs. C'est simple et rapide.

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

Voici mon code

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

fourni par http://javascript.info/tutorial/number-math comme un moyen simple d'évaluer si un objet est un entier approprié pour le calcul.

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

un ensemble simple de factoriels Mémoïsés qui nécessitent des calculs redondants, peut être traité avec" multiplier par 1", ou sont un chiffre qui est une équation simple ne vaut pas la peine de traitement en direct.

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

après avoir examiné les entrées des autres membres (à l'exclusion de L'avis de journal, bien que je puisse mettre en œuvre que plus tard) je suis allé de l'avant et a jeté ensemble un script qui est assez simple. J'ai commencé avec un simple exemple JavaScript OOP inculte et j'ai construit une petite classe pour gérer les factoriels. J'ai alors mis en œuvre ma version de la Memoization qui a été suggérée ci-dessus. J'ai également mis en œuvre la Factorialisation en sténo-graphie mais j'ai fait un petit ajustement d'erreur; j'ai changé le "n<2" en "n<3". "n<2" traiterait toujours n = 2 qui serait un déchet, parce que vous itéreriez pour un 2*1=2; c'est un déchet à mon avis. Je l'ai modifié en "n<3"; parce que si n est 1 ou 2 il retournera tout simplement n, s'il est 3 ou plus il évaluera normalement. Bien sûr, comme les règles s'appliquent, j'ai placé mes fonctions dans l'ordre décroissant de l'exécution supposée. J'ai ajouté l'option bool(true|false) pour permettre une modification rapide entre memo'ED et l'exécution normale (vous ne savez jamais quand vous voulez échanger sur votre page sans avoir à changer le "style"") Comme je l'ai dit plus tôt, la variable factorielles memoized est définie avec les 3 positions de départ, en prenant 4 caractères, et en minimisant les calculs inutiles. Tout ce qui passe après la troisième itération vous manipulez les maths à deux chiffres plus. Je me suis dit que si vous aviez assez de stickler à ce sujet, vous tourneriez sur une table factorielle (telle qu'implémentée).

Qu'est-ce que j'ai prévu après ça? stockage local et / session pour permettre une mise en cache au cas par cas du nécessaire itérations, traitant essentiellement de la question de la" table " mentionnée ci-dessus. Cela permettrait également d'économiser massivement de l'espace côté base de données et serveur. Cependant, si vous allez avec localStorage vous seriez essentiellement aspirer l'espace sur votre ordinateur des utilisateurs simplement pour stocker une liste de nombres et faire leur écran regarder plus rapidement, cependant sur une longue période de temps avec un besoin immense ce serait lent. Je pense que sessionStorage (dégagement après les feuilles de Tab) serait une bien meilleure route. Éventuellement combiner cela avec une auto équilibrage du serveur / cache dépendant local? L'Utilisateur a a besoin de x itérations. L'utilisateur B besoin d'Y itérations. X+Y / 2=montant nécessaire caché localement. Puis il suffit de détecter et bidouiller avec le temps de charge et les repères de temps d'exécution en direct pour chaque utilisateur jusqu'à ce qu'il s'ajuste à l'optimisation pour le site lui-même. Merci!

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

cette édition implémente une autre suggestion de pile et me permet d'appeler la fonction comme factorielle(vrai)(5), qui était un de mes objectifs. : 3 j'ai aussi supprimé quelques assignations inutiles, et raccourci quelques noms de variables non-publiques.

exploitant le fait que Number.MAX_VALUE < 171! , nous pouvons simplement utiliser un table de recherche complète composé de seulement 171 éléments de réseau compact prenant moins de 1,4 kilo-octets de mémoire.

Une recherche rapide de la fonction avec le runtime complexité O(1) et minimal d'accès au tableau les frais généraux de l'151960920" serait ensuite comme suit:

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