15110 Spring 2013 [Kaynar/Gunawardena]

Lab 10 - Thursday, April 4, 2013

Deliverables

1. pi_estimator.rb
2. estimates.txt

Place these files in a lab10 folder. Before leaving lab, zip up the lab10 folder and hand the zip file in.

RubyLabs Information

This lab uses facilities provided by RubyLabs. If you were not present for Lab 4 (with the time operation) or Lab 6 (with the Canvas), you will need to setup RubyLabs before beginning this lab.

CA-Led Activities/Demonstration

• Review Monte Carlo methods and Pi
• rand(n) function
• rand() function
• Pseudo random number generadors and the PRNG class in RubyLabs

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). If we only consider the top right quarter (shaded in the figure to the right), we can estimate pi using the following method. If a point is chosen randomly within the colored square, the probability of it being also within the shaded quarter circle is determined by the ratio of the areas, $\frac{\pi(1)^2}{4} = \frac{\pi}{4},$ to the area of the square, $1^2 = 1.$

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 0 and 1.

2. For each point, determine whether the distance of the point from the origin (calculated by the formula $\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 number of points inside the unit circle to the number of points generated.

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

Activities

All functions should be place in pi_estimator.rb and all questions should be answered in estimates.txt

1. Implement a Ruby function, rand_coord() that uses the Ruby rand() function to generate two random floating point values between 0 and 1 and returns them in an array. The returned array represents a point.

2. Implement a Ruby funciton, in_circ?(x,y) that returns true if the point is in the circle, and false if the point is not in the circle.

3. Implement a Ruby function, estimate_pi(n) that returns an estimate of $\pi$ using the rand_coord and in_circ functions. Remember there is a general description of the method above the activities section. The parameter $n$ is the number of points to be used in the estimation.

4. Implement a Ruby function, rand_coord2(), that returns a random number between 0 and 1 (similar to rand_coord()) that must use the rand(n) function with an integer input. Now, create a Ruby function estimate_pi2() that is identical to estimate_pi() except that it uses rand_coord2().

   Hints:

   • Try making a function rand_float() that returns a random float between 0 and 1 (inclusive).

   • In the rand_float() function, think about what rand(n) could be divided by to output a number between 0 and 1.

   • Think about what kind of value for n in rand(n) do we want to use. How many possible random coordinates can we get if n is 10 as opposed to 1000?

   Test the accuracy of this function compared to that of estimate_pi() (i.e. What is the difference between the results of subtracting estimate_pi() and Math::PI versus estimate_pi2() and Math::PI). Which estimate is more accurate and why?

5. The quality of the random point distribution will strongly effect the accuracy of the simulation. To see this, create rand_coord3, which works like rand_coord except that it uses the PRNG class from RandomLab, and a prng_pi that uses rand_coord3 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 rand_coord3 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 rand_coord3.)

   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$?