Understanding Factorials: Calculation Techniques and Insights
Written on
Chapter 1: Introduction to Factorials
Recall the astonishment you felt when you first encountered expressions like "5!" or "7!"—the exclamation mark symbolizing a well-defined mathematical concept.
We define the factorial of a positive integer ( n ), represented as ( n! ), as the product of all integers from 1 to ( n ). Formally, for any positive integer ( n geq 1 ), this can be expressed as:
[ n! = 1 times 2 times ldots times n ]
Additionally, it is established that ( 0! = 1 ).
For instance:
- ( 0! = 1 )
- ( 1! = 1 )
- ( 2! = 1 times 2 = 2 )
- ( 3! = 1 times 2 times 3 = 6 )
- ( 4! = 1 times 2 times 3 times 4 = 24 )
- ( 5! = 1 times 2 times 3 times 4 times 5 = 120 )
From these definitions, it becomes evident that for any positive integer ( n geq 1 ):
[ n! = n times (n-1)! ]
This recursive definition allows us to compute factorials by breaking them down into smaller problems, starting from the base case of ( 0! = 1 ).
The purpose of this article is to explore the straightforward yet profound question of how to compute the factorial of a number—an operation often taken for granted.
Note: While analyzing the runtime of algorithms focused on basic operations between numbers, we must be cautious not to oversimplify our computational model. Typically, we assume that each operation (like addition or multiplication) takes one unit of time, and the primary analysis revolves around counting the number of steps involved. This approach is particularly effective in graph algorithms where counting steps is crucial. A common model used is the Random-access Machine (RAM) model. Although this model is generally sufficient, we should not overlook the size of the numbers involved, especially in numerical algorithms like the one we are discussing.
Before delving into the running time of algorithms that compute ( n! ), let’s consider the following query:
Given a positive integer ( n geq 0 ), how many bits are necessary to represent ( n! ) in binary?
The number of bits needed to express any positive integer is determined by the logarithm base 2 of that number. Thus, the bits needed for ( n! ) can be approximated as:
[ text{bits needed} approx log n! ]
Estimating ( log n! ) reveals:
[ log n! = log (1 times 2 times ldots times n) = log 1 + log 2 + ldots + log n leq n log n ]
Furthermore, we can assert:
[ log n! geq log left(frac{n}{2}right) + log left(frac{n}{2} + 1right) + ldots + log n ]
We can show that:
[ log left(frac{n}{2}right) + log left(frac{n}{2} + 1right) + ldots + log n geq frac{n}{3} log n ]
Putting this together gives:
[ frac{n}{3} log n leq log n! leq n log n ]
This leads us to conclude that approximately ( Theta(n log n) ) bits are required to express ( n! ). Consequently, any algorithm that computes ( log n! ) will need at least ( Omega(n log n) ) time, as this is necessary just to produce the output.
Section 1.1: Analyzing Algorithm Performance
The two definitions of factorial suggest corresponding algorithms—one iterative and one recursive, both exhibiting similar performance characteristics.
For the iterative algorithm, we can outline the steps as follows:
- If ( n < 2 ), return 1.
- Initialize ( t = 1 ).
- For ( i = 2 ) to ( n ), update ( t = t times i ).
- Return ( t ).
This algorithm performs ( n - 1 ) iterations, each involving multiplication. Notably, once ( i ) surpasses ( n/2 ), ( t ) becomes sufficiently large, requiring ( Theta(n log n) ) bits for representation. Therefore, the multiplication for at least ( n/2 ) iterations will necessarily take ( Omega(n log n) ) time, with a maximum of ( O(n log^2 n) ) time if we employ the fastest multiplication methods. Thus, we can conclude that this algorithm has a runtime of at least ( Omega(n^2 log n) ).
The recursive approach can be summarized as follows:
FACTORIAL(n):
- If (n < 2), return 1.
- Return n * FACTORIAL(n-1).
This algorithm mirrors the iterative version in terms of operations and thus also has a runtime roughly around ( Theta(n^2) ), ignoring logarithmic factors.
Section 1.2: Divide-and-Conquer Approach
To improve efficiency, we can apply a divide-and-conquer strategy. The primary issue with the recursive algorithm is the significant number of multiplications involving large numbers. We can explore alternate ways of partitioning the problem to create a shallower recursion tree.
For integers ( i < j ), we define ( Pi(i, j) ) as the product of consecutive numbers from ( i ) to ( j ). Therefore, we can express:
[ n! = Pi(1, n) ]
For any integer ( t ) such that ( 1 leq t < n ), we can write:
[ Pi(1, n) = Pi(1, t) times Pi(t + 1, n) ]
Our aim is to derive a faster method for calculating ( Pi(i, j) ) for any ( i < j ). This gives rise to the following algorithm template:
CONSECUTIVE_PRODUCT(i, j):
- If (i == j), return i.
- Select an integer ( t ) from the set ( {i, i+1, ldots, j-1} ).
- Return CONSECUTIVE_PRODUCT(i, t) * CONSECUTIVE_PRODUCT(t + 1, j).
We can choose ( t ) as the midpoint:
[ t = i + frac{(j - i)}{2} ]
The encoding length of ( Pi(i, j) ) can be expressed as:
[ Pi(i, j) leq j^{(j - i + 1)} ]
This leads to a running time analysis of the recursive algorithm, which reveals that the total time complexity can be bounded by:
[ T(i, j) leq O((j - i) log (j - i) log^2 j) ]
Substituting ( i = 1 ) and ( j = n ) allows us to conclude that ( n! ) can be computed within ( O(n log^3 n) ) time. This represents a marked improvement over the quadratic running times observed with simpler algorithms.
Conclusion
This article has explored the seemingly simple task of calculating the factorial of a number. The divide-and-conquer method discussed offers a substantial improvement over naive algorithms, although it is not optimal. A more advanced algorithm by Peter B. Borwein achieves a running time of ( O(n log^2 n log log^2 n) ), which can be found through further research.
For a visual and detailed explanation of factorials, refer to the following videos:
The first video, titled "Factorials Explained!", offers a comprehensive breakdown of the factorial concept and its applications.
The second video, "Factorials Shortcuts", discusses efficient methods for calculating factorials.