Fast Factorial Functions

 N !

There are five algorithms which everyone who wants to compute
the factorial n! = 1.2.3...n should know.

The algorithm

SplitRecursive,
because it is simple and the fastest algorithm which does not
use prime factorization.
The algorithm

PrimeSwing, 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
of these numbers.
The ingenious
algorithm of

Moessner 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 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 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 the Simple-Minded
only: long factorial(long n) {return n <= 1 ? 1 : n*factorial(n-1);}
Just don't use it!

An example of a PrimeSwing computation:

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
and here.
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) and
in the SageMath link below (Algo 5).

  
 Link
 Content

  
Algorithms
A very short description of 21 algorithms for computing the factorial function n!.

 X
Julia factorial

*NEW* The factorial function based on the swinging factorial which in turn is computed
via prime factorization implemented in Julia.

  
Mini Library

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
Various algorithms implemented inJava, C# and C++.

  
SageMath
Implementations in SageMath.

  
LISP
Implementations in Lisp.

  
Benchmarks

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
Which algorithm should we choose?

  
Download
Download a test application and benchmark yourself.

 X
Approximations
A unique collection! Approximation formulas.

  
Gamma quot
Bounds for Gamma(x+1)/Gamma(x+1/2)

  
Gamma shift
Why is Gamma(n)=(n-1)! and not Gamma(n)=n! ?

 X

Hadamard

Hadamard's Gamma function and a new factorial function
[MathJax version]

  
History
Not even Wikipedia knows this!
The early history of the factorial function.

  
Notation
On the notation n!

  
Binary Split
For coders only. Go to the page of the day.

  
Sage / Python
Implementation of the swing algorithm.

 ‼
Double Factorial
 The fast double factorial function.

  
Prime Factorial
Primfakultaet ('The Primorial', in German.)

  
Bibliography
Bibliography on Inequalities for the Gamma function.

 X
Bernoulli &Euler
Exotic Applications:
Inclusions for the Bernoulli and Euler numbers.

  
Binomial
Fast Binomial Function (Binomial Coefficients).

  
Variations
A combinatorial generalization of the factorial.

 X
Stieltjes'
CF
On Stieltjes' Continued Fraction for theGamma Function.

  
al-Haytham /Lagrange
The ignorance of some western mathematicians.A deterministic factorial primality test.

  
Factorial Digits
Number of decimal digits of 10n!

  
Calculator
Calculate n! for n up to 9.999.999.999 .

  
RPN-Factorial
The retro-factorial page!

  
Permutations
Awesome! Permutation trees, the combinatorics of n!.

  
Perm. trees
Download a pdf-poster
with 120 permutation trees!

Gamma
LogGamma
Plots of the factorial (gamma) function.

  
External links
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. 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
Variants ofVariations
Eulerian Polynomials
vonStaudt Primes
Irregular Primes
Generalized Binomial

Bernoulli Manifesto
BernoulliFunction
Partitions Stirling
Zeta Polynomials
Perfect Rulers
Clausen Numbers

Hadamard Gamma
History Factorial
Permutation Trees
Swiss Knife
Swinging Factorial
Worpitzky Triangle

The computation of the factorial function, n!, has several distinct algorithmic approaches, each presenting different trade-offs concerning speed, simplicity, and the handling of large numbers. Among the methods known, the SplitRecursive algorithm is highlighted as simple and fast without requiring the use of prime factorization. Conversely, the PrimeSwing algorithm is presented as the asymptotically fastest method known for computing n!, achieved by basing the computation on the prime factorization of 'Swing Numbers'. Another contrasting method is Moessner's ingenious approach, which computes the factorial using only additions, although this method is noted to be slow in practice. Furthermore, the Poor Man's algorithm is described as highly implementable across various programming languages without relying on external Big-Integer libraries, demonstrating fast performance even for factorials up to 10000!. To enhance performance in modern computing environments, the ParallelPrimeSwing algorithm improves upon PrimeSwing by incorporating concurrent programming methods to utilize multiple processors.

For scenarios where extreme computational performance is not the primary concern, utilizing a BigInteger library offers a practical solution. An example implementation demonstrates a recursive approach that splits the computation effectively. For handling factorials of very large numbers, BigInteger libraries are necessary, as suggested by recursive structures that manage the intermediate products. In contrast, a simple, purely recursive definition exists, which is cautioned against for practical use due to potential inefficiencies.

The efficiency of the PrimeSwing method is fundamentally linked to the prime factorization of the swing numbers, which is crucial for its implementation. The conceptual foundation of this method relies on an efficient computation of the swinging factorial, which is then linked to the prime factorization of these specific numbers. Benchmarks suggest that using these fast algorithms allows for the calculation of factorials of extremely large numbers, such as 100,000,000!, within a minute when utilizing optimized methods.

Beyond direct computation, the mathematical landscape surrounding the factorial involves connections to other advanced concepts. There are various related areas explored, such as approximation formulas, including bounds for the Gamma function ratios, and the distinction between Gamma(n) and n!. The relationship between these concepts is explored through topics like the Gamma shift, which addresses why Gamma(n) is defined as (n-1)! rather than n!, and the development of Hadamard's Gamma function. The history of the factorial also intersects with permutations, combinatorial structures like permutation trees, and concepts related to the digitals of factorials.

The study of factorials extends into deeper mathematical territory, encompassing concepts from the Bernoulli and Euler numbers, binomial coefficients, and generalizations like the combinatorial generalization of the factorial. Furthermore, connections are drawn to Stieltjes' Continued Fraction for the Gamma Function and the exploration of different prime number properties, such as irregular primes and the Primorial. The field also involves factorial primality tests and the study of factorial digits. Various resources and literature exist to explore these facets, including the notation, binary split techniques, and implementations across various languages and mathematical software systems like SageMath.