N !

Fastfactorialfunctions

There are five algorithms which everyone who wants to compute the factorial n! = 1.2.3...n exactly 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:
    static 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);
    }
    static 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 if n > 12.
    Link  Content
   Algorithms
 X FFF-MiniLib 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 in Java, C# and C++.
   Benchmarks
   Conclusions Which algorithm should we choose?
   Download
 X Approximations A unique collection! Approximation formulas.
   Gamma quot
   Gamma shift Why is Gamma(n)=(n-1)! and not Gamma(n)=n! ?
 X Hadamard
   History Not even Wikipedia knows this!
The early history of the factorial function.
   Notation
   Binary Split For coders only. Go to the page of the day.
   Sage / Python Implementation of the swing algorithm.
 ‼ Double Factorial
   Prime Factorial Primfakultaet ('The Primorial', in German.)
   Bibliography
 X Bernoulli &
Euler
Exotic Applications:
Inclusions for the Bernoulli and Euler numbers.
   Binomial
   Variations A combinatorial generalization of the factorial.
 X Stieltjes' CF
   al-Haytham /
Lagrange
The ignorance of some western mathematicians.
A deterministic factorial primality test.
   Factorial Digits
   Calculator Calculate n! for n up to 9.999.999.999 .
   RPN-Factorial
   Permutations Awesome! Permutation trees, the combinatorics of n!.
   Perm. trees Download a pdf-poster with 120 permutation trees!
   Gamma
LogGamma
   External links Some bookmarks.

Fast-Factorial-Functions: The Homepage of Factorial Algorithms. (C) Peter Luschny, 2000-2013. All information and all source code in this directory is free under the Creative Commons Attribution-ShareAlike 3.0 Unported License (the same license which Wikipedia uses). 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. 2013 : 370,000 visitors! Thank you!

Visit also our survey of the Bernoulli numbers on the occasion of the 300-th anniversary of the publication of
Jacob Bernoulli's Ars Conjectandi, 1713-2013.