Factorial Function | Old and New Standard Algorithms (no prime factorization) |
---|---|
Additive Moessner | Alfred Moessner's ingenious method uses only additions! Unfortunately, it is the slowest method. |
Additive Swing | This method uses only addition and squaring! Based on the notion of the 'swing numbers'. See: Divide, Swing and Conquer the Factorial! |
Naive Product | The 'obvious' method (or should I call it the ubiquitous stupid one?). |
Recursive Product | The most simple not naive method to calculate the factorial. Models a complete binary tree. |
Boiten Split | Discovered by Eerke Boiten by playing with transformational programming. See: Factorization of the factorial. |
Recursive Split | Is related to the Boiten algorithm like the Recursive Product to the Naive Product. |
Hyper | A beautiful simple algorithm based on a hypergeometric expansion of the factorial. See: Divide, Swing and Conquer the Factorial! |
Hyper Double | A optimized variant of the Hyper Simple algorithm which uses additionally a symmetric relation between the coefficients. See: Divide, Swing and Conquer the Factorial! |
Swing | A beautiful simple but powerful algorithm. See: Divide, Swing and Conquer the Factorial! |
Swing Double | A optimized variant of the Simple Swing algorithm. See: Divide, Swing and Conquer the Factorial! |
Swing Rational | A recursive variant of the Swing Double algorithm, which uses rational arithmetic. See: Divide, Swing and Conquer the Factorial! |
Swing Rational Double | An attempt to optimize the Swing Rational algorithm. See: Divide, Swing and Conquer the Factorial! |
Linear Difference | Based on the differences of the factorials. |
Square Difference | Based on the differences of squares. |
Recursive Square Difference |
Like the forgoing, but computed recursively. |
Advanced Algorithms (based on prime factorization) |
|
Prime Factorization Repeated Squaring |
An algorithm proposed by Peter Borwein. See: On the Complexity of Calculating Factorials. |
Prime Factorization Nested Squaring |
An algorithm proposed by Arnold Schönhage et al.. See: Fast Algorithms, BI-Wiss.-Verl., 1994, page 225. |
Prime Factorization Swing |
An algorithm proposed by Peter Luschny. See: Divide, Swing and Conquer the Factorial! (Write me to get the preprint.) |
Prime Factorization Swing-List |
A variant of the foregoing algorithm (working directly with lists of prime factors). |
Prime Factorization Swing-Cache |
A variant of the foregoing algorithm (caching primorials). |
Prime Factorization Binomial |
A simplification of an algorithm given by Ilan Vardi's 'Comp. Recreations in Mathematica', chap. 4.3, based on P. Goetgheluck, Prime divisors of binomial coefficients, Math. Comp. 51, 1988, 325-329. |
Prime Factorization Primorial Squaring |
An algorithm proposed by Bruce Leenstra. (Personal communication). |