Buffon’s needle

  • Difficulty: 030/100
  • Author: jeremy theler
  • Keywords: PRINT, SKIP_STATIC_STEP, VAR, CONST, step_static, static_steps, pi, random, cos, floor,

Buffon’s needle is a classical probability problem that dates back from the XVIII century whose solution depends on the value of \(\pi\). When I first read about this problem in my high-school years, I could not believe two things. The first one, that the number \(\pi\) had something to do with the probability a stick has of crossing a line. And the other, that one would actually be able to compute \(\pi\) by throwing away sticks. Of course, this was long before I learned about calculus, distributions and Monte Carlo methods.

The problem consists of a table of length \(L\) over which transversal lines separated by a length \(d\) are drawn. A stick (needle) of length \(\ell\) is randomly thrown over the table. What is the probability \(p\) that the stick crosses one line?

A table with transversal lines 

For \(\ell < d\) the answer is

\[ p = \frac{ 2 \ell }{ \pi d} \]

To convince myself that the two facts I did not believe back when I was a youngster were actually true, I would just run the example below. Four experiments (I know that generating random numbers in a digital computer is not a real experiment, as neither is solving the equations of a chaotic natural convection loop. However, I could not come up with a better word) of ten millions throws each are simulated, and the experimental frequency is compared to the theoretical value. I am now convinced.

buffon.was

To solve the Buffon’s needle problem the Monte Carlo way, two random numbers are generated: the distance \(0 \leq x < L\) from one side of the table to the center of the thrown stick, and the angle \(0 \leq \theta < 2\pi\) with respect to the table longitudinal axis. One way of checking whether a stick crosses or not a line is the following. First, compute the location of both ends of the stick

\begin{align*} x_1 &= x + \frac{1}{2} \ell \cos(\theta) \\ x_2 &= x - \frac{1}{2} \ell \cos(\theta) \\ \end{align*}

Now, if the floor of \(x_1/d\) is equal to the floor of \(x_2/d\), the stick does not cross a line. Otherwise, it does.

The input file iteratively performs \(10^7\) throws and prints the partial frequency of crosses as a function of the number of throws, along with the constant analytical result. Four runs are performed, and the results are plotted in the figure.

VAR count           # number of times the stick crosses one line
static_steps = 1e7  # number of times we trow the stick

CONST L l d result

L = 10    # length of the table
l = 0.8   # length of the stick
d = 1     # distance between lines
result = 2*l/(pi*d) # expected theoretical result

x = random(0, L)          # location of the center of the stick
theta = random(0, 2*pi)   # the resulting angle

x1 = x + 0.5*l*cos(theta) # coordinates of the stick ends 
x2 = x - 0.5*l*cos(theta)

# increase count if the stick crosses one line
# (remember ! is the "not equal" operator)
count = count + (floor(x1/d)!floor(x2/d))

# print the partial results
PRINT %g step_static count/step_static result SKIP_STATIC_STEP 1e5
$ wasora buffon.was > experiment1.dat
$ wasora buffon.was > experiment2.dat
$ wasora buffon.was > experiment3.dat
$ wasora buffon.was > experiment4.dat
$ pyxplot buffon.ppl
$ 
buffon.png
buffon.png