Arithmetic Functions: Factorials

00:00 In this lesson, we’ll begin our exploration of the arithmetic functions in the math module. In particular, we’ll take a look at an example involving the factorial function.

00:11 The math module defines many number-theoretic type functions and a few classification-type functions. There are a few functions that have to do with rounding, and these are ceil(), floor(), and truncation, or trunc().

00:25 And then there are a few for combinatorial computations. These are factorial(), perm(), and comb(). And then there are some classification-type functions, so these all return a Boolean. And then there are functions that are reducers, so these are functions that take either an iterable as an argument or a variable number of arguments and then produce a single value.

00:45 Definitely take a look at the online documentation for the math module so you can see what all the other functions are and some examples.

00:55 Now, I wanted to show you an example as to why you would want to use some of the functions in the math module instead of, say, building your own functions, and I wanted to do this using the factorial() function.

01:07 You may remember from, say, high school math, that n factorial where n is a positive integer is the product of the first integers from 1 through n.

01:18 Now here, n is supposed to be a positive integer. However, for convenience, we define 0 factorial to equal 1. Here are some examples of computing a factorial. So, 3 factorial, 1 times 2 times 3, that’s 6.

01:34 And here’s 6 factorial. And notice that these are nested. There’s factorials within factorials, so 6 factorial contains 3 factorial, 1 times 2 times 3. It also contains 4 factorial, and it also contains 5 factorial.

01:51 So a way to think about computing 6 factorial is to compute 5 factorial and then multiply it times 6. We’ll take advantage of this when we write our own implementation using recursion of the factorial function so that we can compare it with the factorial() function in the math module. All right, let’s take a look at this.

02:14 Now, go ahead and try some computations with the factorial() function. Go ahead and compute, say, the factorial of 6. You saw that this should be 720.

02:25 You also saw that factorials are nested, so the factorial of 6 can be computed by first computing the factorial of 5, and then multiplying that by 6.

02:41 Let’s compare the implementation of the factorial() function with some natural ways that you would write your own version of the factorial() function.

02:51 Computing n factorial involves multiplying the integers from 1 through n, and so maybe a way that you’re already thinking about writing a factorial function is to use a for loop.

03:03 Here’s an example of using a for loop to implement a factorial function. The code for this function is provided underneath the description of the lesson.

03:13 You first want to do some error checking, just to make sure the number entered is positive and it’s an integer, and then if it’s 0, you want to return 1, and then initialize a output variable to 1, run a for loop that multiplies the factorial times k, and then you want to return factorial. Go ahead and run that.

03:37 Here’s a version using recursion. We do the same error checking, we return 1 if the input is 0, and then you saw that if you want to compute the factorial of num, you can compute it by first computing the factorial of num - 1 and then multiplying by num. So here we’re using recursion, we are calling the same function within the function, and so that’s the main idea of recursion. Go ahead and run that.

04:06 What we want to do is we want to compare those two functions with the built-in factorial() function in the math module. Let’s quickly make sure that we wrote those functions correctly.

04:21 Okay, so you get the same answer with one test case. You declare that these functions are ready to be shipped, and so now let’s just test them for computational speed.

04:32 To compare the functions, we’re going to use the timeit module, so go ahead and import timeit, and timeit has a function called timeit() Let’s take a look at the help() documentation for that so we can quickly find out how to use this.

04:49 The timeit() function is going to take in a statement—that’s the code that we want to execute—and the number of times that this code will execute is a million times.

04:57 That’s the default value. We can change that by passing in a value to the keyword argument number. Now, before we execute this function, we may want to run some setup code—maybe importing a module or something.

05:11 And then the other thing to take note is that if we have some variables defined in this code here, and those variables, for example, are stored in the global namespace, then we want to pass in the global namespace to this keyword argument globals.

05:27 Let’s do this real quick so you can see what I mean.

05:31 Let’s use the timeit() function for each of the three different ways to compute the factorial function that we have right now. Create a variable called with_loop, and let me bring up some code.

05:43 Here, we’re going to execute the fact_loop() function, evaluate it at the integer 10, and we need to bring in the global namespace because we define fact_loop() in the global namespace. Go ahead and run that.

06:00 Then you want to do the same thing with the recursion function.

06:07 All right, that seemed to take considerably longer. Now let’s go ahead and do the same thing but with the built-in factorial() function. So we’ll create a variable called with_factorial, and here, we need to have a setup value, and the setup value is going to be "import math".

06:25 Okay, so run that, and that seemed real fast. Now let’s take a look at the three values, so with a loop and then with recursion, and then with factorial.

06:37 With the factorial, it’s about ten times faster than the loop and significantly faster than with recursion. The main reason why the factorial() function from the math module has a much shorter execution time—and it’s going to be generally the case for a lot of the functions in the math module—is that these functions, they are thin wrappers around the corresponding math functions in the C standard library, and those functions in the C standard library—they’ve been around for a long time. They’re highly optimized, and so we reap the benefits of that in Python if we use the math module. All right, coming up next we’ll take a look at functions in the math module that round floats to integers.