The Python installation comes with its own library of functions. The factorial function math.factorial() is included with its math module. Math modules are part of the Python install code package. Math modules or functions such as factorial, square root, sine, and exponential may be used in Python programs. To use them, the import command must be used prior to the math function call, as shown in the code that follows.
import math print(math.factorial(4)) # the output is: 24 because 4 factorial is 24
The import math command incorporates math functions from the Python library during the code execution.
Factorial in Mathematics
In mathematics, the term factorial is given to a specific expression that results in the product of natural numbers in sequential order either ascending or descending. The sequence starts or ends with 1. For example, 1*2*3*4 = 24, is said to be “4 factorial” and denoted by 4! (with the exclamation mark.
Therefore, 1*2*3*4*5 is 5! which could also be written as 5*4*3*2*1. In general, for arbitrary (greater) integers n, you can write n! = n * (n-1) * (n-2) * … * 3 * 2 * 1.
Factorial numbers have many applications, especially in the field of probability and combinatorial math. Combinatorics is about counting, or ways to arrange things, or permutations. For a very simple example, how many possible ways are there for one to place 4 books on a shelf?
_4_ _3_ _2_ _1_ In the illustration on the left, there are 4 bookshelf positions.
You can place any of the four books in the first position from left to right. In the second position, you have any of the 3 books left to place there, and so on. Therefore, the total number of possible ways to arrange the books is 4! = 4*3*2*1 = 24.
It is a permutation with 4 different elements (books). In general, the number of permutations of n elements is given by n! = n*(n-1)*…*2*1.
A more practical example is a typical state lottery, where the lottery tickets have basically 6 sets of number pairs or 2-digit numbers. Each digit is composed of 10 possible numbers, namely, 0 – 9. There is a formula on which python math factorial functions could be used to calculate the odds of winning. The formula is:
where the number of permutations of n elements are taken r at a time. The numerator, n! here refers to the range of numbers used in a pair. For example, if the 2-digit numbers are picked from 1 to 40, then the result is:
So, the probability of winning this lottery is 1/3818380. This illustrates that when factorial numbers are used, one is dealing with large numbers. In addition, this case contains a denominator that brings up the importance of why 0! needs to be 1, since divisibility by zero is not allowed. Is buying lottery tickets a waste of money?
Interestingly, the combinatorial probability is covered in Discrete Math along with other topics such as graph theory, trees, cryptography, and several other areas. Discrete Math is an important set of courses that appear in the computer science curriculum. Therefore, factorial numbers are an important topic for programming. One could argue that in many software applications Discrete Math is more important for programmers to master than calculus.
Math Factorial Function Alternatives
In Python, the method math.factorial can be used to calculate factorial numbers as mentioned previously. But as usual, you can define your own factorial function to generate the same result. Examples 1 and 2 below define a factorial function. Example 1 includes a very important fact about factorial numbers, i.e., what 0! equal to. Mathematically, 0! is equal to 1 and 1! Is also equal to 1. When defining your own function, it is good practice to include this. The following code covers 0! and 1! as a conditional and returns 1 for either; whereas the iterative method in example 2 below does not cover 0!.
Factorial Alternative 1: A Recursive Approach
import math
def fcto(n):
'''Factorial called fcto is defined'''
if n==0 or n==1 :
return 1
else :
return n * fcto(n-1)
# the rest of factorial expression, n(n-1)(n-2)...3(2)(1)
print(fcto(5))
# 120In this example, line 6 is the trickiest since this is the recursive part of function fcto. The print() command in line 13 first calls the function with 5 as a parameter, so the function, fcto(5) returns 5 * fcto(4), and then fcto is called on 4, which returns 4 * fcto(3), and then fcto is called on 3, which returns 3 * fcto(2), and so on until finally, fcto(2-1) is 1, hence line 4 is executed returning 1.
Factorial Alternative 2: Iterative Approach
import math
def factorial(n):
fact = 1
for num in range(2, n+1):
fact *= num
return fact
print(factorial(4))
# 24
The factorial function is called with 4. Within the scope of the function, the variable fact = 1. And then, the for loop iteration begins with the value of 2 for num. Since in the first iteration num is 2, then 2×1 is returned. On the next iteration num = 3, so the fact variable gets assigned 2×3, so 6 gets returned. So far, 2 and 6 have been returned. This constitutes the first two factorial numbers, or 1×2 = 2, or 2! and 1x2x3 = 6, or 3!. On the next iteration num is 4, so fact gets assigned 6×4 = 24, which is 4!. This is the last iteration since the range upper limit is n + 1, or 4 + 1 = 5.
5 is not used, since the upper bound of the range command is not executed.
Math Factorial Runtime Complexities
Factorial numbers, n!, increase in value very fast as n gets larger, the product grows much faster than the fast-growing exponential functions, 10^x as an example.
A growth comparison of common functions in mathematics are generally expressed as n! >> 10^x >> x^3 >> x^2 >> lnx, where >> means much-larger-than. In computer science they teach the Big-O notation:
The point is that when you design algorithms using calculations with n!, it is good practice to do careful runtime analysis.
For this reason, how you write programs that make use of factorial functions could make a significant difference in runtime. When calculating large numbers, it is preferrable to use linear O(n) or O(log(n)) if possible. It might be even acceptable to use estimates. For example, since
equals
it is a case where O(n log(n)) could be applicable, but it is an estimate. This is called Stirling’s approximation that gives an approximate value for the factorial function. However, if the numbers involved in the algorithm are large enough, this might be an acceptable solution for reasonable runtimes.
Python is an interpreter type language – one in which compiling is not necessary. This makes python portable across operating systems and easy to use. But the price you pay for these conveniences, for example, is that these languages are computationally slower. For example, they are slower than Java or C++. This is another reason why you must be careful with the implementation of math.factorial function. Here are 3 examples that illustrate runtime differences. All 3 were discussed above. The iterative, recursive and the math.factorial runtimes for these snippets are compared here.
Example 1: Timing the Recursive approach for 30!
import math
import time
start = time.time()
def fcto(n):
if n==0 or n==1:
return 1
else:
return n*fcto(n-1)
print(fcto(30))
stop = time.time()
print("\ntime elapsed for Recursive: " + str(stop-start), "\n")
The output:
265252859812191058636308480000000 time elapsed for Recursive: 0.011820793151855469
Example 2: Timing the Iterative approach for 30!
import math
import time
start = time.time()
def factorial(n):
fact = 1
for num in range(2, n + 1):
fact *= num
return fact
print(factorial(30))
stop = time.time()
print("\ntime elapsed for iterative: " + str(stop-start), "\n")
The output:
265252859812191058636308480000000 time elapsed for iterative: 0.0
Example 3: Timing the math.factorial function for 30!
import math
import time
start = time.time()
print(math.factorial(30))
stop = time.time()
print("\ntime elapsed for math.factorial: " + str(stop-start), "\n")
Output: 265252859812191058636308480000000
time elapsed for math.factorial: 3.1948089599609375e-05The output:
265252859812191058636308480000000 time elapsed for Recursive: 0.011820793151855469
These are small programs with a simple algorithm, but they provide a sample of the differences in runtime. There is no claim here as to which program is the best, because there may have been other operating system processes on my computer running in the background at the time of the program execution. The main point is that there are time differences that can be significant with complex algorithms, hence careful analysis is called for. Although, after running these 3 programs multiple times, I found that the execution time differences between the 3 programs were consistent.