Difficulty: Beginner
Prerequisites
- This project requires the following Python modules to be installed on your computer:
pygame
Background
Lots of everyday math problems, like the equation x + 5 = 7, can be solved directly. However, if a mathematical problem is of a certain type, or if it is very complicated, you might not be able to solve it by hand. This is one area where computers come in handy.
One common way to use a computer to solve certain math problems is the Monte Carlo method. Monte Carlo methods use the results of hundreds, thousands, or even millions of random simulations to calculate a good estimate of average behavior.
Monte Carlo methods were developed by Manhattan Project scientists working on atomic weapons at the dawn of the computer age, and nowadays are used in virtually every category of science and math. For example, they are helpful in predicting the flow of liquids and the behavior of cells. Geologists use them to find minerals and oil and ecologists use them to simulate ecosystem changes.
Whether predicting the weather or the stock market, the Monte Carlo method is a useful tool to have.
Estimation of Pi
The King of Programmia wants to build a giant circular labyrinth and wants to know how many bricks he needs for the outer wall. He knows the diameter (how far the maze is across) but needs to know the circumference (how far the maze is around). To calculate the circumference accurately, you need to know the value of π (pi) to several decimal places. Unfortunately, you don’t have any digits of π memorized, and the castle WiFi is down, so you can’t look it up on the internet. The King wants this calculated as soon as possible, so you come up with a clever way of estimating π using the Monte Carlo method.
You can easily calculate the area of a square (length * length), so you inscribe a circle inside a square of known area like so:
You know that the area of the square is
length * length
and that the area of the circle is
π * (length / 2) * (length / 2)
or
(length * length) * (π / 4).
So, if you divide the area of the circle by the area of the square, you get:
(area of circle)/(area of square) = (π / 4)
because the (length * length) cancels out.
To estimate π, all you need to do is find the ratio of the area of the circle to the area of the square and multiply by four!
So, you start “throwing darts” at the square: picking random (x, y) points within the square:
Since a dart is equally likely to land anywhere in the square, the ratio of the number of darts that hit the circle to the total number of darts thrown at the square will be a very good estimate of the ratio of the area of the circle to the area of the square. However, you would need to throw a lot of darts to get a very accurate result, so you write a computer program to do it for you.
What to Do
- Download the zip file from here and unzip it to a folder.
- Run
monte_carlo_pi.py. Need help with Python? - Type in a number of iterations (darts to throw at the board).
- Now, watch it run!
- Write down the estimated value, then try it again with a different number of iterations, noting the value you got for each (try 100, 1000, 5000, 10000, 50000, 100000, and 1000000).
- The real value of the first several digits of π is
3.1415692654.... Subtract this from the value you got for each number of iterations to see how far off you were. Make a graph with this “error” on the y-axis and the number of iterations on the x-axis.
