Walkthrough — Module 04: Random Numbers

Read this AFTER a stage is green — it explains how the reference solution is built and why.

Stage 1: The linear congruential method

The Lcg struct carries Knuth's four magic quantities (x, a, c, m), and the one design decision that pays off repeatedly is encoding the word-size modulus 2^64 as m == 0. That lets next branch once: for m == 0 it uses wrapping_mul/wrapping_add, since the machine's 64-bit overflow is reduction mod 2^64; for m > 0 it widens to u128 before multiplying so a*x + c cannot overflow before the % m. The constructor reduces seed and parameters mod m (except in the 2^64 case) to keep everything canonical. period uses direct cycle detection with a first_seen array rather than Floyd's tortoise-and-hare, because with the modulus in hand the array is O(m) time and space and returns the exact cycle length — and crucially it counts only the cycle, not the tail, which matters when gcd(a, m) > 1 makes the map non-injective and real tails appear. The assert!(m <= 1<<26) keeps that array affordable. The reference tests turn Theorem 3.2.1.2A into checks: full period for m = 16 exactly when a ∈ {1,5,9,13} and c odd, and even the RANDU planes identity x_{n+2} - 6x_{n+1} + 9x_n ≡ 0.

Stage 2: The chi-square test

chi_square is a direct transcription of the §3.3.1 formula, and its value is mostly in the guards it asserts: equal-length slices, non-empty, and every expected count strictly positive — because a zero expected count is both a division-by-zero and a sign the caller violated Knuth's "merge sparse categories so each n*p_s is reasonably large" rule. Writing it as a zip().map().sum() over (obs - exp)^2 / exp keeps it a clean one-liner with no accumulator bugs. chi_square_uniform is layered on top: it sums the counts to get n, sets every expected count to n/k, and delegates — so there is a single implementation of the statistic and the uniform case can't drift from the general one. The test confirms the two agree on the same data, which is the right contract to pin.

Stage 3: Shuffling

shuffle is Algorithm P with the signature choice that unlocks the whole module: rng: &mut impl FnMut(u64) -> u64 returning a value in 0..bound. That injected closure is why the tests can drive the shuffle with a fixed tape of draws and enumerate every outcome. The correctness argument is structural: position j swaps only with 0..=j, a shrinking range, so the sequence of draws rng(t), rng(t-1), ..., rng(2) is a bijection onto the t! permutations — each permutation is produced by exactly one tape, hence uniform. The reference proves this for n = 3 by showing all 6 tapes give 6 distinct results. naive_shuffle is kept deliberately, as the cautionary counter-example: swapping position i with the full range 0..n gives n^n equally likely tapes, and since n^n is not divisible by n! for n > 2, the permutations cannot be equiprobable — the test pins the biased 4/5/5/5/4/4 distribution over the 27 tapes for n = 3. The idiom worth stealing: to unit-test a randomized algorithm, thread the randomness through a closure and enumerate the finite tape space.

Stage 4: Reservoir sampling

reservoir_sample takes an IntoIterator stream and the same injectable rng, and its structure follows Algorithm R exactly. The priming loop fills the reservoir with the first k records and — importantly — returns early with everything read if the stream is shorter than k, so a short stream degrades gracefully; k == 0 returns empty without ever consulting rng (the test asserts rng is never called). The steady state is the elegant part: for record number t, draw M uniform in 0..t, and if M < k overwrite reservoir[M]. The invariant, proved by induction in the lesson, is that after t records each has probability exactly k/t of being held; the new record enters with probability k/t and, when it does, evicts a uniformly random incumbent, which keeps every survivor at k/t too. Because it makes one pass and holds only k items, it works on streams whose length is unknown in advance — the property a two-pass or "collect then sample" approach cannot offer. The test enumerates all 12 tapes for n = 4, k = 2 and confirms each of the 6 two-element subsets arises exactly twice: exact uniformity, not just asymptotic.