Monte Carlo Pi & Processing.js

March 29th 2013

Over the years, mathematicians have dedicated tremendous amounts of research to conceiving of new and faster methods of approximating Pi. Hundreds of books have been written on this remarkable constant, and on disparate attempts to get another thousand digits. The current, bleeding-edge algorithms are remarkably fast, but also, quite frankly, often mind-boggling. When looking at all of these crazy algorithms, there’s often the risk of losing sight of the forest for the trees. Sometimes, it’s fun to look at a method that you can understand and comprehend intuitively with nothing more than middle-school math, just to get a new, deeper perspective on Pi and what it really means. That’s where the Monte Carlo method of approximating Pi, probably one of my favorites, comes in. A Monte Carlo method is simply any method that uses repeated random simulations to calculate probabilities. Basically, instead of using ‘real’/theoretical statisitcs to calculate the probability of heads on a fair coin, just simulate flipping it a million times and record what percentage is heads/tails. While it may not be as accurate, and is potentially orders of magnitude slower, the Monte Carlo method has the advantage of being extremely easy to comprehend conceptually, and usually also to implement.

Where does Pi come in? Well, first some background ($r$ is a radius, $s$ is a side length):

$Area\ of\ a\ Circle = \pi r^2$

$Area\ of\ a\ Square = s^2$

Now consider a Circle inscribed in a square, with radius $r$, like so:

Since the center point of the circle is the same as that of the square, it follows that the side length of the square ($s$) would be equal to twice the radius:

$s = 2r$

Therefore, by substituting $2r$ for $s$, we can arrive at the following to represent the area of the square using the radius of the inscribed circle:

$Area\ of\ a\ Square = s^2 = (2r)^2 = 4r^2$

Now we can return to our Monte Carlo method. I like to think of this particular method in terms of a dart board because, well, the inscribed circle looks just like a target. Imagine you have an infinite supply of darts, and you throw them at random locations on the dart board. You don’t try to aim inside or outside the circle (or maybe you do if, like me, you’re bad enough for it not to matter), and none of your darts miss the board entirely. Now, if you kept this up for an infinitely long time, the ratio between the darts in the circle and the darts in the square should theoretically become equal to the ratio between the area of the circle and the area of the square. So, considering that none of our darts land outside the square, we can say:

$\frac{Darts\ in\ Circle}{Darts\ Thrown} = \frac{Area\ of\ Circle}{Area\ of\ Square}$

And if we use our formulae from above to simplify:

$\frac{Darts\ in\ Circle}{Darts\ Thrown} = \frac{\pi*r^2}{4r^2} = \frac{\pi}{4}$

$\frac{4 * Darts\ in\ Circle}{Darts\ Thrown} = \frac{4*\pi}{4} = \pi$

Obviously, as we throw more darts, the ratio becomes closer to the theoretical probability and our approximation gets more accurate. Now lets try implementing it! Feel free to skip to the bottom if you’re not interested in the code, and just want to see the simulation.

For this, I’m going to use the fabulous Processing.js. First, I’ll go ahead and make a canvas in my html document, and give it an id. I’m also putting a span above it where I’ll display the approximation so far:

 π ≈ <span id="pi"></span><br /><canvas id='monte-carlo'></canvas> 

Now, require the processing files (You can put this in the head of your document):

 <script src="//cdnjs.cloudflare.com/ajax/libs/processing.js/1.4.1/processing.min.js"></script> 

With processing, you can use the Processing language or Javascript. I opted to use Processing, just because it’s simpler and can handle inline javascript for interacting with the DOM. So, after the canvas element we created, we can put in the real code:


<script type="text/processing" data-processing-target="monte-carlo">
void setup()
{
  //Called initially
}

void draw(){  
  //Called in a loop, about 60 times per second
}
</script>

Now for the fun part! We simply replace the setup method above with the code to draw the square with inscribed circle, and make the draw method draw a random point inside the square. One of the great things about Processing.js is its ability to use javascript inline with no special accomodations, so I just wrote in some utility functions and counter variables at the top of the script. This could probably use some refactoring, but it works and it’s simple. The script itself is pretty self-explanatory, and quite heavily commented, but you can consult the Processing Reference for full method signatures and docs:


<script type="text/processing" data-processing-target="monte-carlo">

  // In Processing, we can just throw in javascript and have it be left alone by the Processing parser,
  // so here are the variables to keep track of the number of points inside the circle and square respectively
  var inCircle = 0;
  var inSquare = 0;
  // each point, in turn, will be in this variable
  var pt = 0;
  //a function to see if a point is inside the circle:
  var isInCircle = function(point) {
    //check if the distance from the center of the circle the point is less than the radius
    return Math.sqrt(Math.pow(101 - point.x,2) + Math.pow(101 - point.y, 2)) <= 100;
  };
  //a function to update the Pi approximation
  var updateApprox = function() {
    document.getElementById("pi").innerHTML = 4 * inCircle / inSquare;
  };


  void setup() {
    //Make the frame rate as fast as possible (This might not be the best way to do it...)
    frameRate(1000);
    // set the size of the canvas
    size(205,205);
    // white background
    background(255);
    // set the fill on shapes to transparent
    noFill();
    // set the origin of the elipses to the upper right corner
    ellipseMode(CORNER);
    // set the thickness of the line
    strokeWeight(2);
    // set the line color to black
    stroke(000);
    // draw the square
    rect(1,1,200,200);
    // draw the inscribed circle
    ellipse(1,1,200,200)
  }

  void draw () {
    // generate a random point. Note: 'random' is a Processing function
    pt = {x: random(1, 201), y: random(1, 201)};
    // increment the correct counters, and change color depending on region
    inSquare++;
    stroke(0,255,0);
    if(isInCircle(pt)) {
      inCircle++;
      stroke(255, 0, 0);
    }
    //draw the point
    point(pt.x, pt.y);
    //every 30 points, update the approximation
    if(inCircle % 30 === 0) {
      updateApprox();
    }
  }

</script>

And here’s the result. Reload the page to start over. It gets to pi extremely slowly, but I think its a fun and intuitive visual presentation. Thanks for reading!

$\pi\approx$

blog comments powered by Disqus