Fast Factorial Algorithms

The article describes five algorithms for computing factorials, including a recursive "product tree" method and the "PrimeSwing" algorithm, which relies on the prime factorization of swinging factorials for efficiency. It notes that the factorial computation can be reduced to computing the swinging factorial. The page, authored by Peter Luschny, is listed in NIST's Dictionary of Algorithms and Data Structures and is freely available under a Creative Commons license.

There are five algorithms which everyone who wants to compute the factorial n = 1.2.3...n should know. 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 ; } 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 . 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