Breaking News

Please Help Community by G+

Monte Carlo method to compute an approximation to π - CS 222 Program 2

The program

Your program will use a Monte Carlo method to compute an approximation to π. In a Monte Carlo computation a sequence of random values is generated and run through a model of a system. For our simple program the random values will be used to plot points as described below.

You will generate a random sequence of points in the unit square in the coordinate plane and see how many fall inside the unit circle. In the following figure seven of ten randomly generated points fell inside the circle.
7/10 = 0.7 then gives a (very) rough approximation to the ratio:

(area of circle segment)/(area of unit square) = π/4

Thus 0.7 is an approximation to π/4 so 4 × 0.7 = 2.8 is an approximation to π. Larger numbers of points will give better approximations.

The program will use the above method to compute approxiations to π four times: using 10 points, 100 points, 1000 points, and 1000000 points. It will report the results of each of the computations with the number of points used, the computed approximation, and the percent error. Because of the randomness in the computation you will get different approximations each time you run the program. Here you see an example running this program three times:

djn@djn-laptop:~/school$ pi
points: 10, value: 3.600000, error: 14.591559%
points: 100, value: 3.160000, error: 0.585924%
points: 1000, value: 3.100000, error: 1.323935%
points: 1000000, value: 3.141440, error: 0.004859%
djn@djn-laptop:~/school$ pi
points: 10, value: 2.800000, error: 10.873232%
points: 100, value: 3.320000, error: 5.678882%
points: 1000, value: 3.096000, error: 1.451259%
points: 1000000, value: 3.142448, error: 0.027227%
djn@djn-laptop:~/school$ pi
points: 10, value: 2.800000, error: 10.873232%
points: 100, value: 3.280000, error: 4.405643%
points: 1000, value: 3.204000, error: 1.986488%
points: 1000000, value: 3.142208, error: 0.019587%

Generating random numbers

The C standard library has a pseudo-random number generator called rand. Each call to the function rand() returns the next integer in a sequence of pseudo-random numbers. To set the beginning point in this sequence you must seed the random number generator with the srand() function. To choose a somewhat random seed read the system clock: srand(time(0)). In order to use these functions you must #include <stdlib.h>. srand() is only called once, near the beginning of the program.

rand() returns an int in the range 0 to RAND_MAX (which is defined in <stdlib.h>). Generate a random double between 0 and 1 with:


Generate a random point by generating x and y coordinates this way.


You will write a function double approximate(int points) which creates points (as above) in the unit square and counts how many of these are inside the unit circle (within distance 1 of the origin). Return the approximation to π which is 4 times the number of points inside the circle divided by the total number of points (remember to use appropriate type casts).

You will also write a function void print(int points) which calls approximate(). It will then display the the result of computing an approximation like:

points: 100, value: 3.280000, error: 4.405643%

'%' can be displayed by using "%%" in printf(). When computing the percentage error you may find double fabs(double); which computes the absolute value of a double useful. The value of π is M_PI if you #include <math.h>.
main() will seed the random number generator and print four approximations, using 10, 100, 1000, and 1000000 points.

You will not need any functions from the math library but if you do use any, and you are on a Unix system, you must tell gcc to link with the math library with the -lm switch, e.g.:

gcc -o montecarlo montecarlo.c -lm
Hassnain Jamil

Hassnain Jamil

No comments:

Post a Comment

Powered by Blogger.