← All Cracked Math projects
PM-I01NOT STARTEDINTERMEDIATEMATHPYTHONIMPACT ★★☆☆☆

Break RANDU, build PCG32, sample anything

Write a statistical test battery that catches a famous bad random number generator (RNG), then estimate a one-in-a-billion event with 10^5 samples.

EST.9 h
REWARD+300 XP
AFTERPCG + 2

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Battery p-values per generator; relative error of the P(Z > 6) estimate at a fixed sample budget (Z is a standard normal variable)
GOAL · The battery flags RANDU with p < 1e-10 while PCG32 passes. PCG32 output is bit-exact with the reference implementation. P(Z > 6) is estimated within 1% using <= 10^5 samples (naive MC would need ~10^13).
TestU01 batteries (L'Ecuyer & Simard) and NumPy's PCG64 · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Implement four random number generators: RANDU (a famously flawed generator), a 64-bit LCG (linear congruential generator, x -> a*x + c modulo 2^64), xorshift and PCG32, vectorised in NumPy uint64. Write a small test battery that looks for hidden patterns: chi-square (are values evenly spread), serial (are consecutive pairs evenly spread), birthday spacings, the 3D-plane/spectral test (RANDU's consecutive triples fall on just 15 planes in 3D) and Kolmogorov-Smirnov (does the sample match the target distribution). On top, build three samplers: inverse-CDF (push uniform numbers through the inverse cumulative distribution function), the alias method (constant-time sampling from a discrete distribution using a precomputed table) and rejection sampling (propose a value and accept it with a computed probability). Add an exponentially tilted importance sampler for Gaussian tail probabilities: draw samples shifted toward the rare tail, then reweight them so the estimate stays unbiased.

Approach

Start with RANDU, because its flaw is pure algebra. It computes xn+1=65539 xn mod 231x_{n+1} = 65539\,x_n \bmod 2^{31}. Since 65539=216+365539 = 2^{16} + 3, squaring gives 655392≡6⋅65539−9(mod231)65539^2 \equiv 6 \cdot 65539 - 9 \pmod{2^{31}}, so every output is fixed by the two before it:

xn+2=6xn+1−9xn(mod231).x_{n+2} = 6x_{n+1} - 9x_n \pmod{2^{31}}.

Divide by 2312^{31} and you get 9un−6un+1+un+2=k9u_n - 6u_{n+1} + u_{n+2} = k for a whole number kk. With every uu in [0,1)[0, 1), only k=−5,…,9k = -5, \dots, 9 are possible: 15 parallel planes. Your 3D test has to see that structure without being told the formula.

PCG32 hides the LCG inside it. The state still moves by s←as+c mod 264s \leftarrow a s + c \bmod 2^{64}, but the output is a scrambled view of the old state: xor the state with itself shifted right 18 bits, shift right 27 bits, keep 32 bits, then rotate right by the top 5 bits of the state (s≫59s \gg 59). Get the order of operations exactly as in the reference code, or you will be close but never bit-exact.

For the rare event, plain Monte Carlo is hopeless: p=P(Z>6)≈9.87×10−10p = P(Z > 6) \approx 9.87 \times 10^{-10}, and 1% relative error needs about 1/(p⋅10−4)≈10131/(p \cdot 10^{-4}) \approx 10^{13} samples. Instead draw X∼N(t,1)X \sim \mathcal N(t, 1) and weight each hit by the density ratio:

p^=1n∑i=1n1[Xi>6] e−tXi+t2/2,Var⁡p^p2=1n(et2 Φˉ(6+t)p2−1),\hat p = \frac1n \sum_{i=1}^n \mathbf 1[X_i > 6]\, e^{-tX_i + t^2/2}, \qquad \frac{\operatorname{Var}\hat p}{p^2} = \frac{1}{n}\left(\frac{e^{t^2}\,\bar\Phi(6 + t)}{p^2} - 1\right),

where Φˉ\bar\Phi is the standard normal tail. Derive the variance yourself before trusting it; it decides your sample budget.

VISUALFig. 1
RANDU -5 0 5 9 01 PCG32 -5 0 5 9 01 horizontal: 9u(n) − 6u(n+1) + u(n+2) · vertical: u(n+1) · 600 triples each 15 vertical lines: 15 planes a smooth smear: no planes in this direction
600 consecutive triples from each generator, seen edge-on along the direction (9, −6, 1). RANDU's triples fall on exactly 15 lines; PCG32's spread out smoothly. Why it's here: It shows what the 3D test is hunting for, and why a 1D or 2D test can pass RANDU.

Where people get stuck

  • Silent float promotion. In NumPy 1.x, mixing uint64 with a Python int or int64 can turn the whole expression into float64 and destroy the low bits. Keep every constant as np.uint64 and check the dtype after each step.
  • Rotations by zero. The rotate uses a left shift by (-rot) & 31. Do it in 64-bit and mask to 32 bits afterwards, so a shift of 32 never happens.
  • Uniforms that hit 0. Dividing a 32-bit integer by 2322^{32} can give exactly 0, and an inverse CDF then returns infinity. Use (k+0.5)/232(k + 0.5)/2^{32}.
  • Multiple testing. Five tests on four generators means some p-values below 0.05 by chance alone. A tiny p-value counts; a single 0.03 does not.
  • One lucky run. With the shift t=6t = 6 the formula above gives a relative standard deviation of about 0.83% at n=105n = 10^5. That is close to the 1% target, so roughly one run in five misses it (measured locally: 78% of 200 seeds landed inside). Check across many seeds, and consider a better proposal.
HINT · OBJECTIVE 3
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 6
Stuck? Hints stay hidden until you ask.

Objectives

0 / 7 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. The battery flags RANDU with p < 1e-10 while PCG32 passes; PCG32 output is bit-exact with the reference implementation; P(Z > 6) is estimated within 1% using at most 10^5 samples. Record the median relative error over seeds with `python tools/mlarena.py record PM-I01 "<relative error>"`.
  2. Battery p-values on NumPy's PCG64 pass a uniformity check, so a failure means the generator, not the test.
  3. At least 95 of 100 independent seeds land within 1% of scipy.stats.norm.sf(6) at n = 10^5.

Side quests

Replace the mean shift with a proposal shaped like the tail itself, such as 6 + Exponential(rate 6). Measure how much the relative variance drops and explain why.
Run TestU01's SmallCrush on your PCG32 and on RANDU through a small C wrapper, and compare its verdicts with your battery.

Terms in plain words

LCG (linear congruential generator)
A random number generator that repeatedly computes x = a*x + c modulo m; fast, but with patterns that tests can detect.
Test battery and p-value
A set of statistical tests run on a generator's output; a tiny p-value means the output is very unlikely to be truly random.
Importance sampling
Sampling from a different distribution that hits the region you care about more often, then reweighting each sample to correct for that.
Exponential tilting
A specific way to build the importance distribution by multiplying the density by e^(t x), which shifts a Gaussian toward its tail.
Alias method
A table-based trick that samples from any discrete distribution in constant time per draw.

Why it rates ★★☆☆☆

Solid fundamentals. The importance-sampling result is the part that transfers to ML.