COMP790 Spring 2005
Assignment 1
Due on: Feb. 1, 2004.
Total points: 100
1. (40 pts) You are required to write a program to calculate PI using the
hit-or-miss Monte Carlo method. The hit-or-miss method is illustrated as
follows:
If you are a very poor dart player, it is easy to imagine throwing darts randomly at the above figure, and it should be apparent that of the total number of darts that hit within the square, the number of darts that hit the shaded part (circle quadrant) is proportional to the area of that part. In other words,
.
Then, it is easy to show that
As a result, the pseudo-code can be
total=(total number of throws)
x = (random#)
y = (random#)
hits=0
distance = sqrt(x*x+y*y)
if distance less than or equal to 1.0 then
hits=hits+1
....
Write the hit-or-miss Monte Carlo program in C/C++ or Fortran. Calculate PI and the error ( the absolute value of your PI - accurate PI value in 25 digits) using your program with 100, 1000, 10000, ..., 10^9 points. Plot a log-log graph of the error and the number of points.
2. (60 pts) Extend the above hit-or-miss Monte Carlo program for evaluating PI to an MPI program. The MPI program should be able to run with 1~16 processes. Plot a log-log graph of the error and the number of points. Also, calculate the computational time of evaluating 10^9 points with 1, 2, 4, 8, 16 processes and plot a log-log graph of the computational time and the number of processes.
(Hint: the random number generator function in UNIX is drand48().
Each process in the MPI program should evaluate different random numbers. Therefore, each process should have a different random number generator seed using srand48(). To implement this, each process can use its rank as the random number generator seed.)
Delivery
form
The delivery form of the assignment should be a
document with the program printout and the corresponding graphs.