Pi approximation using Monte Carlo method

Monte Carlo is a method to solving problems that uses random inputs to examine the domain. This method has a wide variety of applications from problems too complex to solve analytically to estimating amount of time a task will take in FogBugz. Pi approximation is a simple example that illustrates the idea of how the Monte Carlo method works.

The algorithm below uses the JavaScript (ES6) generators to create an infinite stream of inputs and the HTML5 canvas to visualize the classification of points.

• The blue circle square has an area of πr².
• The gray square has an area of (2 × r)² = 4r².
• The ratio of the circle area to square area is p = πr²/4r² = π/4.
• Therefore the value of π is 4×p.
• The red square contains ¼ of blue and gray points so the ratio of points is the same (p).

The implementation takes a random point inside the unit square of size 1×1 and checks if that point lies within the blue circle. The ratio of points inside the circle to all generated points is p. Multiplying p by 4 gives the approximate value of π.

To run the example your browser has to support:

• ES6 generators
• for-of loops

Chrome (version 36) supports the ES6 generators but it's necessary to enable Experimental JavaScript at chrome://flags/#enable-javascript-harmony. Firefox (version 31) supports generators natively.

function* points() {
    while (true) {
        var x = Math.random();
        var y = Math.random();
        var distance = Math.sqrt(x * x + y * y);
        var isInside = false;
        if (distance < 1) {
            isInside = true;
        }
        yield {
            x: x,
            y: y,
            isInside: isInside
        };
    }
}

function* piApprox(points) {
    var inside = 0;
    var all = 0;
    for (var point of points) {
        all++;
        if (point.isInside) {
            inside++;
        }
        yield {
            x: point.x,
            y: point.y,
            inside: inside,
            isInside: point.isInside,
            all: all,
            approximation: 4 * (inside / all)
        };
    }
}

function* take(count, seq) {
    for (var i = 0; i < count; i++) {
        yield seq.next().value;
    }
}

var solutions = piApprox(points());

function next() {
    var x, y;

    for (var item of take(100, solutions)) {
        x = item.x * canvas.width;
        y = item.y * canvas.height;
        context.fillStyle = item.isInside ? 'blue' : 'silver';
        context.fillRect(x, y, 1, 1);
    }

    inEl.textContent = item.inside;
    outEl.textContent = item.all;
    piEl.textContent = item.approximation;

    window.requestId = window.requestAnimationFrame(next);
}

window.requestAnimationFrame(next);

var canvas = document.querySelector('canvas');
var context = canvas.getContext('2d');

var inEl = document.querySelector('.inside');
var outEl = document.querySelector('.outside');
var piEl = document.querySelector('.pi');

var stop = document.querySelector('.stop');
stop.disabled = false;

stop.onclick = function() {
    window.cancelAnimationFrame(window.requestId);
};

The same algorithm implemented using pepper.js can be found on the Monte Carlo Estimate for Pi site.

Comments