the Morris approximate counter

Suppose you must count a huge number of events — up to a billion — but you only have an 8-bit register, which normally tops out at 255. Counting exactly is hopeless: a billion needs 30 bits. Morris's trick, from 1978, is to count APPROXIMATELY and store not the count itself but (roughly) its logarithm, so a tiny register can represent gigantic numbers. The price is that the answer is a random estimate, close but not exact. It is the seed idea of streaming: trade a little accuracy for an enormous saving in memory.

Here is how it works. Keep a small integer X, starting at 0. On each event, do NOT always increment. Instead, increment X only with probability 1/2^X (flip X fair coins; bump X only if all come up heads). So when X = 0 you increment every time, when X = 1 you increment about half the time, when X = 5 only about 1 in 32 times. The register climbs slower and slower, tracking the logarithm of the true count. To read off an estimate of how many events happened, compute 2^X - 1. One can prove this estimate is unbiased — its expected value equals the true count n — so on average it is right, though any single run scatters around n. The whole counter needs only about log log n bits, since X itself only grows to about log n.

The Morris counter matters as the first and simplest sketch, and the template for 'store a logarithm, accept randomness': the same logic underlies probabilistic counting and HyperLogLog for distinct elements. It shines when you have millions of counters (one per flow, per key, per cell) and cannot spare full-width integers for each. The honest caveats: a single Morris counter is noisy (its standard deviation is a constant fraction of n, so one estimate can be off by tens of percent); you tame that by averaging many independent counters or using a tunable base a closer to 1, which trades more memory for more accuracy. It is unbiased in expectation, not accurate on any one run.