This lab concerns loop writing. The lab consists of five separate exercises, each of which presents a loop-based technique for computing π. Each exercise is completely self contained. There are more problems here than most students should be able to complete in the two hour lab period, so you should view the problems you don't get done in lab as homework. All five of these problems are due as homework to be turned in on Friday.
Imagine a square dart board with side length two. A circle of radius one is drawn in the middle of the board. Suppose we throw darts at the board, and the darts hit completely at random. Most of the darts will land inside the circle, although some will not. If the darts indeed land at random and we throw a large number of them, the ratio of the number of darts that land in the circle to the number of darts that we throw should approach the ratio (area of the circle)/(area of the dart board) = π/4. In other words,
4 * numberInCircle / numberTotal
should end up being about π.
Write a program that generates a large number of dart locations at random and counts how many of the darts land in the circle. Use that to compute the ratio described above.
To generate a random floating point numbers in the range -1 to 1, you will use the code
x = 2.0*Math.random() - 1.0;
The Math.random() function returns a random real number in the range from 0.0 to 1.0, so we have to adjust the value returned slightly to produce a number that falls in the desired range.
To determine whether or not a dart lands in the circle, use the test
if(Math.sqrt(x*x + y*y) <= 1.0) // Lands in the circle
The structure of the loop you will write for this exercise is
Repeat for N points Compute the coordinates of the point Determine whether or not the point lands in the circle Count the point if it does
Throughout the history of Mathematics there have been a great many attempts to compute π. Many of the formulas for π have a regular, repetitive structure that makes it easy to compute them with loops. The first such formula known was Vieta's formula:
The Vieta formula is in the form of a product, which lends itself well to implementation by a while or for loop. The idea is that each time through the loop we compute a new term for the product and multiply it by the existing product. Note also that in this example each new term is computed in a simple way from the term that came before it.
Write a program which uses the Vieta formula to compute π.
The structure of the loop you will write for this exercise is
Repeat N times Compute the value of a new term based on the previous term The new product is the old product times the new term.
The mathematician Leibniz developed this formula as a by-product of his work in the development of calculus:
If you have had Math 150, you have seen this formula before: it comes from the power series expansion for the arctan function:
Write a program which uses the Leibniz formula to compute π.
This example differs from the previous example in the way that each individual term in the sum is computed. This time around, it makes more sense to figure out a way to compute the value of the term from the loop index. Can you see what the connection is between the indices 1,2,3, etc. and the corresponding terms 1, 1/3, 1/5, etc.? Can you also find a simple way to create the alternating plus/minus behavior that the sum demands?
The structure of the loop you will write for this exercise is
Repeat N times Compute the value of a new term based on the value of the loop index Add or subtract the new term from the sum to get a new sum.
Yet another formula for π is due to the English mathematician Wallis:
This example presents a greater challenge in loop writing in that the pattern used to generate the individual terms is more complex. Can you find a way to generate the pattern?
If we draw a circle of radius one, we know that its area will be π. If we cut that circle in half, the resulting figure will have an area of π/2. If we could compute that area by some means, we would have another method for estimating π. For this exercise, we are going to use one such area computing method, called the trapezoid rule, to compute the area of the semicircle. That calculation will give us an estimate for π/2, and hence yet another way to estimate π.
The trapezoid rule works like this. Take the interval from -1 to 1 and cut it up into N segments of equal length. Over each segment place a trapezoid that just fits under the circle.
The picture shows a typical subinterval and the trapezoid sitting over the subinterval. Note that the trapezoid does a pretty good job approximating the shape of the circle over that subinterval. As we make the subintervals smaller, the approximation gets even better.
The area of a given trapezoid is given by
width*(height1 + height2)/2
where width = 2.0/N is the width of the segment the trapezoid sits over and height1 and height2 are the heights of the left and right sides of the trapezoid. If we know the x positions of the left and right sides of a trapezoid, we can compute the two heights via the formulas
height1 = Math.sqrt(1.0 - x1*x1); height2 = Math.sqrt(1.0 - x2*x2);
To compute the total area, we simply have to write a loop that steps over each of the N subintervals. Each time through the loop we compute x1 and x2 use those values to compute the area of the trapezoid via the formulas shown here. The loop adds up the areas of the trapezoids. For large N, the total area of the trapezoids should come out very close to π/2.