Estimating pi in R using Monte Carlo (Iterating)

While in this example we do not use the MapReduce infrastructure, we can still use Map and Reduce functions to illustrate how these work.

We use a divide and conquer approach. We use the unit circle (radius equals 1) in this case, the natural map function is to simply divide the circle into n parts, say for example four parts:

Unit Circle

But we can see from the graph (and formally, from being able to convert any subsection of the square and circle into any other section by calculating x = cos (), y = sin(θ) for any r with angle θ) that each part is actually equivalent:

Angles

Thus our map function can just be to calculate, for each worker, the ratios of hits and misses in the circle for the ranges (0<=x<=1, 0<=y<=1) over and over.
Many Quarter Circles

The Reduce function can, in fact just simply be the average of all of our individual experiments, where n is the number of workers, and the it a value is the approximate result of pi estimated by each worker..

Map Function

In terms of R, if we assign 1,000 experiments to each worker:

# The amount of work each worker will do (1 point is not worth it the
# overhead of having a worker...)
ExperimentsPerWorker <- 1000; piMap <- function (workerID=NA) { # Generate points, we generate them all at once... testX <- runif(ExperimentsPerWorker, min=0, max=1) testY <- runif(ExperimentsPerWorker, min=0, max=1) # Test if in the circle i <- 1; inCircle <- 0; while (i < ExperimentsPerWorker) { if ((testX[i] ^ 2 + testY[i] ^ 2) <= 1.0) inCircle <- inCircle + 1 i <- i + 1 } # Return the ratio. In this program, each worker # is actually identical in the task they do... # All tasks are actually identical --a special case. return (4.0 * inCircle/ExperimentsPerWorker) } # This function reduces a multitude of worker results # into a single number: piReduce <- function (prelimResults) { return (mean(prelimResults)) } # The master function separates the complete task based # on a given number of workers piMaster <- function (workers) { prelimResults <- matrix(seq(0,workers-1,by=1)) prelimResults <- apply (prelimResults, 1, piMap) estimatedPi <- piReduce(prelimResults) return (estimatedPi) }

Now when we run the experiment, for one to one hundred workers, i.e. from one thousand to one million experiments, and plot, we approximate pi as follows:

Screen Shot 2014-09-28 at 10.37.47 PM

Comments are closed