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: * * @author */ 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.

 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

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

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.)