Algorithms & Data Structures
the bound is a claim, and it is checkable
Generator

HyperLogLog, p = 10: 60 runs, 5,120 bits, true answer 50,000

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
HyperLogLog, p = 10: 60 runs, 5,120 bits, true answer 50,000Every mark is one complete run of HyperLogLog, p = 10 over the same stream of 50,000 distinct keys, differing only in the seed of its hash. The horizontal position is the relative error of that run's estimate. The shaded band is ±3.25%, the standard error the analysis predicts for 5,120 bits; 23 of 60 runs fall outside it, against the 19 a normal distribution would put there. The measured root-mean-square error is 3.61% and the worst single run is 9.71%.exact-11.2%-3.3%0.0%3.3%11.2%rmse 3.61%worst 9.71%23 of 60outside the band5,120 bits · 60 seeds · relative error of one runpredicted ±3.25%

HyperLogLog, p = 10: 60 runs, 5,120 bits, true answer 50,000

Every mark is one complete run of HyperLogLog, p = 10 over the same stream of 50,000 distinct keys, differing only in the seed of its hash. The horizontal position is the relative error of that run's estimate. The shaded band is ±3.25%, the standard error the analysis predicts for 5,120 bits; 23 of 60 runs fall outside it, against the 19 a normal distribution would put there. The measured root-mean-square error is 3.61% and the worst single run is 9.71%.

Drawn at 700 × 240, wide on the page. Everything above is what error-spread returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

4 essays call error-spread. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

0.1bits the register neededrelative errora = 2a = 1.5a = 1.2a = 1.1a = 1.05a = 1.02√((a−1)/2), predicted200 runs per base · n = 20,000 · exact counter needs 15 bits72.6% at 5 bits One pass, and no room

Counting past what the register holds

 01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50% One pass, and no room

A count read off the leading zeros

 exact-11.2%-3.3%0.0%3.3%11.2%rmse 3.61%worst 9.71%23 of 60outside the band5,120 bits · 60 seeds · relative error of one runpredicted ±3.25% One pass, and no room

The correction that makes it work

 10,0000.1total bits of stateruns outside ±15%1 × 483 × 485 × 487 × 489 × 48240 runs per design · tolerance ±15% · truth 12,00067 → 3 failures When the algorithm flips a coin

The estimate that is a median of means

The library, page 2 of 5 — where error-spread sits