Fast Factorial Functions
N !
--><br>There are five algorithms which everyone who wants to compute<br>the factorial n! = 1.2.3...n should know.
The algorithm
SplitRecursive,<br>because it is simple and the fastest algorithm which does not<br>use prime factorization.
The algorithm
PrimeSwing, because it is the (asymptotical) fastest<br>algorithm known to compute n!. The algorithm is based on the<br>notion of the 'Swing Numbers' and computes n! via the<br>prime factorization<br>of these numbers.
The ingenious<br>algorithm of
Moessner which uses only additions! Though of no<br>practical importance (because it is slow), it has the fascination<br>of an unexpected solution.
The
Poor<br>Man's algorithm which uses no Big-Integer library<br>and can be easily implemented in any computer language and is<br>even fast up to 10000!.
The
ParallelPrimeSwing algorithm, which is the PrimeSwing<br>algorithm with improved performance using methods of concurrent<br>programming and thus taking advantage of multiple core processors.
If you do not attach great importance to high performance then<br>get a BigInteger library and use:
BigInt recfact(long start, long n) {<br>long i;<br>if (n
And here is an<br>algorithm which nobody needs, for the Simple-Minded<br>only: long factorial(long n) {return n<br>Just don't use it!
An example of a PrimeSwing computation:
As this example shows an efficient computation of the factorial function<br>reduces to an efficient computation of the swinging factorial n≀.<br>Some information about these numbers can be found<br>here<br>and here.<br>The prime factorization of the swing numbers is crucial for the implementation<br>of the PrimeSwing algorithm.
A concise description of this<br>algorithm is given in this write-up (pdf) and<br>in the SageMath link below (Algo 5).
Link<br>Content
Algorithms<br>A very short description of 21 algorithms for computing the factorial function n!.
Julia factorial
*NEW* The factorial function based on the swinging factorial which in turn is computed<br>via prime factorization implemented in Julia.
Mini Library
The factorial function, the binomial function, the<br>double factorial, the swing numbers and an efficient<br>prime number sieve implemented in Scala and GO.
Browse Code<br>Various algorithms implemented in<br>Java, C# and C++.
SageMath<br>Implementations in SageMath.
LISP<br>Implementations in Lisp.
Benchmarks
Benchmark 2013:<br>With MPIR 2.6 you can calculate 100.000.000! in less than a minute provided you use<br>one of the fast algorithms described here.
Conclusions<br>Which algorithm should we choose?
Download<br>Download a test application and benchmark yourself.
Approximations<br>A unique collection! Approximation formulas.
Gamma quot<br>Bounds for Gamma(x+1)/Gamma(x+1/2)
Gamma shift<br>Why is Gamma(n)=(n-1)! and not Gamma(n)=n! ?
Hadamard
Hadamard's Gamma function and a new factorial function
[MathJax version]
History<br>Not even Wikipedia knows this!
The early history of the factorial function.
Notation<br>On the notation n!
Binary Split<br>For coders only. Go to the page of the day.
Sage / Python<br>Implementation of the swing algorithm.
Double Factorial<br>The fast double factorial function.
Prime Factorial<br>Primfakultaet ('The Primorial', in German.)
Bibliography<br>Bibliography on Inequalities for the Gamma function.
Bernoulli &<br>Euler<br>Exotic Applications:
Inclusions for the Bernoulli and Euler numbers.
Binomial<br>Fast Binomial Function (Binomial Coefficients).
Variations<br>A combinatorial generalization of the factorial.
Stieltjes'<br>CF<br>On Stieltjes' Continued Fraction for the<br>Gamma Function.
al-Haytham /<br>Lagrange<br>The ignorance of some western mathematicians.<br>A deterministic factorial primality test.
Factorial Digits<br>Number of decimal digits of 10n!
Calculator<br>Calculate n! for n up to 9.999.999.999 .
RPN-Factorial<br>The retro-factorial page!
Permutations<br>Awesome! Permutation trees, the combinatorics of n!.
Perm. trees<br>Download a pdf-poster<br>with 120 permutation trees!
Gamma
LogGamma<br>Plots of the factorial (gamma) function.
External links<br>Some bookmarks.
Fast-Factorial-Functions: The Homepage<br>of Factorial Algorithms. (C) Peter Luschny, 2000-2017. All information and<br>all source code in this directory is free under the<br>Creative Commons<br>Attribution-ShareAlike 3.0 Unported License. This page is listed on the famous "Dictionary of Algorithms<br>and Data Structures" at the National Institute of Standards and Technology's<br>web site (NIST). Apr. 2003 / Apr. 2017 : 800,000 visitors! Thank you!
Rational<br>Trees<br>Variants of<br>Variations<br>Eulerian<br>Polynomials<br>vonStaudt<br>Primes<br>Irregular<br>Primes<br>Generalized<br>Binomial
Bernoulli<br>Manifesto<br>Bernoulli<br>Function<br>Partitions<br>Stirling<br>Zeta<br>Polynomials<br>Perfect<br>Rulers<br>Clausen<br>Numbers
Hadamard<br>Gamma<br>History<br>Factorial<br>Permutation<br>Trees<br>Swiss<br>Knife<br>Swinging<br>Factorial<br>Worpitzky<br>Triangle
Visit also our survey of the Bernoulli numbers on the occasion of the 300-th<br>anniversary of the publication of
Jacob Bernoulli's Ars Conjectandi, 1713-2013.
-->