Algorithmes rapides pour le calcul de la factorielle
J'ai trouvé cette page décrivant un certain nombre d'algorithmes pour le calcul de la factorielle. Malheureusement, les explications sont courtes et je n'ai pas envie de passer au crible la ligne après la ligne de code source pour comprendre les principes de base d'algorithmes.
Quelqu'un peut-il me diriger vers des descriptions plus détaillées de ces (ou autres) des algorithmes pour le calcul de la factorielle?
Edit: Cette page décrit la méthode de factorisation, la technique commun à tous le meilleur factorielle des algorithmes. Il contient aussi un bel exemple de code en Python. L'auteur des liens vers une description binaire de fractionnement et les références d'un article dans le Journal des Algorithmes ("la Complexité de Calcul de Factorielles") qui a l'air prometteur, si je pourrais obtenir mes mains sur elle.
- Si votre factorielle est grand, et que vous voulez une approximation, n'oubliez pas de Stirling de l'approximation. J'ai remarqué qu'il n'était pas mentionné dans cette page. en.wikipedia.org/wiki/Stirling%27s_approximation
- Je cherche à calculer la grande factorielles exactement...peut-être que j'aurais été plus clair dans ma question. Merci pour la suggestion, si!
- Vous pouvez également essayer de mine Rapide exacte bigint factorielle
Vous devez vous connecter pour publier un commentaire.
Découvrez ce papier (lien PDF) par Richard Fateman. Les exemples de code sont en Lisp, mais dans tous les cas, une grande partie du secret se résume à réduire au minimum le nombre de bignum (précision arbitraire entier) les calculs que vous avez à faire.
Naturellement, si vous n'avez pas besoin/ont bignums, il est trivial; soit une table de recherche ou une simple boucle sera très bien.
EDIT: Si vous pouvez utiliser une approximation de réponse, vous pouvez calculer le logarithme de la factorielle directement par la somme de
log(k)
pourk = 2 ... n
, ou en utilisant le vénérable L'approximation de Stirling. Vous voulez travailler avec le logarithme dans la mesure du possible d'éviter les débordements; en particulier, un naïf application de Stirling rapprochement débordement dans beaucoup d'endroits où il n'est pas obligatoire.Il y a aussi une autre méthode. Cette méthode est détaillée ici qui divise par deux le montant de la multiplication pour un peu de l'addition et de la soustraction. Vous souhaitez sans doute la première méthode indiquée, et la deuxième méthode présentée est une lecture intéressante si vous ne pouvez le comprendre.