# 15110 Fall 2011 [Cortina/von Ronne]

## Laboratory 9 - October 27

### Overview

In this lab, students will:

1. Use random number to estimate $$\pi$$ using the Monte Carlo method.
2. Explore how increasing the number of trials affects precision.
3. Explore how different random number generators affect the result (time permitting).

### Deliverables

1. pi_estimator.rb with rand_coord and estimate_pi functions
2. Optionally, pi_estimator2.rb with prng_coord and prng_pi functions.

### The Monte Carlo Method and $$\pi$$

The Monte Carlo method is a computational technique that works by calculating a statistical summary of a large number of random operations. One simple use of the Monte Carlo Method is to approximate the value of $$\pi$$.

Consider a unit circle (a circle of radius 1 whose center is at (0,0)) on a Cartesian plane, and a square whose corners are at (-1,1), (1,1), (1,-1), and (-1,-1). (Shown at right.). If a point is chosen randomly within square, the probability of it being also within the circle is determined by the ratio of the area of the circle, $$\pi(1)^2 = \pi,$$ to the area of the square, $$2^2 = 4.$$

We can use this fact to build a procedure to estimate the value of $$\pi$$:

1. Randomly generate a large number of points ($$n$$ points), each of which consists of a random x-coordinate and a random y-coordinate. These coordinates should be selected randomly from a uniform distribution of floating point values between -1 and 1.

2. For each point, determine whether the distance of the point from the origin $$\sqrt{x^2+y^2}$$ is less than or equal to 1.0. These are the points "inside" the unit circle.

3. Find the ratio of the total number of points inside the unit circle to the total number of points generated.

4. Multiple this ratio by 4 to obtain an estimate of $$\pi$$.

### Getting a Random Cordinate between -1 and 1

In lecture, you learned that it is possible to obtain a random integer between 0 and $$n-1$$ by using the Ruby function rand(n). To obtain a random floating point number between -1 and 1, you can:

1. Generate a random integer between 0 and 2,000,000,000.

2. Subtract 1,000,000,000 from the result of the previous step.

3. Divide the result of the previous step by 1000000000.0 to obtain a random floating point value between -1.0 and 1.0.

### Activities

1. Individually or in pairs, implement a ruby function, rand_coord that uses the Ruby rand function to generate a random floating point value between -1 and 1. Test your function several times to make sure it generates different floating point numbers.

2. Individually or in pairs, implement a ruby function estimate_pi(n) that returns an estimate of $$\pi$$ computed following the procedure describe above. The parameter $$n$$ should control the number of points that are generated.

1. Use your estimate_pi function to generate an estimate of $$\pi$$ using an $$n$$ of 1000. Report the value to the class. For how many digits is it correct (i.e., the same as Math::PI)? Is your estimate of PI the same as that of your classmates?

2. Use your estimate_pi function to generate an estimate of $$\pi$$ for different values of $$n$$ as directed by your CA. Report the value to the class.

3. Time permitting, create a prng_coord, which works like rand_coord except that it uses the PRNG class from RandomLab, and a prng_pi that uses prng_coord to calculate an estimate of pi.

Hints:

• In addition to $$n$$, you will probably want to give prng_pi additional parameters for specifying the values of a, c, and m that are used to create a PRNG object.

• You'll probably want to pass the PRNG object and the m-value from prng_pi into prng_coord as parameters.

• The random(min,max) operation of PRNG objects will not return values greater than the PRNG's m-value, so you'll need to take that into account when doing prng_coord.)

Experiment with initializing the PRNG object with different (a, c, and m) parameters for PRNG, such as:

• 1, 8, 12
• 1, 7, 12
• 81, 337, 1000
• 1225, 6173, 29282
• 421, 54773, 259200

Which of these give better/worse estimates for $$\pi$$?