Introduction to Programming (CPSC 124)
—Hobart & William Smith Colleges, Spring 2015
Project #2
Home | Syllabus | Calendar | Class Notes | Labs and Projects | General Notes

Due by 12:19 pm on Friday, February 20


Summary and Goals

This assignment consists of several working programs, which you are to study, modify, analyze, and test. There are a number of short answer problems which ask you to describe your results. Finally, there are three small programming problems at the end, to give you some additional practice both with loops and method definitions and with the ideas you'll study here.

There are three levels of achievement, depending on the number of problems you successfully complete:

The assignment's primary goal is to reinforce your skills in both analysis of loops and the construction of loops to solve new problems. Along the way, it introduces a number of topics that touch on more advanced areas of computer science: overflow, control of error in intermediate computations, and algorithmic complexity.

Background

The library function Math.exp(x) computes the value ex, where e = 2.718281828 ... is the base of the natural logarithm (link, for the curious). From the calculus, we know that this value is equal to the infinite Taylor series

If Taylor series are unfamiliar to you, don't worry. The idea is the same one underlying the piApprox problem from class exercises: you're given a pattern for a series of additions, and if you could carry out the series far enough (infinitely), you would get a value exactly equal to ex. Like the problem, we can use this series to write a program that gives an approximation of the true value. Given the values of x (a double value) and integer n, we can approximate ex by computing n terms of the Taylor series. We do this with a loop that runs n times, at each iteration computing the ith term of the series

For most of the problems in this assignment, we are going to use three versions of a program that computes the exp function. Here's version #1:

public class Exp1 {
    public static void main(String[] args) {
        double x = Double.parseDouble(args[0]) ;
        int n = Integer.parseInt(args[1]) ;
        
        double eX = 1.0;  // This will store our answer
        
        int i = 1; // counter variable, used to run the outer loop n times        
        while (i <= n) {   // counting n times, starting from 1
            ///////////////////////
            // Compute the numerator of the ith term (i.e. x^i):
            double num = 1.0; // this stores the numerator for the current term
            
            int j = 1; // counter variable for the inner loops
            
            while (j <= i) {   // counting i times, starting from 1
                num = num * x;
                j = j + 1;
            } // while
            
            // After the loop finishes, num == x^i
            
            ///////////////////////
            // Now compute the denominator (i.e. i!):
            int denom = 1; // this stores the denominator for the current term
            
            j = 1; // reusing the counter variable, since we don't need the old value
            while (j <= i) {   // counting i times, starting from 1
                denom = denom * j;
                j = j + 1;
            } // while
            // denom == i!
            
            ///////////////////////
            // Compute the ith term of the series
            double term = num / denom;
            
            // Add the ith term to the answer
            eX = eX + term;
            
            i = i + 1;
        } // outer while loop
        
        System.out.println(eX);
    }
}

Version #2:

public class Exp2 {
    public static void main(String[] args) {
        double x = Double.parseDouble(args[0]) ;
        int n = Integer.parseInt(args[1]) ;
        
        double eX = 1.0;  // This will store our answer
        
        int i = 1;  // counter variable for the outer loop
        while (i <= n) {  
            // Compute the ith term of the series
            double term = 1.0;             
            int j = 1; // counter variable for the inner loop
            while (j <= i) {
                term = term * (x / j);
                j = j + 1;
            }

            // Add the ith term to the answer:
            eX = eX + term;
            
            i = i + 1;
        } // outer while loop
        
        System.out.println(eX);
    }
}

and Version #3:

public class Exp3 {
    public static void main(String[] args) {
        double x = Double.parseDouble(args[0]) ;
        int n = Integer.parseInt(args[1]) ;
        
        double eX = 1.0;  // This will store our answer
        double term = 1.0;   // This will store the current term to add to eX
        
        int i = 1;  // counter variable
        while (i <= n) {  
            // Compute the ith term of the series, and add it to the answer:    
            term = term * (x / i);
            eX = eX + term;
            
            i = i + 1;
        } // while loop
        
        System.out.println(eX);
    }
}
java Exp1 x n

(or "Exp2", "Exp3") and each program will print an approximation of the value ex, as computed from the first n terms of the series.

Save each file, and try running each one with the following values

java Exp1 1.0 5
java Exp2 1.0 5
java Exp3 1.0 5

You can check the quality of the results by comparing them to

Math.exp(1.0)

(Try modifying each program to print this additional value at the end.)

You'll see that the results are close, but not nearly close enough. You need more terms from the series (a larger value for n) to improve the results.

Your Job

Problems 1 - 3

  1. For the Exp2 and Exp3 programs, what is the smallest value of n that is necessary to match the result from the Math library?

  2. Note that, in the case of Exp1, you won't be able to find this value. In fact, above a certain n value, you'll get a nonsensical answer. What is this value, and what is the smallest value of n value where it occurs?

  3. Though other values of n below the "obvious nonsense" threshold produce results that seem reasonable, most of them are actually wrong, too. As you increase n, you should see the result getting closer and closer to the exact value. However, the approximation should always be less than the actual value (because we're always adding terms in this series). What is the smallest value of n for which the result becomes worse?


Problems 4 - 6

The reason that Exp1 works for small values of n but fails otherwise is integer overflow: values that are too large to represent accurately as an int or double. You saw this in the observed results of Problem #5 of Lab 4 (where the program very quickly prints 0 for every value, forever). In the next few problems, we'll explore the idea more deeply. The issue is that in computing the series terms, the intermediate num and denom values grow very large, very quickly, leading to bad values for the terms.

Above a certain value of n, the Exp1 program cannot give accurate results for any value of x. To find out this value precisely, let's see how quickly the value of denom becomes useless (that's the value used to store i!).

Your job:

  1. Write a program that takes a single integer argument, x, and prints the first x values of n!, in a nicely formatted table:

    
    n        n!
    -------------------------------------
    0        1
    1        1
    2        2
    3        6
    4        24
    5        120
    6        720
    7        5040
    8        40320
    9        362880
    10       3628800
    
    (etc.)
    

    Use this program to print out the first 30 values of n!

    (Tip: You can control the horizontal placement of elements on a line by inserting the special "tab" character, '\t'. Try, for example,

    System.out.println("Box 1\tBox 2");
    System.out.println("..3\t4");
    System.out.println("5\t..6");
    

    )

  2. Look at the table your program prints: What is the largest value of n for which the answer is accurate?

  3. Java has another integer type, long, which is similar to int, but with a much larger range of possible values. Suppose we modified Exp1 so that we declared denom as a long. Would it help? What is the largest value of n for which the modified program will give accurate results? To answer this, make a second version of your factorial table program, using long instead of int, and argue your results as in the previous problem.


Problems 7-8

The Exp2 program reduces this risk of overflow using the observation that for every term of the series, the denominator and the exponent in the numerator are the same. In particular, we can use the identity


which means that if we keep track of the value used to build the ith term after (j - 1) iterations of the inner loop, we can just multiply that by (x / j), repeating the step i times to get the ith term of the series.

This eliminates the overflow problem, but still leaves us with the second shortcoming of the original method: the inner loop wastes computing time by computing values we already know!

To see why this is, note that both xn and n! can be computed from (respectively) xn-1 and (n-1)!:

This means that we can eliminate the inner loop entirely, by reusing the previously computed value of term, and that is the insight behind the Exp3 program.

Your job

How much difference does this make in the method's efficiency? A common way to answer this is to measure the number of times the "main operations" execute. A good candidate here is the multiplication used to compute the value of term, which executes once for every time its nearest enclosing loop runs.

  1. Add code to both the Exp2 and Exp3 programs, which can be used to measure the number of times that the statement

    term = term * (x / i);

    executes. For Exp3.java, this is very easy, since there's already a variable tracking this value. For Exp2, I suggest declaring another counter variable before the beginning of any loops, adding a statement to increment this counter every time the multiplication of term happens, and printing the final counter value at the end of the program, along with the value of eX. (Note: this approach is essentially a second accumulator pattern)

  2. For each program, determine the number of multiplications that occur for the following values of n: 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000. Explain, in a sentence or two, why you are seeing these results.


Problems 9 - 10

What value should we pick for n? That depends on how long it takes to get a good approximation of ex, which, in turn, depends on x. Better to just let the loop run until we have an answer that's "good enough". The usual approach to this is to check that we can still make meaningful improvement on the result (eX) by running the loop another time: that is, as long as eX &neq; eX+term. This is similar to the indefinite form we used in the square root example from class.

Your job

  1. Modify the Exp3 program so that the while loop uses this indefinite form. However, instead of the "eX != eX+term" test, use the approach we studied in class for testing equality of double values:

    Math.abs(eX - (eX + term)) > EPSILON

    For EPSILON, use the value 0.000000000000001.

  2. Save this as the source file Exp4.java.

  3. Add code to Exp4 to determine how many times the while loop will run with the following values of x: 0.001, 1.00001, 3.1415928, 10, 20. (This is trivial, once you've solved Problem 7.)


Problems 11 - 12

  1. Write a program, Sin.java, which takes a single argument, x, assumed to be given in degrees. The program should print the sine of x.

  2. Write a program, Cos.java, which takes a single argument, x, assumed to be given in degrees. The method should print the cosine of x.

To compute these values, you'll need to convert them to radians first. Then use the Taylor series expansions

And finally, ...

  1. Make your own math library class, μMath, and save it in a file named uMath.java. This library should have the following methods: sqrt(), exp, sin, and cos. Add implementations of toRadians() and toDegrees(), if you like. The signatures and contracts should match those of the standard Math library methods (in particular, sin and cos should expect their arguments in radians, not degrees).


Turn in:

Summary of Expectations

Turn in (READ ME):

Turn in a paper copy of your short answers and all accompanying source code that you have written or modified. Since these are all short programs, you are encouraged to save paper by including more than one source file on a single sheet of paper. For programs that you have merely modified, indicate the changes clearly.

Submit an electronic copy of the final version of your programs (the factorial test program(s), the modified Exp2.java and Exp3.java, Sin.java, Cos.java, Exp4.java, and uMath.java) in a folder named hw2. Remember to copy this to your turn in folder:

/classes/cs124/<your last name>/hw2/

Also, please respect my file name requests. I ask for precise names because it makes it easier for me to test your work. Thanks.

Acknowledgement

The core of this assignment, including the three versions of Exp and the sin and cosine problems, were taken from an example problem in Introduction to Programming in Java: An Interdisciplinary Approach, by Robert Sedgewick and kevin Wayne.

John H. E. Lasseter