Introduction

Computing n! (n factorial) is straightforward for small values but becomes a big-integer problem rapidly — 100! has 158 digits. The naive loop multiplying 1 through n is O(n) multiplications, but each multiplication grows more expensive as the product gets larger. Faster approaches include divide-and-conquer (splitting the range to balance operand sizes), prime factorization (binary splitting on prime powers), and Stirling's approximation for floating-point estimates. For most applications, language built-ins (math.factorial in Python) already use optimized algorithms internally.

Iterative Method

1def factorial_iterative(n):
2    result = 1
3    for i in range(2, n + 1):
4        result *= i
5    return result
6
7print(factorial_iterative(20))  # 2432902008176640000

The iterative approach performs n - 1 multiplications. For large n, the intermediate result grows to thousands of digits, making later multiplications significantly slower than earlier ones (big-integer multiplication is not O(1)).

Recursive Method

1def factorial_recursive(n):
2    if n <= 1:
3        return 1
4    return n * factorial_recursive(n - 1)
5
6# Hits Python's default recursion limit at n ≈ 1000
7# import sys; sys.setrecursionlimit(10000)

Recursion has the same time complexity as iteration but adds call stack overhead. For large n, it risks RecursionError in Python or stack overflow in C/Java.

Divide and Conquer

1def factorial_dc(n):
2    """Multiply the range [1..n] by splitting in half recursively."""
3    if n <= 1:
4        return 1
5    return prod_range(2, n)
6
7def prod_range(low, high):
8    if low > high:
9        return 1
10    if low == high:
11        return low
12    mid = (low + high) // 2
13    return prod_range(low, mid) * prod_range(mid + 1, high)
14
15print(factorial_dc(100))

Splitting the range produces balanced operands for each multiplication. Two 500-digit numbers multiplied is faster than one 1000-digit number multiplied by a small number, because sub-quadratic multiplication algorithms (Karatsuba, Toom-Cook) are more efficient on equal-sized operands.

Prime Factorization (Binary Splitting)

1def factorial_prime(n):
2    """Compute n! using prime factorization."""
3    primes = sieve_of_eratosthenes(n)
4    result = 1
5    for p in primes:
6        # Count how many times p divides n!
7        power = 0
8        pk = p
9        while pk <= n:
10            power += n // pk
11            pk *= p
12        result *= p ** power
13    return result
14
15def sieve_of_eratosthenes(limit):
16    is_prime = [True] * (limit + 1)
17    is_prime[0] = is_prime[1] = False
18    for i in range(2, int(limit**0.5) + 1):
19        if is_prime[i]:
20            for j in range(i*i, limit + 1, i):
21                is_prime[j] = False
22    return [i for i in range(2, limit + 1) if is_prime[i]]
23
24print(factorial_prime(100))

Legendre's formula counts the exact power of each prime p in n!: sum of floor(n / p^k) for k = 1, 2, .... This avoids multiplying by non-prime factors entirely and can be combined with binary splitting for the final product.

Stirling's Approximation (Floating Point)

1import math
2
3def stirling(n):
4    """Approximate n! using Stirling's formula."""
5    if n == 0:
6        return 1
7    return math.sqrt(2 * math.pi * n) * (n / math.e) ** n
8
9# Comparison
10for n in [10, 20, 50, 100]:
11    exact = math.factorial(n)
12    approx = stirling(n)
13    error = abs(exact - approx) / exact * 100
14    print(f"{n}! — exact: {exact:.2e}, stirling: {approx:.2e}, error: {error:.4f}%")
15
16# 10! — error: 0.0833%
17# 100! — error: 0.0008%

Stirling's approximation is not exact but is useful for estimating the magnitude of factorials, computing log-factorials for statistical applications, and cases where floating-point precision is sufficient.

Language Built-Ins

1# Python — uses a fast C implementation internally
2import math
3result = math.factorial(1000)  # Nearly instant
4
5# Java (BigInteger)
6import java.math.BigInteger;
7BigInteger factorial = BigInteger.ONE;
8for (int i = 2; i <= 1000; i++) {
9    factorial = factorial.multiply(BigInteger.valueOf(i));
10}
11
12# C++ with __int128 or Boost
13#include <boost/multiprecision/cpp_int.hpp>
14boost::multiprecision::cpp_int factorial(int n) {
15    boost::multiprecision::cpp_int result = 1;
16    for (int i = 2; i <= n; ++i) result *= i;
17    return result;
18}

Python's math.factorial uses an optimized binary splitting algorithm in C, making it faster than any pure Python implementation. Always prefer language built-ins when available.

Memoization for Repeated Calls

1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def factorial_memo(n):
5    if n <= 1:
6        return 1
7    return n * factorial_memo(n - 1)
8
9# First call: computes 100!
10factorial_memo(100)
11
12# Subsequent calls: O(1) lookup
13factorial_memo(50)  # Already cached from computing 100!

If your application calls factorial repeatedly with different values, memoization avoids recomputation. Each call to factorial_memo(k) caches all values from 1 to k.

Common Pitfalls

• Integer overflow in typed languages: int and long overflow for n > 12 (32-bit) or n > 20 (64-bit). Use BigInteger (Java), boost::multiprecision (C++), or arbitrary-precision types.
• Recursion stack overflow: Recursive factorial hits the call stack limit at ~1000 in Python and ~10,000 in Java. Use iteration or increase the stack size.
• Unbalanced multiplication in naive loop: Multiplying a huge number by a small number is slower per digit than multiplying two medium numbers. Divide-and-conquer balances operand sizes for better performance.
• Using Stirling's for exact results: Stirling's approximation has relative error ~1/(12n). For combinatorics requiring exact integer results, use the iterative or prime factorization method.
• Not using language built-ins: Custom implementations in Python are 10-100x slower than math.factorial, which is implemented in optimized C with binary splitting.

Summary

• Iterative multiplication is the simplest: O(n) multiplications, but each grows expensive for large n
• Divide-and-conquer balances operand sizes, improving big-integer multiplication performance
• Prime factorization computes the exact prime power decomposition of n!
• Stirling's approximation gives fast floating-point estimates with ~0.08% error at n=10
• Use math.factorial (Python), BigInteger (Java), or equivalent built-ins for production code
• Memoize when computing factorials repeatedly with different arguments