Skip to content

Instantly share code, notes, and snippets.

@fphilipe
Last active Dec 20, 2015
Embed
What would you like to do?
Monte Carlo Sampling of π

From the Wikipedia article on Monte Carlo method:

Monte Carlo methods (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results; [...]

Given that the circle and the square have a ratio of areas that is π/4, the value of π can be approximated using a Monte Carlo method:

  1. Draw a square on the ground, then inscribe a circle within it.
  2. Uniformly scatter some objects of uniform size (grains of rice or sand) over the square.
  3. Count the number of objects inside the circle and the total number of objects.
  4. The ratio of the two counts is an estimate of the ratio of the two areas, which is π/4. Multiply the result by 4 to estimate π.
<!DOCTYPE html>
<meta charset='utf-8'>
<body>
<style>
body {
font-family: 'Helvetica Neue', Helvetica, sans-serif;
}
.wrapper {
padding: 10px;
}
svg {
float: left;
margin-right: 10px;
}
.inside {
fill: red;
}
.outside {
fill: blue;
}
circle {
stroke: black;
stroke-width: 1px;
fill: none;
}
hr {
border: solid black;
border-width: 1px 0 0 0;
}
table {
width: 300px;
}
.numeric td:first-child, .numeric td:first-child + td {
white-space: nowrap;
width: 1%;
}
.numeric td:first-child + td + td {
width: 99%;
}
</style>
<script src='http://d3js.org/d3.v3.min.js'></script>
<div class='wrapper'>
<table class='numeric'>
<tr>
<td>π</td>
<td>&approx; 4 &times; inside</td>
<td>&divide; total</td>
</tr>
<tr>
<td></td>
<td>= 4 &times; <span id='inside'>0</span></td>
<td>&divide; <span id='total'>0</span></td>
</tr>
<tr>
<td></td>
<td colspan='2'>= <span id='pi'>NaN</span></td>
</tr>
</table>
<p>Relative Error: <span id='error'>NaN</span>%</p>
<hr />
<table class='config'>
<tr>
<td>Speed:</td>
<td>
<select>
<option value='1000'>Slow</option>
<option value='100' selected>Medium</option>
<option value='10'>Fast</option>
</select>
</td>
</tr>
<tr>
<td>Points per iteration:</td>
<td><input type='number' step='10' value='100' /></td>
</tr>
<tr>
<td colspan='2'>
<input type='button' value='Start' class='toggle' />
<input type='button' value='Reset' class='reset' />
</td>
</tr>
</table>
</div>
<script>
var inside = 0
var total = 0
var circleRadius = 240
var timeout
var running = false
var speed = 100
var pointsPerIteration = 100
var points = []
var svg = d3.select('.wrapper').insert('svg', ':first-child')
.attr('width', circleRadius * 2)
.attr('height', circleRadius * 2)
svg.append('circle')
.attr('cx', circleRadius)
.attr('cy', circleRadius)
.attr('r', circleRadius)
var toggleButton = d3.select('.toggle').on('click', toggle)
d3.select('.reset').on('click', reset)
d3.select('select').on('change', function() {
speed = parseInt(this.options[this.selectedIndex].value, 10)
})
d3.select('input[type=number]').on('change', function() {
pointsPerIteration = parseInt(this.value, 10)
})
function reset() {
stop()
points = []
total = 0
inside = 0
redraw()
}
function toggle() {
running ? stop() : start()
}
function start() {
running = true
iterate()
toggleButton.attr('value', 'Stop')
}
function stop() {
running = false
clearTimeout(timeout)
toggleButton.attr('value', 'Start')
}
function iterate() {
for (var i = 0; i < pointsPerIteration; i++) {
// Math.random returns a number in [0, 1) but we need (0, 1]:
var point = [1 - Math.random(), 1 - Math.random()]
if (isPointInside(point))
inside++
total++
points.push(point)
}
redraw()
timeout = setTimeout(iterate, speed)
}
function redraw() {
var rect = svg.selectAll('rect').data(points)
rect.enter().append('rect')
.attr('x', function(d) { return (1 + d[0]) * circleRadius })
.attr('y', function(d) { return (1 - d[1]) * circleRadius })
.attr('width', 1)
.attr('height', 1)
.attr('class', function(d) { return isPointInside(d) ? 'inside' : 'outside' })
rect.exit().remove()
d3.select('#inside').text(inside)
d3.select('#total').text(total)
var pi = 4 * inside / total
var error = Math.abs(Math.PI - pi) / Math.PI * 100
d3.select('#error').text(error.toFixed(5))
d3.select('#pi').text(pi.toFixed(5))
}
function isPointInside(point) {
return Math.sqrt(Math.pow(point[0], 2) + Math.pow(point[1], 2)) <= 1;
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment