Today is March 14th, or Pi Day because 3.14 is March 14th rendered in
month.day date format. A very slightly better way to celebrate the ratio of a circle’s circumference to its diameter is July 22nd, or 22/7 written in
day/month order, a fractional approximation of pi that’s been used for thousands of years and is a better fit than 3.14. Celebrating Pi Day on July 22nd also has the advantage of eschewing middle-endian date formatting.
But Pi Day is completely wrong. We should be celebrating Tau Day, to celebrate the ratio of the circumference to the radius instead of the diameter. That’s June 28th, or 6.283185…. Nonetheless, today is Pi Day and in the absence of something truly new and insightful — we’re still waiting for someone to implement a spigot algorithm in 6502 assembly, by the way — this is a fantastic opportunity to discuss something tangentially related to pi, the history of mathematics, and the idea that human knowledge builds upon itself in an immense genealogy stretching back to the beginning of history.
This is our Pi Day article, but instead of complaining about date formats, or Tau, we’re going to do something different. This is how you approximate pi with the Monte Carlo method, and how anyone who can count to a million can get a better approximation of one the fundamental constants of the Universe than Archimedes.
What Is Monte Carlo?
Before we dig into this, it’s important to describe what the Monte Carlo method of problem solving actually is. In short, it’s measuring or simulating some sort of system with the application of random numbers. Any sufficiently complete history of Monte Carlo method of problem solving begins with Buffon’s needle problem, but this example muddles the issue, and came about two hundred years before this sort of randomness was applied to statistical insight.
The true origin of Monte Carlo simulations came from the development of the hydrogen bomb in the late 1940s. Stanislaw Ulam is credited with discovering this technique when investigating exactly how much neutron shielding would be needed in a certain application. The problem couldn’t be solved, but there was a probability distribution for this system. The key factors of the design were known — how far a neutron would travel through a medium, and how much energy would be given off when colliding with the nucleus of an atom. The solution to this problem was to simply throw random numbers at the problem, letting the known probability distribution take care of the rest.
Working through an example of the Monte Carlo method is a much better way of understanding, so let’s do that. This is how you approximate a value for pi using hundreds of thousands of random numbers.
So How Do We Estimate Pi?
What we’re doing here is drawing a circle, with a diameter of two (a radius of one). This is commonly known as a unit circle. This circle is inscribed into a square with a side length of two. We place hundreds of thousands of random points inside the square, count the total number of points placed and comparing that with the total number of points inside the circle. Because we’ve chosen a radius of one, and the area inside the circle is ,
Total Points / Inside Points will give us an approximation of Pi.
If there’s one thing computers are good at, it’s counting. So with a little bit of Python, we can easily run our experiment:
import random as dot import math as m # Total number of random points. total = 1000000 # Points contained in the circle. inside = 0 #Main loop for i in range(0, total): # Place random dots in unit square x2 = dot.random()**2 y2 = dot.random()**2 # Check if inside circle, # increment counter if inside if m.sqrt(x2 + y2) < 1.0: inside += 1 # We're only doing positive x/y coords, # so multiply by four. pi = (float(inside) / total) * 4 # Print result print(pi) # Print difference difference = m.fabs(pi - m.pi) print(difference)
An explanation of what’s going on in this code should be in order. We set our total points at 1,000,000 and iterate through that range. Each iteration sets a random X and random Y coordinate and places the point on our plane. Determining the total number of points inside the circle is calculated with
x² + y² < 1.0. If that equation is satisfied the “inside” points value is incremented.
That’s the jist of the above code, with one caveat; we don’t need to deal with negative
y coordinates. We can simply ignore those, and multiply the ratio of the number of random points inside the circle over the total number of points by four.
After a few dozen runs of this small script, I rarely got a result that was off by more than 0.002. Most results ranged from 3.141 to 3.143. That may not sound impressive to anyone that can rattle off the first dozen or so digits of pi from memory, but consider the historical alternative. Archimedes’ best estimate for pi was
223 / 71 < π < 22 / 7, or two decimal places. Ptolemy calculated pi to three decimal places, and in the third century, Chinese mathematicians managed to figure out five decimal places. The Monte Carlo method, which is simply counting a dividing albeit on a scale no human should ever have to do, improves on any of these numbers. Do this, and you know pi to more places than Fibonacci.
A Truly Modern Technique
One thing that’s so easy to forget is that ancient people were just as smart as anyone walking down the street today. It’s not fair to discount ancient beliefs that whales are fish, that the Earth is flat, the value of mathematical constants, or even what our solar system looks like simply because someone lived a few thousand years before us. They simply didn’t know any better. Is it fair to criticize Archimedes for not calculating a better value of pi? No, and not just because it would involve counting to a million.
The Monte Carlo technique is an inherently modern technique. It involves randomness, and it’s not a mistake this technique was discovered when attempting to find a solution to a problem involving probability and quantum mechanics. The ancients simply didn’t have the tools to discover this technique.
It’s like the solution to Fermat’s last theorem, or a numeric solution for
n > 2 in the equation
an + bn = cn . A solution was finally found by [Andrew Wiles] in the 1990s, but it was completely unlike any sort of math Fermat would have known of, or anyone else on the planet for that matter. We don’t know if Fermat actually solved this problem, or what his proof would be, but it would have been so simple anyone could understand it instead of [Wiles]’s deep dive into obscure maths.
Could Archimedes have calculated Pi to a greater precision than anyone else by throwing marbles at a circle and square traced out in the sand? No. The knowledge we have today, and what children are taught in grade school, is built upon thousands of years of the brightest minds working on the hardest problems. Flashes of genius are so rare on a species-wide scale that scientific and mathematical advancement happens at a snail’s pace. We should hope that we’re not judged too unkindly a few thousand years down the line — we simply didn’t know any better.
from Blog – Hackaday http://ift.tt/2Hz56NR