← Can tidy dots help you find a circle’s secret number?

experiment.py

Python · 291 lines · Download raw ·

1"""
2Estimate pi by dropping points into the unit square and counting how many
3land inside the quarter circle x^2 + y^2 <= 1.
4
5We compare two ways of choosing the points:
6
7 1. Random points (plain Monte Carlo, "MC")
8 2. Evenly spread points (Halton sequence with a random shift, "RQMC")
9
10For each number of points N = 64, 128, ..., 2^30 (about a billion) we repeat
11the estimate 50 times and record the average absolute error |estimate - pi|.
12The points are made and counted on a GPU in chunks, so a billion points never
13have to fit in memory at once. Without a GPU it falls back to the CPU (set
14MAX_POWER=20 to keep that quick).
15
16Outputs:
17 results.csv one row per N with the mean error and its spread for both methods
18 error.png log-log plot of error vs. N
19 darts.png 256 random points next to 256 evenly spread points
20 race.png how many times more accurate the evenly spread points are, per N
21 guesses.png the guess for pi from the first try of each method, next to the real pi
22
23The last line printed is a JSON summary of the headline numbers.
24
25Run:
26 python3 experiment.py
27"""
28
29import csv
30import json
31import os
32import platform
33import time
34
35import matplotlib
36import numpy as np
37import torch
38
39matplotlib.use("Agg") # draw to a file, no window needed
40import matplotlib.pyplot as plt
41
42# ---------------------------------------------------------------------------
43# Settings
44# ---------------------------------------------------------------------------
45
46MAX_POWER = int(os.environ.get("MAX_POWER", 30)) # largest N is 2^MAX_POWER
47POINT_COUNTS = [2**k for k in range(6, MAX_POWER + 1)]
48NUM_SEEDS = 50 # repetitions per N (gives error bars)
49CHUNK = 2**24 # points handled at once (memory limit)
50DEVICE = "cuda" if torch.cuda.is_available() else "cpu"
51
52
53# ---------------------------------------------------------------------------
54# Building blocks
55# ---------------------------------------------------------------------------
56
57def inside_circle(x, y):
58 """True for each point inside the quarter circle (distance from the corner <= 1)."""
59 return x * x + y * y <= 1.0
60
61
62def van_der_corput(start, n, base):
63 """Numbers start+1 .. start+n of the van der Corput sequence in the given base.
64
65 Recipe for the i-th number: write i in `base`, then mirror its digits
66 around the decimal point. Example in base 2: i = 6 = 110 -> 0.011 = 0.375.
67 The result fills [0, 1) evenly instead of randomly.
68 """
69 index = torch.arange(start + 1, start + n + 1, device=DEVICE, dtype=torch.int64)
70 result = torch.zeros(n, device=DEVICE, dtype=torch.float64)
71 digit_weight = 1.0 / base # value of the first digit after the point
72 while bool((index > 0).any()):
73 result += digit_weight * (index % base)
74 index //= base # drop the digit we just used
75 digit_weight /= base # the next digit is worth `base` times less
76 return result
77
78
79def halton_points(start, n):
80 """Points start+1 .. start+n of the 2-D Halton sequence: base 2 for x, base 3 for y."""
81 return van_der_corput(start, n, 2), van_der_corput(start, n, 3)
82
83
84def random_shift(x, y, shift):
85 """Move every point by the same random offset and wrap around the square.
86
87 This is the Cranley-Patterson rotation: the points stay evenly spread,
88 but the estimate becomes random and unbiased, so we can measure its error.
89 """
90 return (x + shift[0]) % 1.0, (y + shift[1]) % 1.0
91
92
93def counts_at_checkpoints(inside, start, checkpoints):
94 """How many points are inside after each checkpoint N that falls in this chunk.
95
96 `inside` covers points start+1 .. start+len(inside). Returns {N: count within chunk}.
97 """
98 running = torch.cumsum(inside, dim=0, dtype=torch.int64)
99 return {n: int(running[n - start - 1]) for n in checkpoints if start < n <= start + len(inside)}
100
101
102# ---------------------------------------------------------------------------
103# Experiment
104# ---------------------------------------------------------------------------
105
106def run_experiment():
107 """Return one dict per N with mean/std of |estimate - pi| for both methods."""
108 total = max(POINT_COUNTS)
109 # One random-number stream per repetition, plus that repetition's Halton shift
110 streams = [torch.Generator(device=DEVICE).manual_seed(seed) for seed in range(NUM_SEEDS)]
111 shifts = [torch.rand(2, generator=g, device=DEVICE, dtype=torch.float64) for g in streams]
112 mc_inside = np.zeros((NUM_SEEDS, len(POINT_COUNTS)), dtype=np.int64)
113 rqmc_inside = np.zeros_like(mc_inside)
114 mc_total = np.zeros(NUM_SEEDS, dtype=np.int64)
115 rqmc_total = np.zeros(NUM_SEEDS, dtype=np.int64)
116
117 for start in range(0, total, CHUNK):
118 n = min(CHUNK, total - start)
119 hx, hy = halton_points(start, n) # the same Halton points serve every repetition
120 for seed, g in enumerate(streams):
121 # 1. Random points
122 x = torch.rand(n, generator=g, device=DEVICE, dtype=torch.float64)
123 y = torch.rand(n, generator=g, device=DEVICE, dtype=torch.float64)
124 inside = inside_circle(x, y)
125 for col, c in _by_column(counts_at_checkpoints(inside, start, POINT_COUNTS)):
126 mc_inside[seed, col] = mc_total[seed] + c
127 mc_total[seed] += int(inside.sum())
128
129 # 2. Evenly spread points, randomly shifted
130 sx, sy = random_shift(hx, hy, shifts[seed])
131 inside = inside_circle(sx, sy)
132 for col, c in _by_column(counts_at_checkpoints(inside, start, POINT_COUNTS)):
133 rqmc_inside[seed, col] = rqmc_total[seed] + c
134 rqmc_total[seed] += int(inside.sum())
135
136 rows = []
137 for col, n in enumerate(POINT_COUNTS):
138 mc_err = np.abs(4.0 * mc_inside[:, col] / n - np.pi)
139 rqmc_err = np.abs(4.0 * rqmc_inside[:, col] / n - np.pi)
140 rows.append({
141 "n": n,
142 "mc_mean_abs_err": mc_err.mean(),
143 "mc_std": mc_err.std(),
144 "rqmc_mean_abs_err": rqmc_err.mean(),
145 "rqmc_std": rqmc_err.std(),
146 # the actual guesses from the first of the 50 tries, to compare with the real pi
147 "mc_guess_try1": 4.0 * mc_inside[0, col] / n,
148 "rqmc_guess_try1": 4.0 * rqmc_inside[0, col] / n,
149 })
150 return rows
151
152
153def _by_column(found):
154 """Turn {N: count} into (column index, count) pairs for the results table."""
155 return ((POINT_COUNTS.index(n), c) for n, c in found.items())
156
157
158def fitted_slope(n, err):
159 """Slope of log(error) vs. log(N): -0.5 means error ~ N^-0.5, -1 means ~ N^-1."""
160 return np.polyfit(np.log(n), np.log(err), 1)[0]
161
162
163# ---------------------------------------------------------------------------
164# Output
165# ---------------------------------------------------------------------------
166
167def save_csv(rows, path="results.csv"):
168 with open(path, "w", newline="") as f:
169 writer = csv.DictWriter(f, fieldnames=rows[0].keys())
170 writer.writeheader()
171 for row in rows:
172 writer.writerow({k: (f"{v:.10f}" if "guess" in k else f"{v:.6g}" if isinstance(v, float) else v) for k, v in row.items()})
173
174
175def save_plot(n, mc, rqmc, slope_mc, slope_rqmc, path="error.png"):
176 fig, ax = plt.subplots(figsize=(6.4, 4.2), dpi=160)
177 ax.loglog(n, mc, "o-", color="#2557a7", ms=4, label=f"Random points (slope {slope_mc:.2f})")
178 ax.loglog(n, rqmc, "s-", color="#c2410c", ms=4, label=f"Shifted Halton points (slope {slope_rqmc:.2f})")
179 # Dotted guide lines with the textbook rates, starting from the first data point
180 ax.loglog(n, mc[0] * np.sqrt(n[0] / n), ":", color="#2557a7", alpha=0.6, label=r"$\propto N^{-1/2}$")
181 ax.loglog(n, rqmc[0] * (n[0] / n), ":", color="#c2410c", alpha=0.6, label=r"$\propto N^{-1}$")
182 ax.set_xlabel("number of points $N$")
183 ax.set_ylabel(rf"mean $|\hat\pi - \pi|$ over {NUM_SEEDS} tries")
184 ax.grid(True, which="major", alpha=0.3)
185 ax.legend(frameon=False, fontsize=9)
186 fig.tight_layout()
187 fig.savefig(path, facecolor="white")
188
189
190def save_darts_picture(n=256, path="darts.png"):
191 """Draw n random points next to n evenly spread (Halton) points."""
192 rng = np.random.default_rng(2026) # its own generator: does not change results.csv
193 hx, hy = (t.cpu().numpy() for t in halton_points(0, n))
194 pictures = [("Random darts", rng.random(n), rng.random(n), "#2557a7"),
195 ("Evenly spread darts", hx, hy, "#c2410c")]
196 fig, axes = plt.subplots(1, 2, figsize=(7.2, 4.2), dpi=160, layout="constrained")
197 t = np.linspace(0, np.pi / 2, 200)
198 for ax, (title, x, y, color) in zip(axes, pictures):
199 inside = x * x + y * y <= 1.0
200 ax.scatter(x[inside], y[inside], s=10, color=color)
201 ax.scatter(x[~inside], y[~inside], s=10, facecolors="none", edgecolors=color)
202 ax.plot(np.cos(t), np.sin(t), color="black", lw=1.5)
203 ax.set(xlim=(0, 1), ylim=(0, 1), aspect="equal", xticks=[], yticks=[])
204 ax.set_title(f"{title}\n{inside.sum()} of {n} inside, so π ≈ {4 * inside.mean():.3f}", fontsize=10)
205 fig.savefig(path, facecolor="white")
206
207
208def save_guesses_chart(rows, path="guesses.png"):
209 """The first try's guess for pi with each method, as darts are added, next to the real pi."""
210 n = np.array([r["n"] for r in rows])
211 fig, ax = plt.subplots(figsize=(6.8, 4.0), dpi=160)
212 ax.axhline(np.pi, color="#111827", lw=1.2, ls="--", label="real π = 3.14159265…")
213 ax.semilogx(n, [r["mc_guess_try1"] for r in rows], "o-", color="#2557a7", ms=4, label="random darts' guess")
214 ax.semilogx(n, [r["rqmc_guess_try1"] for r in rows], "s-", color="#c2410c", ms=4, label="Halton darts' guess")
215 ticks = [t for t in (100, 10_000, 1_000_000, 100_000_000) if t <= n[-1]]
216 ax.set_xticks(ticks, [{100: "100", 10_000: "10 thousand", 1_000_000: "1 million", 100_000_000: "100 million"}[t] for t in ticks])
217 ax.minorticks_off()
218 ax.set_xlabel("number of darts")
219 ax.set_ylabel("guess for π")
220 ax.grid(True, alpha=0.3)
221 ax.legend(frameon=False)
222 ax.spines[["top", "right"]].set_visible(False)
223 fig.tight_layout()
224 fig.savefig(path, facecolor="white")
225
226
227def save_race_chart(rows, path="race.png"):
228 """Bar chart: how many times smaller the evenly spread error is, for a few N."""
229 picks = [r for r in rows if r["n"] in (64, 4096, 262144, 16777216, 1073741824)]
230 labels = [f"{r['n']:,}" for r in picks]
231 ratios = [r["mc_mean_abs_err"] / r["rqmc_mean_abs_err"] for r in picks]
232 fig, ax = plt.subplots(figsize=(6.8, 3.8), dpi=160)
233 bars = ax.bar(labels, ratios, color="#c2410c")
234 ax.bar_label(bars, labels=[f"{v:.0f}x" if v >= 10 else f"{v:.1f}x" for v in ratios], padding=3)
235 ax.set_xlabel("number of darts")
236 ax.set_ylabel("times more accurate")
237 ax.set_ylim(0, max(ratios) * 1.2)
238 ax.spines[["top", "right"]].set_visible(False)
239 fig.tight_layout()
240 fig.savefig(path, facecolor="white")
241
242
243def main():
244 began = time.time()
245 rows = run_experiment()
246 seconds = time.time() - began
247 save_csv(rows)
248
249 n = np.array([r["n"] for r in rows])
250 mc = np.array([r["mc_mean_abs_err"] for r in rows])
251 rqmc = np.array([r["rqmc_mean_abs_err"] for r in rows])
252 slope_mc, slope_rqmc = fitted_slope(n, mc), fitted_slope(n, rqmc)
253
254 print(f"device: {torch.cuda.get_device_name(0) if DEVICE == 'cuda' else platform.processor() or 'cpu'}")
255 print(f"fitted slope random: {slope_mc:.3f} halton: {slope_rqmc:.3f} ({seconds:.0f} s)")
256 print(f"{'N':>12} {'random err':>10} {'halton err':>10} {'halton better by':>16}")
257 for r in rows:
258 ratio = r["mc_mean_abs_err"] / r["rqmc_mean_abs_err"]
259 print(f"{r['n']:>12} {r['mc_mean_abs_err']:>10.2e} {r['rqmc_mean_abs_err']:>10.2e} {ratio:>15.1f}x")
260
261 save_plot(n, mc, rqmc, slope_mc, slope_rqmc)
262 save_darts_picture()
263 save_race_chart(rows)
264 save_guesses_chart(rows)
265
266 # Final line: machine-readable summary (kept by Delta as result_summary)
267 by_n = {r["n"]: r for r in rows}
268 summary = {
269 "device": torch.cuda.get_device_name(0) if DEVICE == "cuda" else "cpu",
270 "max_darts": int(n[-1]),
271 "seconds": round(seconds, 1),
272 "slope_random": round(float(slope_mc), 2),
273 "slope_halton": round(float(slope_rqmc), 2),
274 }
275 for label, size in (("262k", 2**18), ("1b", 2**30)):
276 if size in by_n:
277 r = by_n[size]
278 summary[f"random_error_{label}"] = float(f"{r['mc_mean_abs_err']:.2g}")
279 summary[f"halton_error_{label}"] = float(f"{r['rqmc_mean_abs_err']:.2g}")
280 summary[f"better_by_{label}"] = round(float(r["mc_mean_abs_err"] / r["rqmc_mean_abs_err"]), 1)
281 # first try's guesses at a few sizes, to set side by side with the real pi
282 summary["pi_true"] = round(float(np.pi), 10)
283 for label, size in (("64", 2**6), ("4k", 2**12), ("262k", 2**18), ("16m", 2**24), ("1b", 2**30)):
284 if size in by_n:
285 summary[f"guess_random_{label}"] = round(float(by_n[size]["mc_guess_try1"]), 10)
286 summary[f"guess_halton_{label}"] = round(float(by_n[size]["rqmc_guess_try1"]), 10)
287 print(json.dumps(summary))
288
289
290if __name__ == "__main__":
291 main()