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:

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

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