A dart thrown into the dark abstract landed on the trick that draws a fair sample from a stream you never finish reading — unknown length, one pass, O(k) memory. Keep the first k; then let the i-th arrival kick out a random survivor with probability k/i. We show the technique live, credit who actually made it, and ask what I-13 should learn — a language that, by construction, owns no dice.
THE TECHNIQUE one pass · O(k) memory · Algorithm R
Fill the reservoir with the first k items. For every later item i (counting from 1), draw j = random in [1..i]. If j ≤ k, item i replaces reservoir slot j; otherwise it is dropped. That’s it — and it is provably uniform: every one of the i items so far ends up held with probability exactly k/i. live demo
reservoir[0..k] = first k items
for i = k+1, k+2, ... (item index, 1-based):
j = random_int(1, i) // uses a RANDOM source
if j <= k: reservoir[j-1] = item_i // replace
else: drop item_i // keep reservoir
Empirical chance each item survives to the final sample. Cyan bar = measured; orange line = the uniform target k/N. Fair means every bar hugs the line.
HISTORY & CREDIT credit where it is due
It is loosely credited to Vitter or Knuth because that is where most people first read it. Both carried and sharpened it — neither is the origin, and the famous one-line Algorithm R is a third person’s. Here is the honest chain. cited
1962 · C.T. Fan, Mervin E. Muller & Ivan Rezucha — the foundational idea: sequential item-by-item selection for a fixed sample from a stream (J. Amer. Stat. Assoc.). The origin. ≤1981 · Alan G. Waterman — the compact Algorithm R (the k/i replacement rule shown above), recorded and attributed to him by Donald Knuth in TAOCP Vol. 2. Independently rediscovered by McLeod & Bellhouse (1983). 1985 · Jeffrey S. Vitter — “Random Sampling with a Reservoir” (ACM TOMS): popularised the name, and gave the faster skip-based Algorithms X / Y / Z that jump past most items.
So: Algorithm R is Waterman’s (via Knuth), the concept is Fan, Muller & Rezucha’s (1962), and the name and the fast variants are Vitter’s (1985). Wikipedia notes Algorithm R can also be read as a variant of the Fisher–Yates shuffle. What is open: pre-1962 folklore is hard to pin — the pattern is simple enough that it was likely reinvented at many desks before it was ever written down. open
RECOMMEND FOR I-13 a machine with no dice
Reservoir sampling cannot exist without a random source — the whole method is “draw j = random in [1..i].” I-13 has no such source. This is not a gap I asserted; I asked the live compiler and it refused — proven, not assumed:
i13 run rand_call.i13 => rand_call.i13:1:8 E0202 unknown function `random` (no entropy primitive)
i13 run rand2.i13 => rand2.i13:1:8 E0202 unknown function `rand` (no builtins AT ALL — every call must resolve to a `def`)
i13 check mod.i13 => mod.i13:3:10 E0001 unexpected character `%` (the k/i bucket needs modulo; there is none)
i13 run det.i13 (twice) => out = 42 · out = 42 (deterministic by construction — same input, same receipt)
grep -riE "rand|entropy|SystemTime|thread_rng|getrandom" src/ => 0 hits (no clock, no OS entropy anywhere in the source)
Do NOT add ambient randomness. A bare random() primitive would pull entropy from the clock or the OS — and that would break the one thing I-13 is: a deterministic machine whose receipts reproduce byte-for-byte (“deterministic outputs survive”). Two runs of det.i13 both print 42 precisely because nothing non-deterministic can enter. Spend that and the receipt discipline is gone.
Instead: lift entropy to an explicit, seeded input. Let the caller thread a seed value; advance it in-language with a small LCG and read j off it. Randomness becomes data the caller supplies, not a hidden power of the machine — so same seed ⇒ same sample ⇒ same receipt. Determinism is fully preserved; the sampler is reproducible on demand and freely re-seedable.
The one honest cost. A seeded LCG needs wrap-around, i.e. modulo — and mod.i13 proves I-13 has no % (E0001). The cheapest fix is the same move the fast-inverse-square-root dart proposed: add modulo as a new BinOp discriminant, spending zero new alphabet symbols (the counted 13 stay 13; only the operator table grows). Tradeoff (stated plainly): I-13’s identity is a counted 13-symbol alphabet and a strictly deterministic core — and here the two pull opposite ways. The seeded-PRNG design protects the determinism (the load-bearing property) at a small cost to the counted-alphabet purity (one extra BinOp discriminant, no new symbol). That is the design-respecting trade: keep the determinism, make entropy an input, never a primitive.