我发现 FastFactorialFunctions 描述了多种计算阶乘的算法。不幸的是，解释很简略，我不想在理解算法的基本原理之前查看一行行的源代码。
有人能否向我指出更详细的描述这些（或其他快速）算法以计算大量精确阶乘的方法？
利用质因数分解求阶乘 (Python) 描述了使用质因数分解的方法，这是所有最佳性能阶乘算法都采用的技术。它还包含一些 Python 的示例代码。作者链接到 二进制分裂算法的描述 并引用了一篇在 Journal of Algorithms 中的文章（“关于计算阶乘的复杂度”），如果我能够得到它，那将是很有帮助的。（点击下载）
请查看Richard Fateman的这篇论文（PDF链接）。代码示例使用Lisp编写，但无论如何，减少必须执行的bignum（任意精度整数）计算是其中的关键。
如果您不需要/拥有bignum，则很简单；可以使用查找表或简单循环即可。
编辑：如果您可以使用近似答案，可以通过对k = 2 ... n求和log(k)直接计算阶乘的对数，或者使用古老的Stirling近似公式。尽可能使用对数来避免溢出；特别是，naive应用Stirling的近似公式将在许多情况下发生溢出，而这些情况是可以避免的。
使用并行化。例如，在Java中：
/*
*
*/
package programas;
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.stream.Stream;
// TODO: Auto-generated Javadoc
/**
* The Class ParalellFactorial.
*/
public class ParalellFactorial {
/**
* Adjusts a too long number to the size of the console.
*
* @param number the number to be adjusted
* @param characters the number of characters on which to break the lines
*/
// Adjust the number when it's too long
public static void adjustNumberToConsole(StringBuilder number, Integer characters) {
final var length = number.length();
if ( length > characters ) {
int startIndex = 0, endIndex = characters;
while ( startIndex < length ) {
final var portion = new StringBuilder(number.substring(startIndex, endIndex));
System.out.println(portion);
startIndex += characters;
endIndex += characters;
if ( endIndex >= length ) {
endIndex = length;
}
}
}
else {
System.out.println(number);
}
}
/**
* The main method.
*
* @param args the arguments
*/
public static void main(String[] args) {
final var keyboard = new Scanner(System.in);
BigInteger number;
ParalellFactorial paralellFactorial;
var error = false;
System.out.println("FACTORIAL OF A NUMBER");
do {
System.out.println("Enter a positive integer:");
try {
number = keyboard.nextBigInteger();
paralellFactorial = new ParalellFactorial();
final var startTime = System.nanoTime();
final var result = paralellFactorial.factorial(number);
final var endTime = System.nanoTime();
error = false;
System.out.println("Factorial of " + number + ":");
final var numberSb = new StringBuilder(result.toString());
adjustNumberToConsole(numberSb, 80);
System.out.println("Total execution time: " + (endTime - startTime) + " nanoseconds");
System.out.println("Number of digits: " + numberSb.length());
}
catch ( InputMismatchException | IllegalArgumentException e ) {
error = true;
keyboard.nextLine();
}
}
while ( error );
keyboard.close();
}
/**
* Factorial.
*
* @param n the number of which we want to calculate the factorial
*
* @return the factorial of the number
*/
public BigInteger factorial(BigInteger n) {
if ( n == null ) { throw new IllegalArgumentException("The argument cannot be null"); }
if ( n.signum() == - 1 ) {
// negative
throw new IllegalArgumentException("Argument must be a non-negative integer");
}
BigInteger result;
// For small input, iterative is faster
if ( n.compareTo(new BigInteger("9495")) <= 0 ) {
result = factorialIterative(n);
}
else {
// Stream is faster
result = Stream.iterate(BigInteger.TWO, bi -> bi.compareTo(n) <= 0, bi -> bi.add(BigInteger.ONE)).parallel()
.reduce(BigInteger.ONE, BigInteger::multiply);
}
return result;
}
/**
* Factorial iterative.
*
* @param n the number of which we want to calculate the factorial
*
* @return the factorial of the number
*/
private BigInteger factorialIterative(BigInteger n) {
if ( n == null ) { throw new IllegalArgumentException(); }
if ( n.signum() == - 1 ) {
// negative
throw new IllegalArgumentException("Argument must be a non-negative integer");
}
if ( n.equals(BigInteger.ZERO) || n.equals(BigInteger.ONE) ) { return BigInteger.ONE; }
var factorial = BigInteger.ONE;
for ( var i = new BigInteger("2"); i.compareTo(n) < 1; i = i.add(BigInteger.ONE) ) {
factorial = factorial.multiply(i);
}
return factorial;
}
}
规格：
第11代英特尔（R）Core(TM) i7-1185G7 @ 3.00GHz
RAM 16.0 GB
64位操作系统。
在Windows 11中使用Eclipse进行测试。
def fact_var(num):
a, b, i = 1,2,2 # base cases and our i counter.
while i < num: # if i is equal to num, we're done, last product will be at return.
c = a * b # start to multiply and save in c.
i+=1 # add 1 to i because we want to multiply next number with c (in the next iteration).
a, b = c, i # update variables to the next iteration.
return a * b if num > 1 else 1 # last product occurs here is num is greater than 1.
print(fact_var(100000))
计算 100,000 的阶乘在我的电脑上需要长达5秒的时间，希望这对文档和即将到来的观众有所帮助！
附注：同样的思路也可以用来计算斐波那契数列，这是一种加法而不是乘法。