Bits of state an exact distinct-counter needs, universe 8 to 20

Bits of state an exact distinct-counter needs, universe 8 to 20

The middle line is log₂ C(u, u/2), the exact floor: a one-pass algorithm that answers the distinct count exactly must reach a different memory state for every half-sized subset of the universe, because two subsets sharing a state give the same answer after one more key is appended and their true answers differ. The upper line is the u-bit bitmap that achieves it. The lower line is ⌈log₂(u+1)⌉, the space a plain counter takes — always below the floor, which is why no plain counter is exact. At u = 12 the floor is 9.85 bits, and a candidate holding 8 was run over all 924 subsets: two of them reached the same state, and appending one key that is in one and not the other leaves answers of 6 and 7 that it cannot tell apart.

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

5 essays call state-floor. 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.