# Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?

I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.

The implementation of the algorithm in computers usually calls for the use of $\pi$, or a trigonometric function, which, even if they are implemented as truncated series, sort of defeats the purpose.

To circumvent this issue, there is the well-known rejection-method algorithm: draw coordinates in the unit square, and see whether they belong to the unit quarter circle. This consists in drawing two uniform reals $x$ and $y$ in (0,1), and counting them only if $x^2+y^2 < 1$. In the end, the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$.

This second algorithm is usually passed off as Buffon's needle, thought it is considerably different. Unfortunately, I have not been able to track down who originated it. Does anybody have any information (documented, or at worst undocumented) as to who/when this idea originated?

• I think its the right place. Jul 1 '12 at 18:05
• @vzn: Thank you for your comment! Indeed this is what I believe, especially considered Von Neumann's other experiments, in particular those summarized in "Various Techniques Used in Connection With Random Digits" (a favorite "paper" of mine). I do hope this information is not classified... though you may be right on this point as well. Jul 5 '12 at 22:06
• by the way there is a closely related algorithm where one just uses all the $n^2$ points on a equally spaced unit square grid, $n$ points on a side, where the unit distance is chosen "small" relative to the radius of the circle. also, legitimately, there must definitely be a "first" citation somewhere in the literature, but I cant find it so far. there is a good book "history of Pi" by peter beckman, some of which is online, and I dont see it credited in the online part [google books]. wonder if it is in the offline part? this is also one of my favorite example monte carlo problems.
– vzn
Jul 6 '12 at 4:56
• Minor nit: $\pi$ should be $\pi/4$ in "the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$." Jul 26 '13 at 3:27
• For a really quirky one, take two random uniform numbers between 0 and 1 and then take their quotient. Estimate the probability it's closer to an even number than an odd number. This should be $\frac{\pi - 1}{4}$ Feb 20 '14 at 17:10

The Monte-Carlo method is usually attributed to Metropolis and Ulam, the latter was a mathematician on the Manhattan project.

If my memory is good, Ulam published a paper where he computes pi using the algorithm.

• uh huh which one?
– vzn
Jul 25 '13 at 4:21
• Try checking Ulam's selected works book: Sets, Numbers and Universes...
– Phil
Jul 25 '13 at 4:25
• A reference would really help. Jul 25 '13 at 4:44
• This link to a bibliography may help: math.fullerton.edu/mathews/n2003/montecarlopi/MonteCarloPiBib/…
– Phil
Jul 25 '13 at 17:49