Documentation
¶
Overview ¶
Package morris provides an implementation of Morris's algorithm for approximate counting with few bits.
The original formula raises a counter i with probability 2^(-i). The restored value is 2^i - 1.
This package introduces a parameter m, so that the first m increments are made with probability 1, then m increments with probability 1/2, then m with probability 1/4... Using m=1 is equivalent to the original formula. A large m increases accuracy but costs more bits. A single counter should use the same m for all calls to Raise and Restore.
This package is experimental.
Error rates ¶
Average error rates for different values of m:
1: 54.2%
3: 31.1%
10: 15.5%
30: 8.8%
100: 4.6%
300: 2.5%
1000: 1.6%
3000: 0.9%
10000: 0.5%
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Raise ¶
func Raise[T constraints.Unsigned](i T, m uint) T
Raise returns the new value of i after one increment. m controls the restoration accuracy. The approximate number of calls to Raise can be restored using Restore.
Types ¶
This section is empty.
Source Files
Directories