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

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

CC BY-SA 3.0
2013-07-25T04:21:18.807Z
uh huh which one?
vzn
CC BY-SA 3.0
2013-07-25T04:25:38.627Z
Try checking Ulam's selected works book: Sets, Numbers and Universes...
Phil
CC BY-SA 3.0
2013-07-25T04:44:34.030Z
A reference would really help.
Huck Bennett
CC BY-SA 3.0
2013-07-25T17:49:58.930Z
This link to a bibliography may help: http://math.fullerton.edu/mathews/n2003/montecarlopi/MonteCarloPiBib/Links/MonteCarloPiBib_lnk_3.html
Phil
CC BY-SA 3.0
2013-07-25T02:27:55.373Z
2013-07-25T02:27:55.373Z
Phil
<p>I'm sure everybody knows of <a href="http://en.wikipedia.org/wiki/Buffon%27s_needle" rel="nofollow">Buffon's needle</a> experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.</p>

<p>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.</p>

<p>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 &lt; 1$. In the end, the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$.</p>

<p>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?</p>

CC BY-SA 3.0
2012-07-01T03:09:56.000Z
Is this the right place to ask such questions? (Though I honestly don't have any real hope of finding an answer at all!)
Jérémie
CC BY-SA 3.0
2012-07-01T18:05:53.237Z
I think its the right place.
Tyson Williams
CC BY-SA 3.0
2012-07-02T07:50:20.147Z
IIRC, you can find the answer in the second chapter of first volume of The Art of Computer Programming by D.E. Knuth.
Kaveh
CC BY-SA 3.0
2012-07-02T15:23:04.017Z
@Kaveh: Thanks for the reference, but unfortunately I checked both the original and 1997 edition, and did not find anything. The index has a reference to "Monte Carlo" which indeed points to the second chapter (section 2.5), but nothing is said about simulating $\pi$ or the method I describe. :(
Jérémie
CC BY-SA 3.0
2012-07-03T05:38:54.427Z
agree with you that this is not same as buffon's method although a clever derivation might show they are equivalent. looking up this history, am amazed that nobody is credited. it seems to be a "folklore theorem". however it was likely discovered by the originators of monte carlo methods, ie ulam & von neumann around ~1944. von neumann did some of the 1st computerized calculations of pi. the methods were invented for atomic bomb calculations & it seems quite possible the origins of the method are even classified info...?
vzn
CC BY-SA 3.0
2012-07-05T22:06:11.860Z
@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"](http://www-apr.lip6.fr/~lumbroso/References/VonNeumann51.pdf) (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
CC BY-SA 3.0
2012-07-06T04:56:12.640Z
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
CC BY-SA 3.0
2013-07-26T03:27:39.250Z
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
CC BY-SA 3.0
2014-02-20T17:10:12.857Z
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
<ds.algorithms><reference-request><randomized-algorithms><ho.history-overview><monte-carlo>
Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?
Jérémie
# Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?

(Asked by: username_0 on 2012-07-01)

I'm sure everybody knows of [Buffon's needle](http://en.wikipedia.org/wiki/Buffon%27s_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?

**Tags:** ds.algorithms, reference-request, randomized-algorithms, ho.history-overview, monte-carlo
> **Comments:**
> **username_0**: Is this the right place to ask such questions? (Though I honestly don't have any real hope of finding an answer at all!)  
> **username_1**: I think its the right place.  
> **username_2**: IIRC, you can find the answer in the second chapter of first volume of The Art of Computer Programming by D.E. Knuth.  
> **username_0**: @Kaveh: Thanks for the reference, but unfortunately I checked both the original and 1997 edition, and did not find anything. The index has a reference to "Monte Carlo" which indeed points to the second chapter (section 2.5), but nothing is said about simulating $\pi$ or the method I describe. :(  
> **username_3**: agree with you that this is not same as buffon's method although a clever derivation might show they are equivalent. looking up this history, am amazed that nobody is credited. it seems to be a "folklore theorem". however it was likely discovered by the originators of monte carlo methods, ie ulam & von neumann around ~1944. von neumann did some of the 1st computerized calculations of pi. the methods were invented for atomic bomb calculations & it seems quite possible the origins of the method are even classified info...?  
> **username_0**: @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"](http://www-apr.lip6.fr/~lumbroso/References/VonNeumann51.pdf) (a favorite "paper" of mine). I do hope this information is not classified... though you may be right on this point as well.  
> **username_3**: 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.  
> **username_4**: 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$."  
> **username_5**: 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}$  

---

## 1 answers

### Answer by username_6 on 2013-07-25. Score: 2

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.

> **Comments:**
> **username_3**: uh huh which one?  
> **username_6**: Try checking Ulam's selected works book: Sets, Numbers and Universes...  
> **username_4**: A reference would really help.  
> **username_6**: This link to a bibliography may help: http://math.fullerton.edu/mathews/n2003/montecarlopi/MonteCarloPiBib/Links/MonteCarloPiBib_lnk_3.html  

---

