Buffon’s needle

If a needle is dropped on a floor of parallel lines, how likely is it to cross one? For a needle of length \(l\) no longer than the spacing \(d\) between the lines, the probability is \(2l/(\pi d)\), so dropping needles and counting estimates \(\pi\). The answer extends to a bent needle, a noodle of any shape. Barbier showed that a curve of length \(L\) crosses \(2L/(\pi d)\) lines on average, however it is bent.

The example drops needles and noodles with planex2d and counts their intersections with the lines. The share of needles that cross must approach \(2l/(\pi d)\), the mean count of a noodle must approach \(2L/(\pi d)\), and a circle of diameter \(d\) must cross exactly twice at every drop.

import math
import random

import matplotlib.pyplot as plt
import planex as px

The floor and the needle

The lines lie \(d = 1\) apart, and the needle is \(l = 0.8\) long, so it crosses at most one line. The pattern repeats from line to line, so a drop needs only the height of the curve’s middle between two lines and its angle, both uniform. drop turns the curve about its middle by a random angle, lifts it by a random height between 0 and \(d\), and counts its intersections with the floor’s lines:

d, l = 1.0, 0.8
floor = [px.Line((-5, k * d), (5, k * d)) for k in range(-4, 6)]


def drop(curve, rng):
    """the curve dropped at a random angle and height, and the number of its crossings with the lines"""
    dropped = curve.Rotated((0, 0), rng.uniform(0, 360)).Translated((0, rng.uniform(0, d)))
    return dropped, sum(len(dropped.Intersections(line)) for line in floor)


rng = random.Random(1777)
needle = px.Line((-l / 2, 0), (l / 2, 0))

Thirty needles, spread along the floor for the picture, with those that cross a line in blue:

Estimating π

Over 200,000 needles, the crossings per drop must match \(2l/(\pi d)\) within their standard error, and the count gives an estimate of \(\pi\):

counts = [drop(needle, rng)[1] for _ in range(200000)]
P = sum(counts) / len(counts)
error = math.sqrt(P * (1 - P) / len(counts))
print("crossings per needle", P, "standard error", error, "| 2l/(πd)", 2 * l / (math.pi * d))
print("π from the needles", 2 * l / (d * P), "standard error", 2 * l / (d * P**2) * error)

crossings per needle 0.5101 standard error 0.0011178058641821485 | 2l/(πd) 0.5092958178940651
π from the needles 3.136639874534405 standard error 0.0068734649001805865

The share of crossing needles lies within one standard error of \(2l/(\pi d)\), and \(\pi\) comes out as 3.137, give or take 0.007.

The estimate improves only as one over the square root of the number of drops. A hundred times as many needles give one more correct digit of \(\pi\), which is why Buffon’s needle is a famous way to compute \(\pi\) but a slow one:

fig, ax = plt.subplots(figsize=(7, 3.4))
drops = [10**k for k in range(2, 6)] + [200000]
ax.semilogx(drops, [2 * l * n / (d * sum(counts[:n])) for n in drops], "o-", color=PLANEX, label="from the needles")
ax.axhline(math.pi, color=INK, lw=1, ls="--", label="π")
ax.set_xlabel("number of needles")
ax.set_ylabel("estimate of π")
ax.legend()
plt.show()

Buffon’s noodle

The noodle is a spline through five points, about 3.85 long, so it can cross several lines in one drop. A circle of diameter \(d\) has the length \(\pi d\), so it crosses \(2\pi d/(\pi d) = 2\) lines on average. Whatever its height, exactly one line runs through it, and it meets that line twice. The noodle’s mean count is compared with \(2L/(\pi d)\), and the circle’s count is printed for a thousand drops:

noodle = px.Spline([(-1.1, -0.2), (-0.5, 0.3), (0, -0.4), (0.5, 0.4), (1.1, -0.1)])
counts = [drop(noodle, rng)[1] for _ in range(50000)]
mean = sum(counts) / len(counts)
error = math.sqrt(sum((c - mean) ** 2 for c in counts) / (len(counts) - 1) / len(counts))
print("noodle of length", noodle.mass, "| crossings per drop", mean, "standard error", error,
      "| 2L/(πd)", 2 * noodle.mass / (math.pi * d))
circle = px.Circle((0, 0), d / 2)
print("circle: the counts at a thousand drops", sorted({drop(circle, rng)[1] for _ in range(1000)}))

noodle of length 3.854667256788794 | crossings per drop 2.45512 standard error 0.004264654670379437 | 2L/(πd) 2.4539573915696513
circle: the counts at a thousand drops [2]

See Boxes, crossings and open ends for Intersections.