Following the algorithms line, there’s one I love to see in action, and that’s the PI calculator using monte carlo.
Using the arctan formula is too simple and not funny at all, we need something less obvious.
So, get a disk of radius 1, the area of that disk is PI * R² but, as the R = 1, the area is PI. You could integrate the function y = sqrt(1 – x²) from -1 to 1 and multiply by 2 and voilá, you have PI. There are loads of integration methods available (brute-force, trapezoid, Simpson, Romberg) and the later generate very acurate results but that’s still not funny.
So, let’s integrate the disk on a different way: Monte Carlo. This method, named (and popularized) by guys like Enrico Fermi, Metropolis and John von Neumann is based on randomness. You already know that, to integrate a function you have to sum every “point” from start to finish. Monte Carlo assumes that it makes no difference if you do it sequential or random. (what makes a lot of sense to me ;).
The algorithm was proved to converge to the correct solution but that’s not all, it was proved that the accuracy is independent of the dimension of your space!! So, if you have a disk to integrate on 2 or a one billion dimensions space, the same accuracy will be achieved with the same number of points.
With an image it’d be easier to understand but try to draw a circumference using points. If you put 6 points, one after the other you’ll have a little arc. But, if you put it equally spaced on the circumference you’ll have a hexagon, which is much closer to a circumference than a little arc.
If you have random points, the probability of having something spaced rather than a little arc is much bigger, so, using random points you have a better result earlier.
Well, back to the PI assuming we don’t know yet the area of that disk. You do know the area of a square of side 2, which is 4. So, if you put such square centred behind the disk it’ll fit perfectly (the diameter of the disk is also 2) you’ll see the four corners of the square. If you start shooting at that target, the probability of hitting the disk is proportional to it’s area related to the square’s area.
So, 4 is to the area of the disk as the total number of hits is to the number of hits on the disk. That’s it. Start shooting, divide the disk hits by the total and you have the area of the disk, which is PI.
The source code is sooo simple anyone can understand, really, and it’s here: PIMC