DUE: Friday, February 26, 23:59 AOE

#### Program Description

In this assignment, you will implement a multithreaded program that performs a Monte Carlo simulation to estimate the mathematical constant $$\pi \approx 3.14\ldots$$. A conceptual description of such a procedure is described in the notes Monte Carlo Simulation. Briefly, the idea of the procedure is to generate many random sample points (i.e., pairs of numbers) lying inside a square, and return the number of samples that lie inside a disk inscribed in the square. Then $$\pi$$ can be estimated from the proportion of samples that fall in the disk.

Your program should take two parameters—the number of samples, and the number of threads—and compute an estimate of $$\pi$$ by performing the specified number of samples evenly distributed across the threads. For example, if the number samples is 1000, and the number of threads is 10, each thread should perform 1000 / 10 = 100 samples (you may assume that the number of samples is evenly divisible by the number of threads).

Specifically, your program must define a PiEstimator class that stores the number of samples and the number of threads used for its calculations. Be sure to use long for the number of samples, as this number could be larger than the maximum int value (which is a little over 2 billion). The PiEstimator class must include a public instance method double getPiEstimate() that returns the desired estimate of $$\pi$$. For example, here is a skeleton of the PiEstimator class to get you started:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Description: <describe your program here>
*
*/

public class PiEstimator {
// add any desired fields here

// constructor taking in the number of sample points, numPoints,
// and the number of threads used to compute the estimate
public PiEstimator (long numPoints, int numThreads) {
...
}

// compute the estimate of pi (improve this description!)
public double getPiEstimate () {
...
}
}



In order to make your program multithreaded, you will need to write a separate class that implements the Runnable interface. For example, you might define a class PiThread as follows in a separate file.

1
2
3
public class PiThread implements Runnable {
...
}


Each instance of PiThread can then perform a prescribed number of samples, and record the number of samples falling within a disk in an appropriate location of a shared array. See the notes on Multithreading for an example of how to define and use threads that modify a shared array.

To test your program, download and run PiTester.java, reproduced below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class PiTester {
// powers of two that are close to powers of 10
public static final long THOUSAND = 1_024;
public static final long MILLION = 1_048_576;
public static final long BILLION = 1_073_741_824;

// array of thread counts to test performance
public static final int[] THREAD_COUNTS = {1, 2, 4, 8, 16, 32, 64, 128, 256};

// the total number of samples to be collected
public static final long NUM_POINTS = BILLION;

public static void main (String[] args) {
System.out.println("Running Monte Carlo simulation with n = " + NUM_POINTS + " samples...\n");
System.out.println( "n threads | pi estimate | time (ms)\n"
+"-----------------------------------");

// start and end times of computation
long start, end;

// test
for (int n : THREAD_COUNTS) {

PiEstimator pe = new PiEstimator(NUM_POINTS, n);

start = System.nanoTime();

double est = pe.getPiEstimate();

end = System.nanoTime();

System.out.printf("%9d |     %.5f | %6d\n", n, est, (end - start) / 1_000_000);
}

System.out.println("-----------------------------------");
}
}



When I run the PiTester program on my computer, I get the following output (which takes a while to produce):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
% java PiTester
Running Monte Carlo simulation with n = 1073741824 samples...

n threads | pi estimate | time (ms)
-----------------------------------
1 |     3.14158 |   8174
2 |     3.14161 |   4690
4 |     3.14161 |   2709
8 |     3.14163 |   1735
16 |     3.14156 |   1867
32 |     3.14167 |   1938
64 |     3.14156 |   1905
128 |     3.14157 |   1907
256 |     3.14164 |   1919
-----------------------------------


Note that the third column indicates the time needed to run approximately 1 billion samples.

#### Hints and Resources

In performing the Monte Carlo simulation, each thread must compute many random samples. In single-threaded programs, you would typically generate (pseudo)random numbers using java.util.Random, and using a method such as nextDouble(). Unfortunately, java.util.Random does not play well with multithreaded programs. Instead, your program should use a “thread local” random number generator so that each thread has its own independent stream of random numbers. Thankfully, Java has a built-in thread local generator, ThreadLocalRandom (see documentation here). To use ThreadLocalRandom, you need to include it at the beginning of your program with

1


Then to get, for example, a random double, you can use

1


Note that current() is a static method that returns a ThreadLocalRandom object specific to the current thread.

#### What to Turn In

Please submit your program files to the Moodle submission site by Friday, February 26, 23:59 AOE. Be sure to submit everything your program needs to run: at minimum PiEstimator.java and PiThread.java (assuming you’ve put the PiThread class in a separate file).

As mentioned in the notes on Monte Carlo Simulation, there are many more applications of Monte Carlo simulation. For a relatively simple application, this paper describes a method for estimating Euler’s number, $$e = 2.718\ldots$$. (If you are off campus, you can access the full text by using the Amherst College proxy, or by searching for the article through the library website.)