Morris' Algorithm (1977) is a probabilistic approximate counting technique that uses O(log log n) space to count large numbers of events. Instead of storing the exact count, it stores a logarithmic representation and uses a probability-based increment rule: when a new event arrives, the counter increments with probability inversely proportional to the jump between consecutive representable values. This keeps relative error near-constant regardless of the magnitude of n. On an 8-bit register, ordinary counting caps at 256, but Morris' approach can approximate far larger counts. A Python implementation is referenced on GitHub.
2 Impressions