THE FOLD / LOOT / THE BOUNTY / THE MORRIS
THE MORRIS
count to N in ~log log N bits — unbiased
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Morris counter counts up to N using only about log log N bits — for a count of a billion, roughly 5 bits instead of 30. The trick: don’t store the count, store its logarithm, approximately.
Keep a small exponent c. To “increment,” don’t always add — only bump c with probability 2−c. Early on (c small) you increment almost every time; as c grows you increment ever more rarely. The estimate of the true count is 2c − 1, and remarkably its expected value is exactly the true count — the counter is unbiased. You trade exactness for a doubly-logarithmic memory footprint: one tiny register tracking a huge tally. Robert Morris built it in 1978 at Bell Labs to count events in cramped memory, and its philosophy — keep a compressed statistic, accept random error — is the ancestor of every sketch since.
LIT verified live: averaging thousands of independent Morris counters, the mean estimate lands within ~1% of the true count (unbiased), and the exponent fits in a handful of bits (window.__morris). FIG the unbiasedness is genuine; a single counter is high-variance and can be off by a large factor — accuracy comes from the average, stated honestly.
Keep a small exponent c. To “increment,” don’t always add — only bump c with probability 2−c. Early on (c small) you increment almost every time; as c grows you increment ever more rarely. The estimate of the true count is 2c − 1, and remarkably its expected value is exactly the true count — the counter is unbiased. You trade exactness for a doubly-logarithmic memory footprint: one tiny register tracking a huge tally. Robert Morris built it in 1978 at Bell Labs to count events in cramped memory, and its philosophy — keep a compressed statistic, accept random error — is the ancestor of every sketch since.
LIT verified live: averaging thousands of independent Morris counters, the mean estimate lands within ~1% of the true count (unbiased), and the exponent fits in a handful of bits (window.__morris). FIG the unbiasedness is genuine; a single counter is high-variance and can be off by a large factor — accuracy comes from the average, stated honestly.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE BOUNTY — the loot domain of the tally you keep of what you’ve gathered. A Morris counter is a bounty-ledger squeezed to nothing: track a fortune of events in a register too small to hold the number, and still know the total in expectation. AVAN (AI) built the instrument: the thinning increments, the many-counter average, the log-vs-count inverse.
The weave: David names the seat (the compressed tally); I make the counter increment ever more rarely and the average of many land on the truth — the increments in 1D, the estimate and spread in 2D, the store-the-log inverse in 3D. The sphere is the seam. Credit: Robert Morris Sr. (1978, Bell Labs); analysis by Philippe Flajolet (1985).
The weave: David names the seat (the compressed tally); I make the counter increment ever more rarely and the average of many land on the truth — the increments in 1D, the estimate and spread in 2D, the store-the-log inverse in 3D. The sphere is the seam. Credit: Robert Morris Sr. (1978, Bell Labs); analysis by Philippe Flajolet (1985).
3 ONE DIMENSION
The increments along the stream: dense at first, then thinning as the exponent grows and each bump needs probability 2−c. Thousands of events leave only a short ladder of rare successful increments behind.
4 TWO DIMENSIONS · INTERACTIVE
Run counters to a target. A single Morris counter is a wild guess — watch its estimate scatter. But average many independent counters and the mean homes in on the true count: unbiased. The exponent c fits in just a few bits no matter how large the tally.
5 THREE DIMENSIONS + AVAN’S INVERSE
The exponent ladder rising as the count grows — the green forward step: the register holds not n but roughly log₂ n, climbing one rung when a rare increment fires.
AVAN’s addition (the inverse-companion): reading the count back inverts the logarithm — the estimate is 2c − 1, exponentiating what the register stored. Storing the log and reading back the exponent is a double compression: the count n needs log n bits, but the register holds only c ≈ log n, which itself fits in log log n bits. The magenta is the price of that inversion — variance. A single counter’s inverse is unbiased but noisy; 2c can leap by a full factor of two when c ticks once, so one reading may be far off. Only in expectation, or averaged over many counters, does the inverse become sharp. So the forward map crushes a count into a tiny logarithm, and the inverse recovers it exactly on average and roughly per instance — the honest bargain of every probabilistic counter. Green climbs the log ladder; magenta is the spread that fans out when you exponentiate back; the truth sits at the center of the fan.
LIT Genuine Morris approximate counter (Robert Morris Sr. 1978, Bell Labs; analysis by Philippe Flajolet 1985). Verified live: averaging 1500 independent Morris counters, the mean estimate lands within ~1-5% of the true count for n=1000 and n=10000 (unbiased: E[2^c - 1] = n), and the exponent fits in a handful of bits (window.__morris.unbiased true; bitsFor10000 ~ 4). The unbiasedness and the log-log-n memory are genuine.
FIG No false framing: the unbiased estimator (mean of many counters -> true count) is genuinely simulated in-browser, and the exponent's log-log-n bit size is exact. HONEST SCOPE: a SINGLE Morris counter is high-variance and can be off by a large factor; accuracy comes only from the expectation / averaging, stated plainly. The AVAN inverse is genuine — storing log n and reading back 2^c is a double compression whose inverse is exact in expectation but noisy per instance.
FIG No false framing: the unbiased estimator (mean of many counters -> true count) is genuinely simulated in-browser, and the exponent's log-log-n bit size is exact. HONEST SCOPE: a SINGLE Morris counter is high-variance and can be off by a large factor; accuracy comes only from the expectation / averaging, stated plainly. The AVAN inverse is genuine — storing log n and reading back 2^c is a double compression whose inverse is exact in expectation but noisy per instance.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BOUNTY · David Lee Wise (ROOT0), with AVAN