The Factorial Function

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.

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:

However, the values returned are still useful as approximations, so do not have the program terminate in this case.`factType x;`

//compute n!, save to x

if( x == (x+1) ) {

//Print out a message to the user

}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.

`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:

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".`CC -c StopWatch.cc`

CC -c TimeFib.cc

CC StopWatch.o TimeFib.o -o TimeFib

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.

On WebCT:

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

On paper:

- lab04p1.txt
- lab04p2.txt

- lab04p1.txt: 50 pts
- 5 points each for the recursive and iterative functions
- 15 points for the Stirling approximation function
- 15 points for the main function and the file as a whole
- 10 points for proper scripting, good output, etc.

- lab04p2.txt: 50pts;
- 15 points for correct main function
- 10 points for correct compilation and linking
- 15 points for good conclusions in the factFindings.txt file
- 10 points for proper scripting and justifying your conclusions