## CS 101 (Spring 2000) Lab 5: Slices of PI

Lab Assigned
Design Due
(In class)

10 AM
Implement
(In Lab)
Demo
(In Lab)
Lab Due
(In class)
Friday
10 AM
15 Feb 18 Feb 22-33 Feb 29-30 Feb 03 Mar

### Overview:

Iteration is another technique for repetitive computations. In this lab, you will use recursion to draw a circle and iteration to throw darts at the circle, which is circumscribed in a square.

### Goals:

By the end of this lab, you should
• Gain more experience in API design
• Gain more experience with recursive solutions and programs
• Gain experience with iterative solutions and programs
• Understand how straight lines approximate curves in graphics
• Understand the role of randomness in simulations
This lab contains two parts, design and implementation, due as shown at the beginning of this document. The Monday after your design is due, a sample design will be handed out in class. We may choose one of your designs for this honor; or, we may write one up on our own. Remember, there is no right or wrong design, but each design may have its own strengths and weaknesses.

### Before starting:

• Read over this entire document before you start.
• Make sure you understand what is expected from you by way of an API.
• Study the recursion and interation examples given in class.
Zip includes:

Recall that the following lines should appear at the top of any files that use the terminal or canvas classes.

```import terminal.*;
import canvas.*;
```

### Problem description: Slices of PI

Design and implement the class `PI.java` that does the following.

• Initially (when the constructor is called), a square of size S is drawn. Also, fully contained in this square, a circle of diameter S is drawn. The circle is actually drawn as a sequence of n straight lines, where n is a parameter of your constructor (hint, hint). In other words, a polygon with n sides approximates the circle. You must use recursion to draw the polygon.
• Subsequently, when a method of your choosing (in your design) is called
• m darts are thrown at the circle in the square. Based on the number that land in vs. out of the circle, you are to return an approximation for PI as described below. You must use iteration to throw the darts.
• The location of each dart throw is shown on the screen by a dot (hint: a very small line). Red dots are those that land in the circle, and black dots are those that land outside.
• Your design should include the specification of some methods to find out how much work your PI class did. At the least, methods to obtain the following should be specified:
• How many darts were thrown?
• How many darts landed inside the circle?
• How many darts landed outside the circle?
• The results of these statistics should be formatted nicely as a string of your `PI`'s `toString()`.

### Design Strategy

• Complete a design cover sheet.
• Define your `PI` class. Give its API and describe what all of its methods do. If necessary, review the definition of an API from the Lab 4 design exercise.
• Don't worry yet about how your methods will do their work; worry only about the API.

### Monte Carlo methods and PI

Algorithms that involve randomness are often said to use Monte Carlo technqiues---the term is named after the famous casino. Randomness is often employed to lend a sense of realism to games and other simulations.

In this case, we wish to throw darts at a board. The board is square, with each side having length S. How do we simulate a random dart throw? Unlike real life, we do want to be sure that it lands somewhere in the square. We can decompose the problem into picking an x and a y coordinate, each chosen randomly so that the dart lands in the square.

For example, if we say the square is addressed from (0,0) to (S-1,S-1), then we can use:

```   int randX = (int) (Math.random() * S);
int randY = (int) (Math.random() * S);
```
to obtain a random x and y coordinate.

Next, we care whether the dart lands inside the circle. By this, we mean that the distance of the dart from the center of the circle is no greater than the circle's radius.

Why do we care? If we throw darts randomly at the square, some will land in the circle, and some will land outside the circle. If the darts are thrown uniformly, without bias, then we expect the darts to land in the circle at a rate proportional to the circle's area with respect to the square.

The circle's area is

```
___     ___ 2
circle area =   PI x   |    S    |
|   ---   |
|    2    |
---     ---
```
while the square's area is
```                          2
square area =          S

```
Dividing these two yields the probability of a dart landing in the circle, namely PI/4. Thus, if we throw darts, counting the number that land inside the circle and the number that we throw, the ratio of those two numbers should approach PI/4.