The Counter Only Remembers the Exponent
An exact counter is boring in the best possible way. Every event adds one. The stored integer is the answer.
The boring version has a sharp memory cliff. An 8-bit counter stops at 255. If you need many counters and only have bytes, the obvious repair is to give every counter more bytes. Robert Morris’s 1978 note starts from exactly that kind of machine constraint: many event counters, byte-sized storage, and no room for 16-bit counters.1
Morris’s trick is to stop storing the count. Store something closer to its logarithm, and increment that stored value only sometimes.
For a base \(b > 1\), keep an integer register \(X\). On each event:
with probability b^(-X): X <- X + 1
otherwise: X stays fixed
Decode the register as:
\[\hat n(X) = \frac{b^X - 1}{b - 1}.\]When \(X=0\), the estimate is 0. When \(X=1\), the estimate is 1. Later, the steps get wider. The counter has become a staircase with random landing times.
The surprising part is not that this compresses the count. The surprising part is that the decoded value is unbiased:
\[\mathbb{E}\left[\hat n(X_N)\right] = N.\]The counter forgot the exact path, but in expectation it kept the total.
The One-Line Martingale
Suppose the register currently has value \(X\). Define
\[Y = \frac{b^X - 1}{b - 1}.\]After the next event, \(X\) increments with probability \(b^{-X}\). The expected next decoded value is:
\[\begin{aligned} \mathbb{E}[Y' \mid X] &= (1 - b^{-X})\frac{b^X - 1}{b - 1} + b^{-X}\frac{b^{X+1} - 1}{b - 1} \\ &= \frac{b^X - 1}{b - 1} + 1 \\ &= Y + 1. \end{aligned}\]That is the whole conservation law. Each real event adds one unit to the expected decoded estimate. Starting from zero, after \(N\) events the decoded estimate has expectation \(N\).
Morris used a parameter \(a\) rather than the base directly:
\[b = 1 + \frac{1}{a}, \qquad \hat n(X) = a\left(\left(1 + \frac{1}{a}\right)^X - 1\right).\]This version has variance:
\[\operatorname{Var}(\hat n) = \frac{N(N-1)}{2a}.\]So for large \(N\), the relative standard deviation is approximately:
\[\frac{\sqrt{\operatorname{Var}(\hat n)}}{N} \approx \frac{1}{\sqrt{2a}}.\]That relative-error scale is almost independent of the count. It is paid for with range. In a fixed-width register, larger \(a\) means a base closer to one, smaller jumps, lower variance, and a smaller maximum decodable count.
Morris’s example used 8-bit counters with \(a=30\). The largest decodable count is about:
\[30\left(\left(1 + \frac{1}{30}\right)^{255} - 1\right) \approx 1.28 \times 10^5.\]His paper reports the same order of magnitude, “about 130,000”, with a relative error around a quarter at 95% confidence under the normal approximation.1
The Lab
The lab below simulates Morris counters directly. It uses a geometric waiting time for the next successful register increment, which is equivalent to processing events one at a time but much faster when the register is already large.
The controls expose the main engineering tradeoffs:
- true events is the real stream length;
- precision a is Morris’s parameter;
- register bits fixes the largest stored exponent;
- trials repeats the experiment to show the sampling distribution; and
- replicas averages independent counters, lowering variance by the usual factor of the number of replicas.
The artifact includes exact checks for small counts and seeded Monte Carlo checks for larger counts: 10 audit cases and 24 named checks.
node - <<'NODE'
const lab = require("./assets/js/morris-counter-lab.js");
const EXPECTED_EXACT_ROWS = 6;
const EXPECTED_SCENARIO_ROWS = 4;
const EXPECTED_ROWS = 10;
const EXPECTED_CHECKS = 24;
const EXPECTED_EXACT_EVENTS = [0, 1, 2, 8, 35, 60];
const EXPECTED_SCENARIO_EVENTS = [1000, 40000, 80000, 160000];
const EXPECTED_EXACT_CHECK_NAMES = [
"exact expectation equals count",
"exact variance matches formula"
];
const EXPECTED_SCENARIO_CHECK_NAMES = [
"empirical mean is inside standard-error envelope",
"saturation is either absent or explicitly near capacity",
"seeded replay is deterministic"
];
const EXPECTED_TOTALS = {
exactRows: EXPECTED_EXACT_ROWS,
scenarioRows: EXPECTED_SCENARIO_ROWS,
passed: EXPECTED_ROWS,
total: EXPECTED_ROWS,
passedChecks: EXPECTED_CHECKS,
totalChecks: EXPECTED_CHECKS
};
const EXPECTED_EXACT_SHAPE = [
"0:meanOk=true:varianceOk=true:checks=2/2",
"1:meanOk=true:varianceOk=true:checks=2/2",
"2:meanOk=true:varianceOk=true:checks=2/2",
"8:meanOk=true:varianceOk=true:checks=2/2",
"35:meanOk=true:varianceOk=true:checks=2/2",
"60:meanOk=true:varianceOk=true:checks=2/2"
];
const EXPECTED_SCENARIO_SHAPE = [
"80000:theoretical=80000:observed=80174.089:saturated=0:deterministic=true:meanOk=true:noBadSaturation=true:checks=3/3",
"1000:theoretical=1000:observed=996.258:saturated=0:deterministic=true:meanOk=true:noBadSaturation=true:checks=3/3",
"40000:theoretical=40000:observed=40013.436:saturated=0:deterministic=true:meanOk=true:noBadSaturation=true:checks=3/3",
"160000:theoretical=160000:observed=159830.740:saturated=0:deterministic=true:meanOk=true:noBadSaturation=true:checks=3/3"
];
const EXPECTED_CHECK_SHAPE = [
"exact:0:exact expectation equals count:true",
"exact:0:exact variance matches formula:true",
"exact:1:exact expectation equals count:true",
"exact:1:exact variance matches formula:true",
"exact:2:exact expectation equals count:true",
"exact:2:exact variance matches formula:true",
"exact:8:exact expectation equals count:true",
"exact:8:exact variance matches formula:true",
"exact:35:exact expectation equals count:true",
"exact:35:exact variance matches formula:true",
"exact:60:exact expectation equals count:true",
"exact:60:exact variance matches formula:true",
"scenario:80000:seeded replay is deterministic:true",
"scenario:80000:empirical mean is inside standard-error envelope:true",
"scenario:80000:saturation is either absent or explicitly near capacity:true",
"scenario:1000:seeded replay is deterministic:true",
"scenario:1000:empirical mean is inside standard-error envelope:true",
"scenario:1000:saturation is either absent or explicitly near capacity:true",
"scenario:40000:seeded replay is deterministic:true",
"scenario:40000:empirical mean is inside standard-error envelope:true",
"scenario:40000:saturation is either absent or explicitly near capacity:true",
"scenario:160000:seeded replay is deterministic:true",
"scenario:160000:empirical mean is inside standard-error envelope:true",
"scenario:160000:saturation is either absent or explicitly near capacity:true"
];
function sameList(actual, expected) {
return actual.length === expected.length &&
actual.every((value, index) => value === expected[index]);
}
function sameJson(actual, expected) {
return JSON.stringify(actual) === JSON.stringify(expected);
}
function exactShape(row) {
return `${row.events}:meanOk=${row.meanOk}:varianceOk=${row.varianceOk}:` +
`checks=${row.passedChecks}/${row.totalChecks}`;
}
function scenarioShape(row) {
return `${row.events}:theoretical=${row.theoreticalMean}:` +
`observed=${row.observedMean.toFixed(3)}:saturated=${row.saturatedTrials}:` +
`deterministic=${row.deterministic}:meanOk=${row.meanOk}:` +
`noBadSaturation=${row.noBadSaturation}:` +
`checks=${row.passedChecks}/${row.totalChecks}`;
}
function checkShape(row, kind) {
return row.checks.map((check) => `${kind}:${row.events}:${check.name}:${check.passed}`);
}
const audit = lab.auditMorrisCounterLab();
console.table(audit.exact.map((row) => ({
events: row.events,
meanOk: row.meanOk,
varianceOk: row.varianceOk,
checks: `${row.passedChecks}/${row.totalChecks}`
})));
console.table(audit.scenarios.map((row) => ({
events: row.events,
theoretical: row.theoreticalMean,
observed: row.observedMean.toFixed(1),
saturatedTrials: row.saturatedTrials,
deterministic: row.deterministic,
checks: `${row.passedChecks}/${row.totalChecks}`
})));
const auditShape = {
totals: {
exactRows: audit.exact.length,
scenarioRows: audit.scenarios.length,
passed: audit.passed,
total: audit.total,
passedChecks: audit.passedChecks,
totalChecks: audit.totalChecks
},
exactCheckNames: Array.from(new Set(audit.exact.flatMap(
(row) => row.checks.map((check) => check.name)
))).sort(),
exactEvents: audit.exact.map((row) => row.events).sort((a, b) => a - b),
exactShape: audit.exact.map(exactShape),
scenarioCheckNames: Array.from(new Set(audit.scenarios.flatMap(
(row) => row.checks.map((check) => check.name)
))).sort(),
scenarioEvents: audit.scenarios.map((row) => row.events).sort((a, b) => a - b),
scenarioShape: audit.scenarios.map(scenarioShape),
checkShape: audit.exact.flatMap((row) => checkShape(row, "exact"))
.concat(audit.scenarios.flatMap((row) => checkShape(row, "scenario")))
};
const shapeErrors = [
sameJson(auditShape.totals, EXPECTED_TOTALS) ? null : "totals",
sameJson(auditShape.exactEvents, EXPECTED_EXACT_EVENTS) ? null : "exactEvents",
sameJson(auditShape.scenarioEvents, EXPECTED_SCENARIO_EVENTS) ? null : "scenarioEvents",
sameJson(auditShape.exactCheckNames, EXPECTED_EXACT_CHECK_NAMES) ? null : "exactCheckNames",
sameJson(auditShape.scenarioCheckNames, EXPECTED_SCENARIO_CHECK_NAMES)
? null
: "scenarioCheckNames",
sameList(auditShape.exactShape, EXPECTED_EXACT_SHAPE) ? null : "exactShape",
sameList(auditShape.scenarioShape, EXPECTED_SCENARIO_SHAPE) ? null : "scenarioShape",
sameList(auditShape.checkShape, EXPECTED_CHECK_SHAPE) ? null : "checkShape"
].filter(Boolean);
if (shapeErrors.length) {
throw new Error(
`audit shape drifted in ${shapeErrors.join(", ")}:\n` +
JSON.stringify(auditShape, null, 2)
);
}
const failedExactCases = audit.exact.filter(
(row) => !row.passed || row.passedChecks !== row.totalChecks
);
const failedScenarioCases = audit.scenarios.filter(
(row) => !row.passed || row.passedChecks !== row.totalChecks
);
if (!audit.ok || failedExactCases.length || failedScenarioCases.length ||
audit.passed !== audit.total ||
audit.passedChecks !== audit.totalChecks) {
throw new Error(JSON.stringify({
failures: audit.failures,
failedExactCases,
failedScenarioCases,
shapeErrors,
auditShape
}, null, 2));
}
console.log(
`${audit.passed}/${audit.total} audit cases and ` +
`${audit.passedChecks}/${audit.totalChecks} checks passed`
);
NODE
Those named checks verify:
- the dynamic-programmed expectation matches the true count for small \(N\);
- the dynamic-programmed variance matches \(N(N-1)/(2a)\);
- the jump simulation is deterministic under a fixed seed;
- empirical means land within a standard-error envelope around the true count; and
- register saturation is flagged rather than silently folded into the unbiasedness claim.
The Register Has a Ceiling
The formula is unbiased only before the register saturates. If the register hits its maximum value, the implementation cannot keep taking logarithmic steps. It clips.
That is not a theoretical nuisance. It is the systems bargain.
For \(r\) register bits, the largest stored value is \(2^r - 1\). With Morris’s parameter \(a\), the largest decoded count is:
\[n_{\max} = a\left(\left(1 + \frac{1}{a}\right)^{2^r - 1} - 1\right).\]For fixed \(r\):
- lowering \(a\) increases the range but increases relative noise;
- raising \(a\) lowers relative noise but shortens the range; and
- averaging independent counters lowers noise but spends multiple registers.
This is why the lab has both a “max decoded” metric and a “saturated trials” metric. A run can look stable because the counter stopped moving. That is not a successful approximation.
A Tiny Counter Is Not a Tiny Truth
Morris’s counter is sometimes described as using \(O(\log \log N)\) bits. That is the memory headline, and it is real: the register value tracks a logarithm of the count, so the number of bits needed to store that register grows like the logarithm of a logarithm.2
The headline hides the variance bill.
For the base-2 version, where \(a=1\),
\[\operatorname{Var}(\hat n) = \frac{N(N-1)}{2}.\]The relative standard deviation is about 70%. That is not a dashboard counter. It is a tiny, unbiased, very noisy sketch.
The parameterized version matters because it lets a system decide how much of that noise to buy down. In the lab default, \(a=30\) gives a theoretical relative standard deviation near 13%. Averaging four independent counters cuts that in half, but uses four registers. Raising \(a\) also lowers variance, but the 8-bit range falls quickly.
Nelson and Yu’s later work is useful perspective here: approximate counting is not just a historical curiosity but a clean problem about the best possible memory/error/failure-probability tradeoff.3 One way to improve accuracy is to average many Morris counters; another is to change the base. Those choices can have different space consequences even when they look similar from the variance formula alone.
Where This Belongs
A Morris counter is a good fit when:
- many counters are needed;
- each counter only needs approximate statistical weight;
- relative error is acceptable;
- the maximum representable count has been budgeted; and
- the downstream consumer understands that the estimate is noisy.
It is a poor fit when:
- exact thresholds matter;
- low counts need exact treatment beyond the first event;
- saturation would be operationally invisible;
- adversarial manipulation of randomized counters is in scope; or
- the system needs to subtract, merge, or audit individual event identities.
The counter is elegant because it does one thing cleanly:
spend randomness so a small exponent can stand in for a large count
That is not the same as remembering the count. It is remembering just enough of the logarithm that the expectation comes out right.
-
Robert Morris, “Counting Large Numbers of Events in Small Registers”, Communications of the ACM 21(10), 1978. Morris motivates the problem with byte-sized counters, gives the randomized update rule, and analyzes the parameterized version with 8-bit counters counting roughly 130,000 events. ↩ ↩2
-
Philippe Flajolet, “Approximate Counting: A Detailed Analysis”, BIT 25, 113-134, 1985. Flajolet gives a detailed distributional analysis and frames approximate counting as maintaining large counts in small counters; Springer lists the DOI as 10.1007/BF01934993. ↩
-
Jelani Nelson and Huacheng Yu, “Optimal Bounds for Approximate Counting”, PODS 2022. The paper reviews the Morris counter, including the unbiased estimator and variance for a parameterized base, before proving modern upper and lower bounds. ↩