← Can tidy dots help you find a circle’s secret number?
experiment.py
| 1 | """ |
| 2 | Estimate pi by dropping points into the unit square and counting how many |
| 3 | land inside the quarter circle x^2 + y^2 <= 1. |
| 4 | |
| 5 | We 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 | |
| 10 | For each number of points N = 64, 128, ..., 2^30 (about a billion) we repeat |
| 11 | the estimate 50 times and record the average absolute error |estimate - pi|. |
| 12 | The points are made and counted on a GPU in chunks, so a billion points never |
| 13 | have to fit in memory at once. Without a GPU it falls back to the CPU (set |
| 14 | MAX_POWER=20 to keep that quick). |
| 15 | |
| 16 | Outputs: |
| 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 | |
| 23 | The last line printed is a JSON summary of the headline numbers. |
| 24 | |
| 25 | Run: |
| 26 | python3 experiment.py |
| 27 | """ |
| 28 | |
| 29 | import csv |
| 30 | import json |
| 31 | import os |
| 32 | import platform |
| 33 | import time |
| 34 | |
| 35 | import matplotlib |
| 36 | import numpy as np |
| 37 | import torch |
| 38 | |
| 39 | matplotlib.use("Agg") # draw to a file, no window needed |
| 40 | import matplotlib.pyplot as plt |
| 41 | |
| 42 | # --------------------------------------------------------------------------- |
| 43 | # Settings |
| 44 | # --------------------------------------------------------------------------- |
| 45 | |
| 46 | MAX_POWER = int(os.environ.get("MAX_POWER", 30)) # largest N is 2^MAX_POWER |
| 47 | POINT_COUNTS = [2**k for k in range(6, MAX_POWER + 1)] |
| 48 | NUM_SEEDS = 50 # repetitions per N (gives error bars) |
| 49 | CHUNK = 2**24 # points handled at once (memory limit) |
| 50 | DEVICE = "cuda" if torch.cuda.is_available() else "cpu" |
| 51 | |
| 52 | |
| 53 | # --------------------------------------------------------------------------- |
| 54 | # Building blocks |
| 55 | # --------------------------------------------------------------------------- |
| 56 | |
| 57 | def 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 | |
| 62 | def 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 | |
| 79 | def 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 | |
| 84 | def 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 | |
| 93 | def 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 | |
| 106 | def 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 | |
| 153 | def _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 | |
| 158 | def 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 | |
| 167 | def 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 | |
| 175 | def 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 | |
| 190 | def 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 | |
| 208 | def 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 | |
| 227 | def 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 | |
| 243 | def 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 | |
| 290 | if __name__ == "__main__": |
| 291 | main() |