Fast algorithms for computing the factorial

Question

I found FastFactorialFunctions describing a number of algorithms for computing the factorial. Unfortunately, the explanations are terse and I don't feel like sifting through line after line of source code to understand the basic principles behind the algorithms.

Can anybody point me to more detailed descriptions of these (or other fast) algorithms for computing large exact factorials fast?

Factorials with prime factorization (Python) describes the method of prime factorization, the technique common to all of the best-performing factorial algorithms. It also contains some nice example code in Python. The author links to a description of binary splitting and references an article in the Journal of Algorithms ("On the Complexity of Calculating Factorials") that looks promising, if I could only get my hands on it.

Answer 1

Check out this paper (PDF link) by Richard Fateman. The code samples are in Lisp, in but in any event, much of the secret boils down to minimizing the number of bignum (arbitrary precision integer) calculations you have to do.

Naturally, if you don't need/have bignums, it's trivial; either a lookup table or a simple loop will be fine.

EDIT: If you can use an approximate answer, you can either compute the logarithm of the factorial directly by summing log(k) for k = 2 ... n, or by using the venerable Stirling approximation. You want to work with the logarithm wherever possible to avoid overflow; in particular, a naive application of Stirling's approximation will overflow in a lot of places where it doesn't have to.

Answer 2

There is also another method. This method is detailed here that halves the amount of multiplication for a little bit of addition and subtraction. You probably want the first method shown, and the second method shown is an interesting read if you can understand it.

Answer 3

Use parallelization. For example, in 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;
  }

}

Specifications: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz

RAM 16,0 GB

64 bits operating system.

Tested in Windows 11 using Eclipse.

Answer 4

More than ten years later, I would like to provide a Python approach inspired in the fact that you're interested in multiply factorial(n) * n+1 and the base cases are 0 and 1 whose result is 1, then:

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))

For factorial of 100 000 it takes up to 5 seconds in my machine, I hope it serves for documentation and upcoming viewers!

Ps. Same idea is useful to compute fibonacci, which is a summation not a multiplication.