Using Morris' algorithm, the counter represents an "
order of magnitude estimate" of the actual count. The approximation is mathematically
unbiased. To increment the counter, a
pseudo-random event is used, such that the incrementing is a probabilistic event. To save space, only the exponent is kept. For example, in base 2, the counter can estimate the count to be 1, 2, 4, 8, 16, 32, and all of the
powers of two. The memory requirement is simply to hold the
exponent. As an example, to increment from 4 to 8, a pseudo-random number would be generated such that the probability the counter is increased is 0.25. Otherwise, the counter remains at 4. The table below illustrates some of the potential values of the counter: If the counter holds the value of 101, which equates to an exponent of 5 (the decimal equivalent of 101), then the estimated count is 2^5, or 32. There is a fairly low probability that the actual count of increment events was 5 (\frac{1}{1024} = 1 \times \frac{1}{2} \times \frac{1}{4} \times \frac{1}{8} \times \frac{1}{16}). The actual count of increment events is likely to be "around 32", but it could be arbitrarily high (with decreasing probabilities for actual counts above 39).
Selecting counter values While using powers of 2 as counter values is memory efficient, arbitrary values tend to create a dynamic error range, and the smaller values will have a greater error ratio than bigger values. Other methods of selecting counter values consider parameters such as memory availability, desired error ratio, or counting range to provide an optimal set of values. However, when several counters share the same values, values are optimized according to the counter with the largest counting range, and produce sub-optimal accuracy for smaller counters. Mitigation is achieved by maintaining Independent Counter Estimation buckets, which restrict the effect of a larger counter to the other counters in the bucket. ==Algorithm==