Fast Factorial Algorithms

# Fast Factorial Functions Source: [http://www.luschny.de/math/factorial/FastFactorialFunctions.htm](http://www.luschny.de/math/factorial/FastFactorialFunctions.htm) N \! There are five algorithms which everyone who wants to compute the factorial n\! = 1\.2\.3\.\.\.n should know\. - The algorithm[SplitRecursive](http://www.luschny.de/math/factorial/csharp/FactorialSplit.cs.html), because it is simple and the fastest algorithm which does not use prime factorization\. - The algorithm[PrimeSwing](http://www.luschny.de/math/factorial/csharp/FactorialPrimeSwing.cs.html), because it is the \(asymptotical\) fastest algorithm known to compute n\!\. The algorithm is based on the notion of the 'Swing Numbers' and computes n\! via the*[prime factorization](http://www.luschny.de/math/factorial/csharp/PrimeSieve.cs.html)*of these numbers\. - The ingenious algorithm of[Moessner](http://www.luschny.de/math/factorial/csharp/FactorialAdditiveMoessner.cs.html)which uses only additions\! Though of no practical importance \(because it is slow\), it has the fascination of an unexpected solution\. - The[Poor Man's](http://www.luschny.de/math/factorial/csharp/FactorialPoorMans.cs.html)algorithm which uses no Big\-Integer library and can be easily implemented in any computer language and is even fast up to 10000\!\. - The[ParallelPrimeSwing](http://www.luschny.de/math/factorial/java/FactorialParallelPrimeSwing.java.html)algorithm, which is the PrimeSwing algorithm with improved performance using methods of concurrent programming and thus taking advantage of multiple core processors\. - If you do not attach great importance to high performance then get a BigInteger library and use:``` BigInt recfact(long start, long n) { long i; if (n <= 16) { BigInt r = new BigInt(start); for (i = start + 1; i < start + n; i++) r *= i; return r; } i = n / 2; return recfact(start, i) * recfact(start + i, n - i); } BigInt factorial(long n) { return recfact(1, n); } ``` - And here is an algorithm which nobody needs, for theSimple\-Mindedonly:long factorial\(long n\) \{return n <= 1 ? 1 : n\*factorial\(n\-1\);\}Just don't use it\! --- An example of aPrimeSwingcomputation:  As this example shows an efficient computation of the factorial function reduces to an efficient computation of the swinging factorial n≀\. Some information about these numbers can be found[here](http://www.luschny.de/math/swing/SwingingFactorial.html)and[here](http://oeis.org/A056040)\. The prime factorization of the swing numbers is crucial for the implementation of the PrimeSwing algorithm\. A concise description of this algorithm is given in this[write\-up \(pdf\)](http://www.luschny.de/math/factorial/SwingIntro.pdf)and in the SageMath link below \(Algo 5\)\. --- LinkContent[Algorithms](http://www.luschny.de/math/factorial/description.html)A very short description of 21 algorithms for computing the factorial function n\!\.X[Julia factorial](http://www.luschny.de/math/factorial/JuliaFactorial.html)\*NEW\* The factorial function based on the swinging factorial which in turn is computed via prime factorization implemented in Julia\.[Mini Library](http://www.luschny.de/math/factorial/scala/FactorialScalaCsharp.htm)The factorial function, the binomial function, the double factorial, the swing numbers and an efficient prime number sieve implemented in Scala and GO\.[Browse Code](http://www.luschny.de/math/factorial/index.html)Various algorithms implemented in Java, C\# and C\+\+\.[SageMath](http://www.luschny.de/math/factorial/sagemath.html)Implementations in SageMath\.[LISP](http://www.luschny.de/math/factorial/LispFactorial.html)Implementations in Lisp\.[Benchmarks](http://www.luschny.de/math/factorial/Benchmark.html)*Benchmark 2013: With MPIR 2\.6 you can calculate 100\.000\.000\! in less than a minute provided you use one of the fast algorithms described here\.*[Conclusions](http://www.luschny.de/math/factorial/conclusions.html)Which algorithm should we choose?[Download](http://www.luschny.de/math/factorial/download.html)Download a test application and benchmark yourself\.X[Approximations](http://www.luschny.de/math/factorial/approx/SimpleCases.html)A unique collection\! Approximation formulas\.[Gamma quot](http://www.luschny.de/math/factorial/approx/gammaquot.html)Bounds for Gamma\(x\+1\)/Gamma\(x\+1/2\)[Gamma shift](http://www.luschny.de/math/factorial/factandgamma.html)Why is Gamma\(n\)=\(n\-1\)\! and not Gamma\(n\)=n\! ?X[Hadamard](http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunction.html) Hadamard's Gamma function and a new factorial function [\[MathJax version\]](http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunctionMJ.html)[History](http://www.luschny.de/math/factorial/history.html)Not even Wikipedia knows this\! The early history of the factorial function\.[Notation](http://www.luschny.de/math/factorial/FactorialNotation.htm)On the notation n\For coders only\. Go to the page of the day\.[Sage / Python](http://www.luschny.de/math/factorial/SwingFactorialSagePython.html)Implementation of the swing algorithm\.‼[Double Factorial](http://www.luschny.de/math/factorial/DoubleFactorial.html)The fast double factorial function\.[Prime Factorial](http://www.luschny.de/math/factorial/PrimeProxy.htm)Primfakultaet \('The Primorial', in German\.\)[Bibliography](http://www.luschny.de/math/factorial/approx/bibliography.html)Bibliography on Inequalities for the Gamma function\.X[Bernoulli & Euler](http://www.luschny.de/math/primes/berneulerincl.html)Exotic Applications: Inclusions for the Bernoulli and Euler numbers\.[Binomial](http://www.luschny.de/math/factorial/FastBinomialFunction.html)Fast Binomial Function \(Binomial Coefficients\)\.[Variations](http://www.luschny.de/math/seq/variations.html)A combinatorial generalization of the factorial\.X[Stieltjes' CF](http://www.luschny.de/math/factorial/approx/continuedfraction.html)On Stieltjes' Continued Fraction for the Gamma Function\.[al\-Haytham / Lagrange](http://www.luschny.de/math/factorial/AlHaythamLagrangeTheorem.html)The ignorance of some western mathematicians\. A deterministic factorial primality test\.[Factorial Digits](http://www.luschny.de/math/factorial/FactorialDigits.html)Number of decimal digits of 10n\Calculate n\! for n up to 9\.999\.999\.999 \.[RPN\-Factorial](http://www.luschny.de/math/factorial/RPNFactorial.html)The retro\-factorial page\Awesome\! Permutation trees, the combinatorics of n\!\. [Perm\. trees](http://www.luschny.de/math/factorial/combi/PermutationTrees.html)Download a[pdf\-poster](http://www.luschny.de/math/seq/PermutationTrees5Color.pdf)with 120 permutation trees\ [LogGamma](http://www.luschny.de/math/factorial/plots/LogGammaPlots.html)Plots of the factorial \(gamma\) function\.[External links](http://www.luschny.de/math/factorial/GammaLinks.html)Some bookmarks\.Fast\-Factorial\-Functions:**The Homepage of Factorial Algorithms\.**\(C\) Peter Luschny, 2000\-2017\. All information and all source code in this directory is free under the[Creative Commons Attribution\-ShareAlike 3\.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/)\. This page is listed on the famous "Dictionary of Algorithms and Data Structures" at the National Institute of Standards and Technology's web site \(NIST\)\. Apr\. 2003 / Apr\. 2017 : 800,000 visitors\! Thank you\! [Rational Trees](http://www.luschny.de/math/seq/RationalTreesAndBinaryPartitions.html)[Variants of Variations](http://www.luschny.de/math/seq/variations.html)[Eulerian Polynomials](http://www.luschny.de/math/euler/EulerianPolynomials.html)[vonStaudt Primes](http://www.luschny.de/math/zeta/VonStaudtPrimes.html)[Irregular Primes](http://www.luschny.de/math/primes/irregular.html)[Generalized Binomial](http://www.luschny.de/math/swing/divideswingandconquer/GeneralizedBinomialCoefficients.html)[Bernoulli Manifesto](http://www.luschny.de/math/zeta/The-Bernoulli-Manifesto.html)[Bernoulli Function](http://www.luschny.de/math/zeta/BernoulliFunctionIntroduction.html)[Partitions Stirling](http://www.luschny.de/math/seq/CountingWithPartitions.html)[Zeta Polynomials](http://www.luschny.de/math/seq/ZetaPolynomials.htm)[Perfect Rulers](http://www.luschny.de/math/rulers/prulers.html)[Clausen Numbers](http://www.luschny.de/math/zeta/ClausenNumbers.htm)[Hadamard Gamma](http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunction.html)[History Factorial](http://www.luschny.de/math/factorial/history.html)[Permutation Trees](http://www.luschny.de/math/factorial/combi/PermutationTrees.html)[Swiss Knife](http://www.luschny.de/math/seq/SwissKnifePolynomials.html)[Swinging Factorial](http://www.luschny.de/math/swing/SwingingFactorial.html)[Worpitzky Triangle](http://www.luschny.de/ect/Worpitzky-Triangle.html)