Pages Menu
TwitterRssFacebook
Categories Menu

Posted by on Mar 14, 2013 in Damned Lies and Statistics, Uncategorized | 3 comments

Super quick and fairly dirty approximation of π

Happy Pi Day, everybody!

There are literally dozens of ways to compute π, ranging from geometrical approximations to series expansions to modern computational algorithms. I’m not going to go into all that here and now. Instead, for a quick and easy and above all probabilistic way to explain how to derive π to your kids, I’m going to suggest the analogy of a dartboard. If the dots on this chart were scattered uniformly at random throughout the square, what would be the probability that one of them falls inside the circle?

The area of the inscribed circle is π*r*r and the area of the square itself is 2r*2r, dividing the former by the latter we see that the ratio of the area of the circle to that of the square is π/4. Accordingly, the value of π can be approximated by throwing enough random dots at the square, computing how often they fall inside the circle, and multiplying by four. The law of large numbers should ensure that the computed average will converge upon the expected value in the long run, like so:

Sample mean of the ratio of in-circle hits, multiplied by four (n=10,000)

There, now wasn’t that fun? Way more than circumscribing polygons, I can tell you.

  • Chas Stewart

    Just audibly laughed! That was fun.

  • http://www.facebook.com/people/Thaumas-Themelios/100001074236927 Thaumas Themelios

    The general technique of using random or pseudo-random inputs to get fast approximations is called ‘stochastic’ in computer science (e.g. stochastic algorithms, stochastic optimization (this pi technique would fall under this specific heading), stochastic programming, etc.).

    Of course, a *really* quick way to approximate pi is to use one of its continued fractions approximations, e.g. 3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, etc. That last one gives pi to almost 10 decimal places, and only requires dividing two integers:

    104348 / 33215 =
    3.1415926539…
    pi =

    3.1415926535897932384626433832795…

    Further continued fractions rapidly generate more and more accurate approximations. The approximation 80143857 / 25510582 gives pi to about 16 decimal places, which is more accurate than most people need.

    So, while finding pi with stochastic techniques is *definitely* a good example of a neat technique and also an intuitive example of what pi ‘really means’, practically speaking this technique isn’t used for well-known numbers such as pi.

    Where it *is* used is in the *very similar* problem of approximating areas under the curves of *unknown* or hard to define functions (aka numerical integration in calculus). It’s especially used when you need to do *a lot* of little integrations, and you only need ‘pretty good’ integrations to get a good result.

    A classic example I learned in Uni is that of calculating areas and other attributes of the thousands of small triangles used in 3D rendering of shading, texture, light reflection, etc. in high-speed graphics applications. Of course that was years ago, and I don’t know if the technique is still used today, but you might be able to visualize the idea. Since a 3D figure might be quite a distance ‘away’ (in the 3D world/model), you don’t need to have 16 digit accuracy to see a little blue splotch (of a robot, let’s say) way off in the distance. It’s enough just to render it bluish and splotchy. So, you might use a stochastic technique to get a very approximate measure of how blue the distant robot is, how brightly light reflects off of it, etc.

    That way, you can render much more graphical detail, say in a computer game or flight simulator or whatever, because you can process many more 3D triangles (everything is made up of triangles in most 3D software, at least when I was learning about it). The user doesn’t care as much about these approximations because they are ‘good enough’ for the game, rather than being super-accurate perfectly rendered graphics that *still* would end up becoming little blue splotches on a human retina.

    • http://skepticink.com/backgroundprobability/ Damion Reinhardt

      Just to be clear, when I said “super quick” I did not mean in the technical sense of rapid convergence — http://en.wikipedia.org/wiki/Pi#Rapidly_convergent_series

      Of course, for most real world applications you shouldn’t need more than 40 digits.