CompSci 6- Classwork 7 - Feb 4, 2010
10 pts

Today's classwork focuses on computing estimates of values using Newton's method and Monte Carlo Simulation.

You will work with your group, but each of you will use a laptop and solve all the problems. You should discuss problems with your group and help each other debug. Snarf the classwork/07_estimation_cps006_spring10 project.

Your project should have a src directory that contains the Sqrt and Needle classes.

Most assignments will include code to get you started. This code may consist of completed classes that you will utilize but not modify or classes in which some methods have been completed and others are left for you to fill in.

In either case, TODO comments indicate which sections of the code you may edit. You can go to these sections directly by using the Tasks view within Eclipse (click on Window, then Show View, then Task).

Estimating Square Roots

You will use a classic iterative technique that dates back to Heron of Alexandria in the first century. It is a special case of the more general Newton-Raphson method. To compute the square root of a positive number c: Start with an estimate t = c. If t is equal to c/t (up to machine precision), then t is equal to a square root of c, so the computation is complete. If not, refine the estimate by replacing t with the average of t and c/t. Each time we perform this update, we get closer to the desired answer. Your program should keep computing t until t*t is within some small value epsilon of the true c.

TIP: In Eclipse, if you get an infinite loop, you can stop the running of the program in the console window, by clicking on the red square.

1. What kind of loop does the above description imply, a loop for some set number of repetitions or a loop that should continue while some condition is true? Give either the appropriate number of repetitions or continuation condition.

2. Complete the estimate method in Sqrt.
3. Add code in your main method to print out the estimate of the square root of c with a tolerance of EPSILON
4. Add code in the estimate method to print out the number of the iteration and the current value of t each time in the loop. The additional output should look something like:

                1: t = 64.5
                2: t = 33.242248062015506
                3: t = 18.546384918316097
                ...
                8: t = 11.31370849898476
   

5. What parameter to the estimate method most directly affects the time it takes to run? (Put the answer to this question and all questions in your README file)

Estimating Pi

In a simulation you generate random events and evaluate their outcomes. The Buffon needle experiment was devised by Comte Georges - Louis Leclerc de Buffon (1707–1788), a French naturalist. On each try, a one - inch long needle is dropped onto paper that is ruled with lines 2 inches apart. If the needle drops onto a line, count it as a hit. (See Figure 6-3.) Buffon conjectured that the quotient tries/hits approximates π.

Dropping a needle repeatedly on a piece of paper is a rather tedious and not particularly precise operation. Using the java.util.Random class, one can generate pseudo-random numbers. You can use these numbers to determine where the simulated needle falls on the simulated paper.

When throwing a needle, however, there are many possible outcomes. You must generate two random numbers: one to describe the starting position (one end of the needle) and one to describe the angle of the needle with the x - axis. Then you need to test whether the needle touches a grid line. Stop after 10,000 tries.