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.
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