[ Exercises | Chapter Index | Main Index ]

## Solution for Programming Exercise 12.5

This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.

### Exercise 12.5:

It is possible to get an estimate of the mathematical constant π by using a random process. The idea is based on the fact that the area of a circle of radius 1 is equal to π, and the area of a quarter of that circle is π/4. Here is a picture of a quarter of a circle of radius 1, inside a 1-by-1 square:

The area of the whole square is one, while the area of the part inside the circle is π/4. If we choose a point in the square at random, the probability that it is inside the circle is π/4. If we choose N points in the square at random, and if C of them are inside the circle, we expect the fraction C/N of points that fall inside the circle to be about π/4. That is, we expect 4*C/N to be close to π. If N is large, we can expect 4*C/N to be a good estimate for π, and as N gets larger and larger, the estimate is likely to improve.

We can pick a random number in the square by choosing numbers x and y in the range 0 to 1 (using Math.random()). Since the equation of the circle is x*x+y*y=1, the point lies inside the circle if x*x+y*y is less than 1. One trial consists of picking x and y and testing whether x*x+y*y is less than 1. To get an estimate for π, you have to do many trials, count the trials, and count the number of trials in which x*x+y*y is less than 1,

For this exercise, you should write a GUI program that does this computation and displays the result. The computation should be done in a separate thread, and the results should be displayed periodically. The program can use JLabels to the display the results. It should set the text on the labels after running each batch of, say, one million trials. (Setting the text after each trial doesn't make sense, since millions of trials can be done in one second, and trying to change the display millions of times per second would be silly.

Your program should have a "Run"/"Pause" button that controls the computation. When the program starts, clicking "Run" will start the computation and change the text on the button to "Pause". Clicking "Pause" will cause the computation to pause. The thread that does the computation should be started at the beginning of the program, but should immediately go into the paused state until the "Run" button is pressed. Use the wait() method in the thread to make it wait until "Run" is pressed. Use the notify() method when the "Run" button is pressed to wake up the thread. Use a boolean signal variable running to control whether the computation thread is paused. (The wait() and notify() methods are covered in Subsection 12.3.4.)

Here is an applet version of my solution for you to try:

You might want to start with a version of the program with no control button. In that version, the computation thread can run continually from the time it is started. Once that is working, you can add the button and the control feature.

To get you started, here is the code from the thread in my solution that runs one batch of trials and updates the display labels:

```for (int i = 0; i < BATCH_SIZE; i++) {
double x = Math.random();
double y = Math.random();
trialCount++;
if (x*x + y*y < 1)
inCircleCount++;
}
double estimateForPi = 4 * ((double)inCircleCount / trialCount);
countLabel.setText(      " Number of Trials:   " + trialCount);
piEstimateLabel.setText( " Current Estimate:   " + estimateForPi);```

The variables trialCount and inCircleCount are of type long in order to allow the number of trials to be more than the two billion or so that would be possible with a variable of type int.

(I was going to ask you to use multiple computation threads, one for each available processor, but I ran into an issue when using the Math.random() method in several threads. This method requires synchronization, which causes serious performance problems when several threads are using it to generate large amounts of random numbers. A solution to this problem is to have each thread use its own object of type java.util.Random to generate its random numbers (see Subsection 5.3.1). My solution to this exercise discusses this problem further.)

Discussion

I will present three versions of the solution: one without a control button, one with the button and a single computation thread, and one that uses multiple threads. But first, you might be interested in how I set up the JLabels:

```countLabel =      new JLabel(" Number of Trials:   0");
piEstimateLabel = new JLabel(" Current Estimate:   (none)");
JLabel piLabel =  new JLabel(" Actual value of pi: " + Math.PI + "  ");
Font bigMonospace = new Font("Monospaced", Font.PLAIN, 20);
countLabel.setFont(bigMonospace);
piEstimateLabel.setFont(bigMonospace);
piLabel.setFont(bigMonospace);
countLabel.setOpaque(true);
piEstimateLabel.setOpaque(true);
piLabel.setOpaque(true);```

I used a monospaced font (in which all the characters are the same width) so that the characters on the three labels would line up neatly. I set the labels to be opaque to make sure that they would use their own background color rather than let the color of the panel show through.

For the first version of the program, I simply wrapped the code given in the exercise for doing one batch of trials inside an infinite while loop, and made that the run() method of the thread:

```private class ComputationThread extends Thread {
final int BATCH_SIZE = 1000000;  // Number of trials between updates of the display.
long trialCount;     // Total number of trials that have been performed.
long inCircleCount;  // Number of trials in which x*x+y*y is less than 1.
setDaemon(true);
}
public void run() {
while (true) {
for (int i = 0; i < BATCH_SIZE; i++) {
double x = Math.random();
double y = Math.random();
trialCount++;
if (x*x + y*y < 1)
inCircleCount++;
}
double estimateForPi = 4 * ((double)inCircleCount / trialCount);
countLabel.setText(      " Number of Trials:   " + trialCount);
piEstimateLabel.setText( " Current Estimate:   " + estimateForPi);
}
}
}```

The thread is created and started in the constructor of the panel. It's quite possible that several batches of trials are done before the labels ever appear on the screen. That's OK because it's OK to call a label's setText() method even before the label appears.

The first version of the program is pretty short and simple, and it's not too hard to add the control button. First of all, I added the volatile boolean variable, running to the program, and I added the following code at the beginning of the while loop in the thread to make the thread pause when the value of running is false:

```synchronized(this) {
while ( ! running ) { // wait for running to be true
try {
wait();
}
catch (InterruptedException e) {
}
}
}```

When running is false, this code calls the wait() method to go to sleep. It will require a call to notify() elsewhere in the program to wake the thread so that it can continue. Note that the synchronization is on the object "this", which refers here to the thread object. (Recall that obj.wait() must always be called in code that is synchronized on obj. In this case, this plays the role of obj because a simple call to wait() is really a call to this.wait().) A while loop is used in this code rather than an if statement to be absolutely sure that running is true before continuing.

When the thread is first started at the beginning of the program, the value of running is false. The thread sees this value and calls wait() as soon as it starts, and the thread remains in this waiting state until the user clicks the "Run" button. The actionPerformed() method that responds to the button has to set the value of running to true. It also has to call notify() to wake up the thread so it can see the new value. The notify() method must be called on the same object that the thread used to call wait() -- that is, on the thread object itself. The program has a variable named runner that refers to the thread, so the thread is woken with the code:

```synchronized(runner) {
running = true;
runner.notify();
}```

It's important, by the way, that the statement that sets running to true is inside the synchronized statement here, and that the code in the thread that tests the value of running is also inside a statement that is synchronized on the same object. This avoids a race condition: Suppose these statements are not synchronized. Then it is possible that the thread might test the value of running, find it to be false, and decide to call wait(). However, before it actually calls wait(), the event-handling thread might set running to true and call notify(). So it's possible for the notify() to come before the wait(), which means the thread will be left waiting for a notification that was already given! Proper synchronization prevents the thread from being interrupted between the time it decides to call wait() and the time it actually does so.

As I mentioned in the statement of the exercise, I actually wanted to use several computation threads -- one for each available processor. When I wrote that program, however, I was dismayed to find that it was much slower than the single-threaded program. After trying for a while to track down the reason, I eventually remembered that the call to Math.random() has to be synchronized internally (because there is a race condition in the way that the next random number in a sequence is generated). There is a significant overhead involved in synchronization, which can really slow down a program when it is done too often. In this case, when Math.random() was called millions of times per second by several different threads, the slowdown was by a factor of about 100!

Behind the scenes, Math.random() uses an object of type java.util.Random to generate the random numbers. By having each thread create and use its own object of this type, instead of calling Math.random(), I avoided the synchronization problem. (I am honestly not sure how Java avoids the overhead of a synchronized statement when there is only one thread that is synchronizing on a given object.)

Aside from that problem, the main issue introduced by using multiple threads is how to combine the results from the different threads. In the first two versions of the program, the thread keeps track of the total number of trials and the number of trials where x*x+y*y is less than 1. It uses this information to figure out what to put on the display labels. However, when there are two or more threads, the data that is needed to update the display is not available to any one thread. So, someone else has to collect the data from the threads and combine all the data to get the overall total number of trials and the overall total number of trials in which x*x+y*y<1.

There are several ways to do this. I decided to use a queue to transport the results from the computation threads to another thread that combines the results and updates the display accordingly. In fact, the role of the other thread is played by the event-handling thread. There is a timer that goes off every 1/10 of a second. The actionPerformed() method that is called in response to the timer removes all the data that have been collected in the queue and uses it to update the display.

Trials are run in batches of 1,000,000. Each batch produces one result. The result is simply the number of trials in that batch for which x*x+y*y<1. The result is an integer, so for the result queue I use a queue of Integers. Each result in the queue corresponds to 1,000,000 trials, so each time I process a result, I add 1000000 to the total number of trials and add the number from the queue to the number or trials in which x*x+y*y<1.

For the queue, I used a LinkedBlockingQueue. Since the queue is being used by several threads, I need a queue where the operations are properly synchronized. In fact, I don't need the blocking behavior of the blocking queue, but a LinkedBlockingQueue has a nice, synchronized method, drainTo(), for retrieving all the items from a queue in one step. I would have used ConcurrentLinkedQueue if it had a similar method.

I won't discuss the third version of the program further. You can see the source code, which is well commented, below.

The Solution

The first version of the program, with no control button:

```import java.awt.*;
import javax.swing.*;

/**
* This program uses a probabilistic technique to estimate the
* value of the mathematical constant pi.  The technique is to
* choose random numbers x and y in the range 0 to 1, and to
* compute x*x + y*y.  The probability that x*x + y*y is less than
* 1 is pi/4.  If many trials are performed, and the number of
* trials in which x*x+y*y is less than 1 is divided by the total
* number of trials, the result is an approximation for pi/4.
* Multiplying this by 4 gives an approximation for pi.
*
* The program shows the estimate produced by this procedure, along
* with the number of trials that have been done and, for comparison,
* the actual value of pi.  These values are shown in three JLabels.
* The computation is done by a separate thread that updates the
* contents of the labels after every millionth trial.
*
* In this version of the program, the computation thread runs
* continually from the time the program is started until it
* ends.  It is run at a reduced priority so that it does not
* interfere with the GUI thread.
*/
public class EstimatePi_1 extends JPanel {

/**
* Main program just creates a window to show the panel that
* contains the JLabels.
*/
public static void main(String[] args) {
JFrame window = new JFrame("Estimating Pi Probabilistically");
EstimatePi_1 content = new EstimatePi_1();
window.setContentPane(content);
window.pack();
window.setResizable(false);
window.setLocation( 300, 200 );
window.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
window.setVisible(true);
}

private JLabel piEstimateLabel;  // A label for showing the current estimate of pi.
private JLabel countLabel;       // A label for showing the number of trials.

/**
* Constructor creates the three display labels and adds them to this
* panel.  It also creates and starts the computation thread.
*/
public EstimatePi_1() {

setLayout(new GridLayout(0, 1, 2, 2));
setBackground(Color.BLUE);
setBorder(BorderFactory.createLineBorder(Color.BLUE,2));

countLabel =      new JLabel(" Number of Trials:   0");
piEstimateLabel = new JLabel(" Current Estimate:   (none)");
JLabel piLabel =  new JLabel(" Actual value of pi: " + Math.PI + "  ");
Font bigMonospace = new Font("Monospaced", Font.PLAIN, 20);
countLabel.setFont(bigMonospace);
piEstimateLabel.setFont(bigMonospace);
piLabel.setFont(bigMonospace);
countLabel.setOpaque(true);
piEstimateLabel.setOpaque(true);
piLabel.setOpaque(true);

runner.start();

} // end constructor

/**
*  This class defines the thread that does the computation.
*  The thread runs in an infinite loop in which it performs
*  batches of 1000000 trials and then updates the display labels.
*/
final int BATCH_SIZE = 1000000;  // Number of trials between updates of the display.
long trialCount;     // Total number of trials that have been performed.
long inCircleCount;  // Number of trials in which x*x+y*y is less than 1.
setDaemon(true);
}
public void run() {
while (true) {
for (int i = 0; i < BATCH_SIZE; i++) {
double x = Math.random();
double y = Math.random();
trialCount++;
if (x*x + y*y < 1)
inCircleCount++;
}
double estimateForPi = 4 * ((double)inCircleCount / trialCount);
countLabel.setText(      " Number of Trials:   " + trialCount);
piEstimateLabel.setText( " Current Estimate:   " + estimateForPi);
}
}
}

} // end class EstimatePi_1

```

The second version of the program, with a control button and just one thread. Significant changes from the first version are shown in red:

```import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

/**
* This program uses a probabilistic technique to estimate the
* value of the mathematical constant pi.  The technique is to
* choose random numbers x and y in the range 0 to 1, and to
* compute x*x + y*y.  The probability that x*x + y*y is less than
* 1 is pi/4.  If many trials are performed, and the number of
* trials in which x*x+y*y is less than 1 is divided by the total
* number of trials, the result is an approximation for pi/4.
* Multiplying this by 4 gives an approximation for pi.
*
* The program shows the estimate produced by this procedure, along
* with the number of trials that have been done and, for comparison,
* the actual value of pi.  These values are shown in three JLabels.
* The computation is done by a separate thread that updates the
* contents of the labels after every millionth trial.
*
* In this version of the program, there is a "Run"/"Pause" button
* that controls the computation thread.  Clicking the button once
* starts the thread; clicking it again pauses it.  Initially, the
*/
public class EstimatePi_2 extends JPanel implements ActionListener {

/**
* Main program just creates a window to show the panel that
* contains the JLabels and the Run/Pause button.
*/
public static void main(String[] args) {
JFrame window = new JFrame("Estimating Pi Probabilistically");
EstimatePi_2 content = new EstimatePi_2();
window.setContentPane(content);
window.pack();
window.setResizable(false);
window.setLocation( 300, 200 );
window.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
window.setVisible(true);
}

private JLabel piEstimateLabel;  // A label for showing the current estimate of pi.
private JLabel countLabel;       // A label for showing the number of trials.

private JButton runPauseButton;  // Button to control the thread.  Clicking this
// button will pause the thread if it is running
// and will restart it if it is paused.

private volatile boolean running;  // Control variable for signaling the thread to
// run or pause.  Initially, this is false, so
// the thread pauses as soon as it is created,
// until the user clicks the "Run" button.

/**
* Constructor creates the three display labels and adds them to this
* panel.  It adds a "Run"/"Pause" button below the labels.
* It also creates and starts the computation thread.
*/
public EstimatePi_2() {

setLayout(new GridLayout(4, 1, 2, 2));
setBackground(Color.BLUE);
setBorder(BorderFactory.createLineBorder(Color.BLUE,2));

countLabel =      new JLabel(" Number of Trials:   0");
piEstimateLabel = new JLabel(" Current Estimate:   (none)");
JLabel piLabel =  new JLabel(" Actual value of pi: " + Math.PI + " ");
Font bigMonospace = new Font("Monospaced", Font.PLAIN, 20);
countLabel.setFont(bigMonospace);
piEstimateLabel.setFont(bigMonospace);
piLabel.setFont(bigMonospace);
countLabel.setOpaque(true);
piEstimateLabel.setOpaque(true);
piLabel.setOpaque(true);

JPanel bottom = new JPanel();
runPauseButton = new JButton("Run");

runner.start();

} // end constructor

/**
* This method responds to clicks on the button, by
* toggling the value of the signal variable from true
* to false or from false to true.  The text on the
* button is changed to match the state.  When
* running is set to true, notify() is called to wake
*/
public void actionPerformed(ActionEvent evt) {
if (running) {
runPauseButton.setText("Run");
running = false;
}
else {
runPauseButton.setText("Pause");
synchronized(runner) {
running = true;
runner.notify();
}
}
}

/**
*  This class defines the thread that does the computation.
*  The thread runs in an infinite loop in which it performs
*  batches of 1000000 trials and then updates the display labels.
*  Just after it starts and between batches, the thread tests
*  the value of the signal variable, running.  If this variable
*  is false, then the thread sleeps until the value of running
*  is set to true.
*/
final int BATCH_SIZE = 1000000;  // Number of trials between updates of the display.
long trialCount;     // Total number of trials that have been performed.
long inCircleCount;  // Number of trials in which x*x+y*y is less than 1.
setDaemon(true);
}
public void run() {
while (true) {
synchronized(this) {
while ( ! running ) { // wait for running to be true
try {
wait();
}
catch (InterruptedException e) {
}
}
}
for (int i = 0; i < BATCH_SIZE; i++) {
double x = Math.random();
double y = Math.random();
trialCount++;
if (x*x + y*y < 1)
inCircleCount++;
}
double estimateForPi = 4 * ((double)inCircleCount / trialCount);
countLabel.setText(      " Number of Trials:   " + trialCount);
piEstimateLabel.setText( " Current Estimate:   " + estimateForPi);
}
}
}

}  // end class EstimatePi_2

```

The third version of the program, with a control button and multiple threads. Significant changes from the previous versions are shown in red

```import java.awt.*;
import java.awt.event.*;
import java.util.ArrayList;
import java.util.Random;
import javax.swing.*;

/**
* This program uses a probabilistic technique to estimate the
* value of the mathematical constant pi.  The technique is to
* choose random numbers x and y in the range 0 to 1, and to
* compute x*x + y*y.  The probability that x*x + y*y is less than
* 1 is pi/4.  If many trials are performed, and the number of
* trials in which x*x+y*y is less than 1 is divided by the total
* number of trials, the result is an approximation for pi/4.
* Multiplying this by 4 gives an approximation for pi.
*
* The program shows the estimate produced by this procedure, along
* with the number of trials that have been done and, for comparison,
* the actual value of pi.  These values are shown in three JLabels.
* The computation is done by several separate threads.  Periodically,
* the event-handling thread in a method called by a Timer, removes
* results from the queue and applies them to the labels every
* 1/10 second.
*
* In this version of the program, there is a "Run"/"Pause" button
* that controls the computation threads.  Clicking the button once
* starts the threads; clicking it again pauses them.  Initially, the
*/
public class EstimatePi_3 extends JPanel implements ActionListener {

public static void main(String[] args) {
JFrame window = new JFrame("Estimating Pi Probabilistically");
EstimatePi_3 content = new EstimatePi_3();
window.setContentPane(content);
window.pack();
window.setResizable(false);
window.setLocation( 300, 200 );
window.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
window.setVisible(true);
}

private final static int BATCH_SIZE = 1000000;  // This is the number of trials
// in a batch.  A computation thread runs this
// many trials in a fast for loop, without checking
// the value of running and without reporting its
// results.  After the for loop, the thread puts
// the result from that batch into the queue.  It
// then checks the value of running and will pause
// if running is false.

private long totalTrialCount;    // Total number of trials considered so far.
private long totalInCircleCount; // Number of those trials for which x*x+y*y < 1.

private JLabel piEstimateLabel;  // A label for showing the current estimate of pi.
private JLabel countLabel;       // A label for showing the number of trials.

private JButton runPauseButton;  // Button to control the threads.  Clicking this
// button will pause the threads if they are running
// and will restart it if it is paused.

private volatile boolean running;  // Control variable for signaling the threads to
// run or pause.  Initially, this is false, so
// the thread pauses as soon as it is created,
// until the user clicks the "Run" button.

private LinkedBlockingQueue<Integer> resultsQueue; // Results from the computation
// threads are placed into this queue.  Every number
// in the queue represents the results from running
// a batch of trials, of size BATCH_SIZE.  The number
// in the queue is the number of trials in that batch
// that resulted in x*x+y*y being less than 1.  (Note
// that I use a blocking queue rather than a
// ConcurrentLinkedQueue only because the blocking
// queue has a convenient drainTo() method for getting
// all the items out of the queue at once, with correct
// synchronization.)

private Timer resultsTimer;  // While the computation is running, this timer is
// also running.  Every 1/10 second, it grabs the
// results from the queue and applies them to the
// display labels.  (Note that some results can be
// left in the queue while the timer and threads are
// paused.  This seems harmless.)

/**
* Constructor creates the three display labels and adds them to this
* panel.  It adds a "Run"/"Pause" button below the labels.
* It also creates and starts the computation threads and the timer
* that takes the results from the threads and updates the labels
* every 1/10 second.
*/
public EstimatePi_3() {

setLayout(new GridLayout(4, 1, 2, 2));
setBackground(Color.BLUE);
setBorder(BorderFactory.createLineBorder(Color.BLUE,2));

countLabel =      new JLabel(" Number of Trials:   0");
piEstimateLabel = new JLabel(" Current Estimate:   (none)");
JLabel piLabel =  new JLabel(" Actual value of pi: " + Math.PI + " ");
Font bigMonospace = new Font("Monospaced", Font.PLAIN, 20);
countLabel.setFont(bigMonospace);
piEstimateLabel.setFont(bigMonospace);
piLabel.setFont(bigMonospace);
countLabel.setOpaque(true);
piEstimateLabel.setOpaque(true);
piLabel.setOpaque(true);

JPanel bottom = new JPanel();
runPauseButton = new JButton("Run");

for (int i = 0; i < threadCount; i++) {
runner.start();
}

resultsTimer = new Timer(100, new ActionListener() {
public void actionPerformed(ActionEvent e) {
grabResults();
}
});

} // end constructor

/**
* This method responds to clicks on the button, by
* toggling the value of the signal variable from true
* to false or from false to true.  The text on the
* button is changed to match the state.  The timer
* that grabs the results is also started or stopped,
* depending on whether the computation is running.  When
* running is set to true, notifyAll() is called to wake
* up all the threads.  (Note that the synchronization
* for controlling the threads is on the panel object,
* this.  The threads have to synchronize on the same
* object when testing the value of running.)
*/
public void actionPerformed(ActionEvent evt) {
if (running) {
resultsTimer.stop();
runPauseButton.setText("Run");
running = false;
}
else {
runPauseButton.setText("Pause");
resultsTimer.start();
synchronized(this) { // IMPORTANT: Synchronization is now on this JPanel object!
running = true;
notifyAll(); // IMPORTANT: Use notifyAll(), not notify(), to wake all computation threads
}
}
}

/**
* This method is called by the timer, every 1/10 second while the
* computation is running.  It grabs the entire contents of the
* queue that is used to send results from the threads to
* this method.  Each value in the queue represents the number of
* trials, out of a batch of size BATCH_SIZE, in which x*x+y*Y was
* less than 1.  This method updates the total number of trials that
* have been performed and the total number of trials for which
* x*x+y*y was less than 1.  It then updates the display labels
* with the new data.
*/
private void grabResults() {
ArrayList<Integer> results = new ArrayList<Integer>();
resultsQueue.drainTo(results);  // Get entire contents of queue.
// Using this method avoids having to synchronize
// the entire process of removing items from the
// queue one at a time.  (And doing that without
// synchronization would introduce a race condition.)
for (int inCircleCount : results) {
totalTrialCount += BATCH_SIZE;
totalInCircleCount += inCircleCount;
}
double estimateOfPi = 4 * ((double)totalInCircleCount / totalTrialCount);
countLabel.setText(      " Number of Trials:   " + totalTrialCount);
piEstimateLabel.setText( " Current Estimate:   " + estimateOfPi);
// System.out.println("Got " + results.size() + " results.");  // for testing
}

/**
*  This class defines the thread that does the computation.
*  The thread runs in an infinite loop in which it performs
*  batches of 1000000 trials and places the result in the queue.
*  Just after it starts and between batches, the thread tests
*  the value of the signal variable, running.  If this variable
*  is false, then the thread sleeps until the value of running
*  is set to true.  Note that this method creates and uses its
*  own object of type Random to generate random numbers. (Because
*  in multiple threads slowed things down immensely.)
*  Synchronization in this thread, as in the rest of the program,
*  is on the panel object, which is referred to here as
*  "EstimatePi_3.this".  The previous version used the thread
*  object for synchronization, but in this version there can
*  be multiple threads, so it seemed more natural to use the panel.
*/
setDaemon(true);
}
public void run() {
Random myRandom = new Random();
while (true) {
synchronized(EstimatePi_3.this) {
while ( ! running ) {
try {
EstimatePi_3.this.wait();
}
catch (InterruptedException e) {
}
}
}
int inCircleCount = 0;
for (int i = 0; i < BATCH_SIZE; i++) {
double x = myRandom.nextDouble();
double y = myRandom.nextDouble();
if (x*x + y*y < 1)
inCircleCount++;
}