CIS 1.5 Science Section
Professor Langsam
Assignment #3
One
of the simplest applications of
2 feet
Think about the ratio
Since the darts were tossed randomly at the board, we would guess that this ratio should be about the same as
So suppose
n = Number that hit the square + Number that hit the dartboard
d = Number that hit the dartboard.
Then since the area of the square is 4 square feet and the area of the circle is p square feet, we should have
Equivalently, we should have
Furthermore, as n, the total number of darts hitting the square and the dartboard, increases, the law of averages says that the approximation should get better and better.
We can use this idea to estimate _ by replacing our dartboard and dart-throwing with a random number generator. Here’s the basic idea:
in_circle_count =
0;
seed the random
number generator;
for (i = 0; i < n; i++) {
Generate
random x-coordinate in [-1,1];
Generate
random y-coordinate in [-1,1];
if ((x,y) is in the unit circle)
in_circle_count++;
}
pi_estimate =
4.0*in_circle_count/n;
The C++ cstdlib library contains a random number generator, rand(), which will generate a random number between 0 and RAND_MAX, RAND_MAX being a value defined in the library as well. Random number generators are ordinarily “seeded” to control the start of the sequence of random numbers. So if a program is supposed to generate a different sequence of random numbers every time it’s run, the program could be seeded with something like the number of seconds since midnight. A discussion of random numbers is beyond the scope of this assignment. The interested student should refer to one of the references listed in the footnotes[2],[3]
We desire a random number between [-1, 1]. The following formula will generate such a number.
x = pow(-1.0,
rand() % 2) *
rand()/(double(RAND_MAX)+1);
We can determine whether (x, y) is in the unit circle by finding out how far it is from
(0, 0), if
We can save a little bit of computational work by observing this is true, if and only if
Write a C++ program to implement the Monte Carlo Method for the Estimation of p. Your input should be the number of (x,y) pairs (“darts”). Run the program with increasingly large values of n until the value you obtain for p approaches 3.1415.
Questions:
1. How large of an n is required to approach this value?
2. How long does it take your computer to compute this value? Investigate the use of the time function in the C++ ctime library[4].
3. What are the problems with the random number generator that we have used? Investigate other method of producing random number generators.
Be sure your program is clearly documented, well structured and uses meaningful variables. Along with your program and your results, submit a brief report that discusses the above questions.