计算阶乘的快速算法

Question

我发现 FastFactorialFunctions 描述了许多计算阶乘的算法。不幸的是，这些解释很简洁，我不想通过一行又一行的源代码来理解算法背后的基本原理。

有人可以向我指出这些（或其他快速）算法的更详细描述，用于快速计算大型精确阶乘吗？

质因数分解的阶乘 (Python)< /a> 描述了素因式分解的方法，这是所有性能最佳的因式分解算法所共有的技术。它还包含一些很好的 Python 示例代码。作者链接到二进制分割的描述并引用了一篇文章算法杂志（“计算阶乘的复杂性”）看起来很有前途，如果我能得到我的动手。

Answer 1

查看 Richard Fateman 撰写的这篇论文（PDF 链接）。代码示例是用 Lisp 编写的，但无论如何，大部分秘密都归结为最大限度地减少必须执行的 bignum（任意精度整数）计算的数量。

当然，如果你不需要/没有 bignum，那就很简单了；查找表或简单的循环都可以。

编辑：如果您可以使用近似答案，则可以通过对 k = 2 ...的 log(k) 求和来直接计算阶乘的对数... n，或者使用古老的斯特林近似。您希望尽可能使用对数以避免溢出；特别是，斯特林近似的天真的应用会在很多不需要的地方溢出。

Answer 2

还有另一种方法。 此处详细介绍了此方法，该方法将乘法量减半以进行少量加法和减法。您可能想要显示的第一种方法，而显示的第二种方法如果您能理解的话，读起来很有趣。

Answer 3

使用并行化。例如，在 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 代 Intel(R) Core(TM) i7-1185G7 @ 3.00GHz

RAM 16,0 GB

64 位操作系统。

使用 Eclipse 在 Windows 11 中进行测试。

Answer 4

十多年后，我想提供一种 Python 方法，灵感来自于您对乘法 factorial(n) * n+1 感兴趣，并且基本情况是 0< /code> 和 1 其结果为 1，那么：

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 秒，我希望它可以为文档和即将到来的查看者提供服务！

诗。同样的想法对于计算斐波那契很有用，斐波那契是求和而不是乘法。