Here at Civis, we like to have fun. And what’s more fun than coming up with new and creative ways to measure pi? For our recent one-year anniversary party, we hosted a [Civis Science Fair]({% post_url 2014-06-01-anniversary-science-fair %}) in our shiny new office. Joerg Rings and I decided to use the occasion to teach people about a common computational technique called the Monte Carlo method by measuring pi with a smartphone, some computer vision code, a shoebox, and a handful of lentils. Confused? Read on.

## A Little Geometry

Imagine that we stick a circle inside of a square that is just big enough to hold it:

If you brush away the cobwebs from that dusty part of the brain where high school geometry resides, you might remember that pi captures the relationship between the area of a circle

and its radius:

$$

\text{A}_\bigcirc = \pi R^2

$$

Similarly, the area of a square is given by the square of the length of its sides:

$$

\text{A}_\square = (2R)^2 = 4R^2

$$

Putting these two equations together, we get a simple formula for pi:

$$

\pi = 4 \frac{\text{A}*\bigcirc}{\text{A}*\square}

$$

But how do we measure the area of the circle and the square if we can’t use a ruler and those two formulas? Here’s where we turn to Monte Carlo methods.

## Monte Carlo Methods

Monte Carlo methods make clever use of random numbers to do calculations that would otherwise be quite difficult. John von Neumann and Stanislaw Ulam originally invented them during World War II to simulate the scattering of neutrons in radiation shielding materials (Ulam’s uncle was a gambler who liked to frequent the Monte Carlo Casino in Monaco, which gave these methods their name). Instead of solving the difficult equations of motion of the neutrons, they simulated their movement by picking random numbers and shifting the motion of the neutron each time it was supposed to scatter. Monte Carlo methods are used everywhere in the sciences, and we put them to work every single day for the Bayesian statistical work we do to forecast elections.

In our case, we want to calculate the ratio of the areas of the square and the circle. Let’s imagine that we had a handful of pebbles and we scattered them randomly on top of our diagram above. A bunch would land in the circle, and a bunch would land in the square. Because the square is bigger, you’d expect more to end up inside the square than inside the circle. By simply counting the number of items that land inside the square and then counting the number that land inside the circle and taking their ratio, we should get a pretty decent estimate of the ratio of the areas. From our formula above, that should be $$\frac{\pi}{4}$$. And all we had to do was use a little randomness and simple counting.

Scrounging around the office, we came across an old shoebox and a package of dried lentils. Perfect. We threw a handful of lentils into the shoebox, put the lid on, and shook it up. Since we’re way too lazy to count things by hand, we took a photo of the scattered lentils with a smartphone, sent it to a computer, and then taught the computer to find and count the lentils with python and the OpenCV library.

## Computer Vision with Python

The python code loads the image and then runs a Hough transform algorithm that automatically picks out circles in the image and figures out if they’re inside the circle or the square. After tweaking the code a bit, this is what we got:

The lentils outlined in green are inside the circle, the ones in blue are inside the square but not the circle, and the ones in red are outside of both. Taking the ratio, we estimate pi as 3.591, which is off by around 14%. Repeating the process many times throughout the course of the science fair and averaging the results, we ended up, at the end of the night, with an estimate of 3.180, just 1% from the true value. Not too shabby.

Take a look at the source code, or download our ipython notebook yourself and give it a try. And if you’re really interested, read some more about Buffon’s Needle, another Monte Carlo method for estimating pi that was first formulated in 1777.

The post Measuring Pi with Lentils and Python appeared first on Civis Analytics.