Robert Morris [Communications of the ACM, 21:840-842, 1978] proposed a probabilistic technique for approximate counting. The basic idea is to increment a counter containing the value X with probability 2 −X . As a result, the counter contains an approximation of lg n after n events when starting with X = 1, and yields an unbiased estimator. Here we revisit the original idea of Morris, and propose a binary floating-point counter for tracking n. Namely, we use a d-bit significand in conjunction with a binary exponent. The counter has a simple formula for an unbiased estimation of n with a standard deviation of O(n2 −d/2 ). A floating-point counter matches the accuracy of a base-q Morris counter with q = 2 2 −d and uses the same number of d + lg lg n bits. The floating-point counter has the advantage that the incrementation probabilities are always integer powers of 1/2. As a consequence, it needs 2n 1 − o(1) random bits on average in order to count items in a data set of length n. Furthermore, the floating-point counter tracks small values exactly until n = 2 d .
Another application, presented in REF , is a revisited version of Morris Counter designed for binary floating-point numbers.
Approximate counting with a floating-point counter