◄ WORLD V · SONNY 5DART 318 · a helldive at the net

MORRIS COUNTING count to a million in a byte — store the exponent, not the number

How many bits to count to N? Exactly, log₂N. Morris's approximate counter asks for far less: it stores only a small exponent c, and estimates the count as 2c−1. It increments probabilistically — the bigger c already is, the rarer the bump — so c tracks log₂N, and the register needs only log₂log₂N bits. Counting to a million costs a handful of bits, not twenty. It is the first streaming sketch: trade a little accuracy for a double-logarithmic memory that no exact counter can ever reach — because exactness requires log₂N bits, and this is provably below that floor.

THE TECHNIQUE store c; estimate 2c−1; c needs log₂log₂N bits

A count of about a thousand. The demo shows the exponent that represents it and the bits each form needs — exact vs Morris: live demo







  
HISTORY & CREDIT Robert Morris, 1978 · CACM

  
“Counting to N needs log N bits.” — only for an exact count. Morris's probabilistic counter tracks the exponent and needs log log N bits — below the exact floor, by design. cited

  
1978 · Robert Morris (of Bell Labs / early Unix) — “Counting large numbers of events in small registers,” CACM: the approximate counter.
1985 · Philippe Flajolet — the exact analysis of its bias and variance.
now · the ancestor of every streaming sketch (HyperLogLog, Count-Min); approximate counters in hardware and telemetry.

  
The number is never stored — only how many doublings it takes to reach it. A count that lives below the logarithm. Morris 1978






  
RECOMMEND FOR I-13 the exponent that stands for the count, on the compiler

  
On the canonical compiler, a count near 1023 is represented by exponent c=10 (210−1), which fits in 4 bits where the exact count needs 10:

  
$ i13 run op_morris.i13   # c = log2(N); estimate = 2^c - 1
RUN OK · 299 step(s) · peak stack 4 · call depth 11
c = 10
estimate = 1023      -- represented by the exponent alone
bits_for_c = 4       -- Morris register
bits_exact = 10      -- an exact counter

  
Recommend — a keeper shot on the sharpest axis in the batch. Morris's supplement to correctness is not efficiency-in-degree but a hard floor no correct-exact mechanism can cross: an exact counter provably requires log₂N bits; Morris uses log₂log₂N. “Sub-logarithmic memory” is a property every correct exact counter cannot have — precisely the B39 shape (a property a correct-but-different mechanism lacks, here must lack). The honest reason it is a shot and not a confirmed keeper, laid before the panel: the sub-log memory is bought with randomness, and i13 has no RNG — so i13 sizes the register (exponent 10, four bits) but does not enact the probabilistic increment that earns the accuracy. Without the coin, the mechanism that causes the memory savings is modelled, not run. The panel decides whether “represent the count by its exponent” is enough enactment, or whether an unrun probabilistic core makes this a witnessed bound.