# 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. – Tyson Williams 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. – Jérémie 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$." – Huck Bennett 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}$ – dspyz Feb 20 '14 at 17:10