As Robert Morris on 8 bits, up to 10,000 counted

As everyone knows with the help of n-bits, you can implement a counter that counts up to 2 ⁿ -1, but if you have very limited resources, or you just want to experiment and combine the sequences, probabilities, randomness and counter increase into one, then I ask for .






In this article we will see how the so-called probabilistic counter works.
It was first introduced by Robert Morris in 1977, a cryptographer working at BellLabs, known for his phrase

“Three Golden Rules for Computer Security: Do not own a computer, do not turn it on, and do not use it.”

Meter Details

We have t bits at our disposal.
We select some non-negative increasing sequence n _i (i lies in the range from 0 to 2 ^t - 1), going a little ahead I will say that the values ​​of n _i will be our counter values.
Now the most interesting thing is that adding a counter by 1 occurs with a probability of 1 / (n _{i + 1} - n _i ).



For example, our sequence is n _i = i ² , then increasing the counter from a value of 8 will come true with a probability of 1 / (16-8) = 0.125 , as a result, the counter from n _i to n _{i + 1} will increase on average just for n _{i + 1} - n _ioperations

A special case of a probability counter is n _i = i, it is obvious that with such a sequence the counter will be normal and the probability of adding it will be 1

Implementation

Now let's try to put it into practice.
We will implement it in the java language.
Suppose we only have 8GB of constant memory. Since it is significant, using it you can keep score to 127, but this is not enough for us.
The question is which sequence to use. Her choice depends on how long you need to keep the meter and whether you are very willing to sacrifice accuracy. At your disposal are any integer ascending sequences, for example, you can search them in the Online sequence encyclopedia .
We will use Fibonacci numbers and squares of numbers .

We will have two main functions. The first will increment the counter, the second will return the i-th number of the sequence.

 private byte counter = 0;
    public void increase(){
        Random rand = new Random();
        int randNumber = rand.nextInt(getElementSequence(counter + 1) - getElementSequence(counter));
        if(randNumber == 0)
            counter++;
    }

Here the counter is increased depending on the probability. The counter does not know anything about the sequence and only returns the i-th element, depending on the success or failure of the event.

Here is a sequence of squared numbers

private int getElementSequence(int number){
        return (int) Math.pow(number, 2);
    }

But from the Fibonacci numbers

 private int getElementSequence(int number){
        int sumFib = 1;
        int previousElement = 0;
        int temp;
        for(int i = 0; i < number + 1; i++){
            temp = sumFib;
            sumFib = sumFib + previousElement;
            previousElement = temp;
        }
        return sumFib;
    }

We simulate a counter increase in a regular cycle, suppose in 10,000 iterations.

public static void main(String[] args) {
        TestApproximateCounting test = new TestApproximateCounting();
        for(int i=0; i<10000; i++){
             test.increase();
        };
    }

To summarize

for each of the sequences I spent 10 runs of the counter of 10,000 iterations

Run Number	counter value for squared numbers	Squares of numbers	counter value for Fibonacci numbers	Fibonacci numbers
1	93	8 649	20	6 765
2	111	12 321	20	6 765
3	105	11 025	20	6 765
4	103	10 609	21	10 946
5	96	9,216	21	10 946
6	94	8 836	22	17 711
7	93	8 639	19	4 181
8	106	11,236	19	4 181
9	104	10 816	21	10 946
10	94	8 836	20	6 765

As you can see, the errors are very tangible, but if you need to count more than 10,000 on 8 bits, then the probabilistic counter is a good option.

References:
Cormen T., Leiserson C., Rivest R., Stein K. - Algorithms. construction and analysis - 2005
Morris, R. Counting large numbers of events in small registers. Communications of the ACM 21, 10 (1977), 840–842

UPD. upon request, I added two columns to the table showing counter values ​​for each of the sequences, but once again I will say that the value of the counter itself is obtained not from counter but from the getElementSequence function with counter to the input.