Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Example-Computing tex2html_wrap_inline68478

This section presents a simple, Monte Carlo algorithm to compute the value of tex2html_wrap_inline68478 from a sequence of random numbers. Consider a square positioned in the x-y plane with its bottom left corner at the origin as shown in Figure gif. The area of the square is tex2html_wrap_inline68486, where r is the length of its sides. A quarter circle is inscribed within the square. Its radius is r and its center is at the origin of x-y plane. The area of the quarter circle is tex2html_wrap_inline68496.

   figure33911
Figure: Illustration of a Monte Carlo method for computing tex2html_wrap_inline68478.

Suppose we select a large number of points at random inside the square. Some fraction of these points will also lie inside the quarter circle. If the selected points are uniformly distributed, we expect the fraction of points in the quarter circle to be

displaymath68476

Therefore by measuring f, we can compute tex2html_wrap_inline68478. Program gif shows how this can be done.

   program34080
Program: Monte Carlo program to compute tex2html_wrap_inline68478.

The Pi method uses the RandomNumberGenerator defined to generate (x,y) pairs uniformly distributed on the unit square (r=1). Each point is tested to see if it falls inside the quarter circle. A given point is inside the circle when its distance from the origin, tex2html_wrap_inline68520 is less than r. In this case since r=1, we simply test whether tex2html_wrap_inline68526.

How well does Program gif work? When 1000 trials are conducted, 792 points are found to lie inside the circle. This gives the value of 3.168 for tex2html_wrap_inline68478, which is only 0.8% too large. When tex2html_wrap_inline68530 trials are conducted, 78535956 points are found to lie inside the circle. In this case, we get tex2html_wrap_inline68532 which is within 0.005% of the correct value!


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.