Tuesday, April 15, 2014

PI approximation using Monte Carlo method - html5 canvas illustration

Just for fun I've coded simple Monte Carlo PI approximation illustrated with html5 canvas.

Here is full working example on jsfiddle: http://jsfiddle.net/yLmtp/

How it works?

Assuming we have a unit square

unit square
 If we draw circle inside the square with radius
1/2 we know that the area of that particular circle is AreaC  = radius^2 * PI = (1/2)^2 * PI = 1/4 * PI. Also area of unit circle is AreaS = 1^2 = 1

Finally if we calculate ratio of two areas we have AreaC/AreaS = (1/4 * PI) / 1 = 1/4 * PI

Ok, so ratio between areas is 1/4* PI but if we multiply above result by 4 we have exactly PI.

This is how we are going to approximate number PI, by calculating ratio between circle and square and multiplying that result by 4. 





What is the method?

We are going to generate new random (pseudorandom) point Ai(x,y) in each iteration within limits of our square and then we are going to observe will that point fall within the circle also or not. In case it does fall within the area of the circle we increase CA counter by 1 (CA++) otherwise we don't increase CA counter. Also in each iteration we increase SA counter by 1 (SA++) 

The more iterations (randomly generated points we have) more the ratio should converge to 1/4 * PI and since we just want to approximate number PI in each iteration we multiply result by 4.   


This method is very slow, how fast result converges to PI depends on how "random" are pseudorandom numbers generated by software and number of iterations.

The code is not optimized at all, it could be quicker, but that wasn't the intention. 

Here is full working example on jsfiddle: http://jsfiddle.net/yLmtp/

No comments:

Post a Comment