快速阶乘算法

# 快速阶乘函数 来源: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm N \!快速阶乘函数 有五种算法是所有想要计算阶乘 n\! = 1·2·3·...·n 的人都应该了解的。 - **SplitRecursive** 算法 (http://www.luschny.de/math/factorial/csharp/FactorialSplit.cs.html)，因为它简单，且是不使用质因数分解的最快算法。 - **PrimeSwing** 算法 (http://www.luschny.de/math/factorial/csharp/FactorialPrimeSwing.cs.html)，因为它是已知计算 n\! 的（渐近）最快算法。该算法基于“摇摆数”的概念，并通过这些数的*质因数分解 (http://www.luschny.de/math/factorial/csharp/PrimeSieve.cs.html)* 来计算 n\!。 - Moessner (http://www.luschny.de/math/factorial/csharp/FactorialAdditiveMoessner.cs.html) 的巧妙算法，仅使用加法！虽然实际意义不大（因为慢），但因其出人意料的解法而令人着迷。 - **Poor Man's** 算法 (http://www.luschny.de/math/factorial/csharp/FactorialPoorMans.cs.html)，无需使用大整数库，可轻松用任何计算机语言实现，甚至对高达 10000! 的计算也很快。 - **ParallelPrimeSwing** 算法 (http://www.luschny.de/math/factorial/java/FactorialParallelPrimeSwing.java.html)，即 PrimeSwing 算法，通过使用并发编程方法提高性能，从而利用多核处理器。 - 如果你不特别看重高性能，那就使用一个大整数库并采用以下代码： ```` 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); } ```` - 还有一个没人需要的算法，仅适合**头脑简单**的人： `long factorial(long n) { return n <= 1 ? 1 : n * factorial(n - 1); }` 千万别用这个！ --- PrimeSwing 计算示例： 摇摆 如该示例所示，阶乘函数的高效计算归结为摇摆阶乘 n≀ 的高效计算。关于这些数字的一些信息可参见此处 (http://www.luschny.de/math/swing/SwingingFactorial.html) 和此处 (http://oeis.org/A056040)。摇摆数的质因数分解对于实现 PrimeSwing 算法至关重要。 该算法的简明描述可在本文档 (pdf) (http://www.luschny.de/math/factorial/SwingIntro.pdf) 以及下面的 SageMath 链接（算法 5）中找到。 --- 链接内容算法 (http://www.luschny.de/math/factorial/description.html) 对 21 种计算阶乘函数 n! 的算法进行了非常简短的描述。 XJulia factorial (http://www.luschny.de/math/factorial/JuliaFactorial.html) \*NEW\* 基于摇摆阶乘的阶乘函数，摇摆阶乘又通过 Julia 中实现的质因数分解计算。 Mini Library (http://www.luschny.de/math/factorial/scala/FactorialScalaCsharp.htm) 在 Scala 和 GO 中实现的阶乘函数、二项式函数、双阶乘、摇摆数以及高效的质数筛。 Browse Code (http://www.luschny.de/math/factorial/index.html) 用 Java、C# 和 C++ 实现的各种算法。 SageMath (http://www.luschny.de/math/factorial/sagemath.html) 在 SageMath 中的实现。 LISP (http://www.luschny.de/math/factorial/LispFactorial.html) 在 Lisp 中的实现。 Benchmarks (http://www.luschny.de/math/factorial/Benchmark.html) *Benchmark 2013: Use 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 (http://www.luschny.de/math/factorial/conclusions.html) 我们应该选择哪种算法？ Download (http://www.luschny.de/math/factorial/download.html) 下载测试应用程序并自己进行基准测试。 XApproximations (http://www.luschny.de/math/factorial/approx/SimpleCases.html) 独一无二的集合！近似公式。 Gamma quot (http://www.luschny.de/math/factorial/approx/gammaquot.html) Gamma(x+1)/Gamma(x+1/2) 的界。 Gamma shift (http://www.luschny.de/math/factorial/factandgamma.html) 为什么 Gamma(n) = (n-1)! 而不是 Gamma(n) = n! ? XHadamard (http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunction.html) Hadamard 的 Gamma 函数和一个新的阶乘函数。 [\[MathJax version\]](http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunctionMJ.html) History (http://www.luschny.de/math/factorial/history.html) 连维基百科都不知道！阶乘函数的早期历史。 Notation (http://www.luschny.de/math/factorial/FactorialNotation.htm) 关于阶乘记号 n! 的论述。 Binary Split 仅供程序员参考。请访问当日页面。 Sage / Python (http://www.luschny.de/math/factorial/SwingFactorialSagePython.html) 摇摆算法的实现。 !!Double Factorial (http://www.luschny.de/math/factorial/DoubleFactorial.html) 快速双阶乘函数。 Prime Factorial (http://www.luschny.de/math/factorial/PrimeProxy.htm) 素阶乘（“Primorial”，德文）。 Bibliography (http://www.luschny.de/math/factorial/approx/bibliography.html) Gamma 函数不等式的参考文献。 XBernoulli & Euler (http://www.luschny.de/math/primes/berneulerincl.html) 奇异应用：伯努利数和欧拉数的包含关系。 Binomial (http://www.luschny.de/math/factorial/FastBinomialFunction.html) 快速二项式函数（二项式系数）。 Variations (http://www.luschny.de/math/seq/variations.html) 阶乘的组合推广。 XStieltjes' CF (http://www.luschny.de/math/factorial/approx/continuedfraction.html) 关于 Stieltjes 连分数用于 Gamma 函数。 al-Haytham / Lagrange (http://www.luschny.de/math/factorial/AlHaythamLagrangeTheorem.html) 一些西方数学家的无知。一个确定性的阶乘素性检验。 Factorial Digits (http://www.luschny.de/math/factorial/FactorialDigits.html) 10^n! 的十进制位数。 Calculator 计算 n! ，n 最多到 9,999,999,999。 RPN-Factorial (http://www.luschny.de/math/factorial/RPNFactorial.html) 复古阶乘页面。 Permutations Awesome! 排列树，n! 的组合学。 Perm. trees (http://www.luschny.de/math/factorial/combi/PermutationTrees.html) 下载一个 pdf 海报 (http://www.luschny.de/math/seq/PermutationTrees5Color.pdf) ，包含 120 棵排列树。 Gamma LogGamma (http://www.luschny.de/math/factorial/plots/LogGammaPlots.html) 阶乘（gamma）函数的图形。 External links (http://www.luschny.de/math/factorial/GammaLinks.html) 一些书签。 Fast-Factorial-Functions: **阶乘算法主页。** (C) Peter Luschny, 2000-2017. 本目录下的所有信息和所有源代码均根据 Creative Commons Attribution-ShareAlike 3.0 Unported License (http://creativecommons.org/licenses/by-sa/3.0/) 自由提供。此页面列在美国国家标准与技术研究院（NIST）网站著名的“算法与数据结构词典”中。2003年4月 / 2017年4月：800,000 访客！谢谢！ Rational Trees (http://www.luschny.de/math/seq/RationalTreesAndBinaryPartitions.html) Variants of Variations (http://www.luschny.de/math/seq/variations.html) Eulerian Polynomials (http://www.luschny.de/math/euler/EulerianPolynomials.html) vonStaudt Primes (http://www.luschny.de/math/zeta/VonStaudtPrimes.html) Irregular Primes (http://www.luschny.de/math/primes/irregular.html) Generalized Binomial (http://www.luschny.de/math/swing/divideswingandconquer/GeneralizedBinomialCoefficients.html) Bernoulli Manifesto (http://www.luschny.de/math/zeta/The-Bernoulli-Manifesto.html) Bernoulli Function (http://www.luschny.de/math/zeta/BernoulliFunctionIntroduction.html) Partitions Stirling (http://www.luschny.de/math/seq/CountingWithPartitions.html) Zeta Polynomials (http://www.luschny.de/math/seq/ZetaPolynomials.htm) Perfect Rulers (http://www.luschny.de/math/rulers/prulers.html) Clausen Numbers (http://www.luschny.de/math/zeta/ClausenNumbers.htm) Hadamard Gamma (http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunction.html) History Factorial (http://www.luschny.de/math/factorial/history.html) Permutation Trees (http://www.luschny.de/math/factorial/combi/PermutationTrees.html) Swiss Knife (http://www.luschny.de/math/seq/SwissKnifePolynomials.html) Swinging Factorial (http://www.luschny.de/math/swing/SwingingFactorial.html) Worpitzky Triangle (http://www.luschny.de/ect/Worpitzky-Triangle.html)