Lab04, CISC181 (honors), Spring 2006
The Factorial Function

Welcome

Lab04 has two parts.

Part 1 involves writing three functions to compute the factorial in different ways, using iteration, recursion, and a closed formula approximation. A simple program will be written to test the three functions for accuracy, and to test the quality of the approximation.

Part 2 involves using a StopWatch class to time how long it takes to do each of the three versions. The StopWatch class is provided for you; all you have to do is compile it and link it in with your program.

Part 1: Iteration, Recursion, and Approximation

In this part, you will write multiple versions of the factorial function, which is defined as:

f(n) = n! = n * (n-1) * (n-2) * ... * 2 * 1

f(0) is defined to be 1. For values of n less than zero, the function is undefined. Your program should print an error message to cerr and exit with a value of -1 whenever the user inputs a negative value for n. However, your functions themselves should not perform any error checking. We are writing these functions to be as fast as possible, and error checking takes time, so your functions should simply assume that the input will be a non-negative integer. Be sure to specify this in the comments above your functions; it is the responsibility of whoever calls these functions to make sure the input is valid.

Although the factorial is an integer function (n must be an integer, and the result is always an integer), the approximation we are going to use will only work for floating-point types. Later, we are going to compare how fast these three functions are, so it is important that they all work on the same types. Therefore, all three functions must take an return floating point types.

Moreover, we will want to switch between using the different floating point types later on in the lab. One way to do this is with a typedef statement. A typedef basically tells the compiler to make a new type name (like int, double, float, char) that you make up, and whenever it sees that type, to replace it with the type you give it. So you should put a line at the top of your code of the form:

typedef double factType;

This will tell the compiler to treat any variables of the type factType as double. This will come in handy when we want to change to flost or another type; we will just have to change one line of code - the typedef - rather than search through for every instance of double.

You will write three functions for this part, each of which computes the factorial in a different way. Each of these functions will take and return a variable of type factType. Put these functions in a file called fact1.cc

Recursive function for n!. This function should take one variable of type factType and return that number's factorial (also of type factType). You learned about recursive functions in class recently. This function should call itself. The base case will be when n=0.

Iterative function for n!. This function will also take and return a variable of type factType. However, the iterative version will use a while or for loop to compute the factorial, rather than recursion.

James Stirling was a Scottish mathematician who lived from 1692-1770. He helped discover a good closed formula approximation for n!, which has come to be known as Stirling's formula. As modified by Gosper, it is:

You will write a function which takes and returns a variable of type factType and approximates the factorial by Stirling's formula. For this function, you will need to include the math library with the line
#include <cmath>
so that you can use the functions sqrt and pow. Also useful to you will be the predefined constants for e and π, which are M_E and M_PI, respectively.

IMPORTANT: We are going to be getting very large values of the factorial function. For all computer numeric types (e.g. float, double, int), there is an absolute limit to how large a number can be stored in the type. In your definitions, be sure that, if the value of n! is possible to be stored in the given type, then your function returns a valid number. That is, be sure that no intermediate value computed in your functions is greater than the final value of n!.

So that's just 3 functions. Fortunately, each of them is really short; just a few lines of code. Give them appropriate names, such as factorialRecursive(), factorialStirling(), etc.

Once you've written these functions, your task is to write a main function which does all of the following:

Prompt for and input a number from the user to use for n
Check to make sure that n is a non-negative integer. If it is not, print an error message to cerr and exit with a value of -1.
Compute n! three times, using each of the functions you have written, and save the results into three variables.
Because of limitations in the way doubles are stored, after a certain point, n! will be too large to store all the digits in a double, so the values will be truncated. This is OK, but you want to tell the user when it happens. The easiest way to do this is to add one to the number. If the number does not change, then you have overflowed the double type. This might look like:
factType x; //compute n!, save to x if( x == (x+1) ) { //Print out a message to the user }
However, the values returned are still useful as approximations, so do not have the program terminate in this case.
Print out all three values to cout, labeling them according to their computation methods.
Check to make sure that the values returned from the iterative and recursive functions are the same. Then compute the relative error in Stirling's approximation according to the following formula:
relative error = |actual - approximate| / actual
(where actual is the value returned from the iterative or recursive versions and approximate is the value returned from Stirling's formula). You will need to use the math library function fabs to compute the absolute value of the numerator.
Print out the relative error to cout.

Now produce a script file called lab04p1.txt in which you cat your source, compile your fact1.cc program and run it a few times, giving different values for n. Be sure to use type double in your typedef statement for this part. Run this version of your program to show the relative error when n = 5, 10, 50, 100, and 200.

Part Two: timing functions with a StopWatch class

Now, for each of your three functions, you are going to determine how long it takes (in terms of CPU time) to call that function a large number of times. First, since you will be modifying your program from part 1, make a copy of your work so far. Use the command

cp fact1.cc fact2.cc

to make the copy. Now you can work on fact2.cc and the original file will remain unmodified.

You will be using a StopWatch class, written by P. Conrad, which is available in the two files StopWatch.h and StopWatch.c, at the following link.

http://www.udel.edu/CIS/181h/pconrad/06S/ta/lab04/

You'll need to copy those two files into the directory where you are working. An example of how to use these files is also included, in the file timeFib.cc.

Essentially, to determine how long something takes to run, you need to do the following:

Put #include "StopWatch.h" at the top of your program.
Put the StopWatch.h file in your directory along with your program.
Declare a variable inside your main as "StopWatch s".
Use the notation "s.start()" or "s.stop()" or "s.readValue()" etc. as shown in the example code to use the StopWatch variable.
When you go to compile, you must first compile the two source code files with the "-c" switch, creating two object files (with extension ".o"), and then link them together to make an executable, as follows:
CC -c StopWatch.cc CC -c TimeFib.cc CC StopWatch.o TimeFib.o -o TimeFib
This last line links the two object files into an executable called "TimeFib". You can also do the same exact thing with g++. However, just for this lab, so that we all get the same values for timings, I ask that you all use the CC compiler. When you compile your program, obviously you will need to use "fact2.cc" instead of "TimeFib.cc".

Now, you need to rewrite/modify your main function. You need to input two values from the user: the number n to calculate the factorial of (as before), AND a number count specifying the number of times to loop for the timings. Then, you need to call each of the three versions of the functions on n the specified number of times, recording the time it takes for each function. See the TimeFib.cc file for help on how to do this.

For this part, you do not have to worry about relative error or checking to see that the values match. In fact, you don't even need to save the values at all. However, since we are performing timings, you need to be certain that the portions of your code that are being timed for each function are exactly the same (except for the function calls themselves).

Once your program works, compile three different versions of it into the executables factFloat, factDouble, and factLongDouble, changing the type in your typedef statement to float, double, and long double, for each version. (long double is a special floating point type that is not available on all machines. Numbers stored in ints or floats use 32 bits, and number stored in doubles use 64 (hence the name). But numbers stored in long doubles use a whopping 128 bits, for maximum accuracy!)

Now you need to do some investigation. For each of the three programs you made, find which versions of the factorial function perform best for different values of n. For example, "when the type is float, the Stirling is best for n≤5, the recursive is best for 6≤n≤21, and the iterative is best for n>21". (Note: the preceding is highly unlikely to be true.) For your investigation, choose values of the count variable for each n that give you times between 50 and 500 milliseconds. If your values are all less than 50, they are not very precise, and if any of them are much more than 500, then you are probably using up too much CPU time.

Put your findings in a file called factFindings.txt. Note that for the long double version, you should more or less ignore the Stirling function, since this relies on functions from the math library which only work on doubles, not long doubles (note that these functions will still be fine for floats - why?). However, for the long double version, you should get some very surprising results between the iterative and recursive versions. See if you can make any explanation.

To turn in, make a script file called lab04p2.txt in which you cat your source file, fact2.cc (with any typedef statement) and the factFindings.txt file. Then perform a few runs of each of the three compiled programs to support your findings. Note that you do NOT have to compile anything in this script file.

What to turn in

On WebCT:

lab04p1.txt
fact1.cc
lab04p2.txt
fact2.cc
factFindings.txt

On paper:

lab04p1.txt
lab04p2.txt

Grading for Lab 04