Как Роберт Моррис на 8-ми битах до 10 000 считал

Как все знают с помощью n-бит, можно реализовать счетчик считающий до 2ⁿ-1, но если у вас очень ограниченные ресурсы, или вам просто хочется поэкспериментировать и объединить в одно целое последовательности, вероятности, рандом и увеличение счетчика, то прошу под кат.

В этой статье мы увидим как работает, так называемый вероятностный счетчик.
Впервые он был представлен Робертом Моррисом в 1977 году, шифровальщиком, работающим в BellLabs, известного своей фразой

«Три золотых правила для обеспечения компьютерной безопасности: не владейте компьютером, не включайте его и не используйте его».

Подробнее о счетчике

В нашем распоряжении есть t бит.
Выбираем какую-либо неотрицательную возрастающую последовательность n_i (i лежит в промежутке от 0 до 2^t — 1), заходя немного вперед скажу, что значения n_i это и будут наши значения счетчика.
Теперь самое интересное — прибавление счетчика на 1 происходит с вероятностью 1/(n_i+1 — n_i)

Например наша последовательность это n_i = i², тогда увеличение счетчика от значения 8 сбудется с вероятностью 1/(16-8) = 0.125, в итоге счетчик с n_i до n_i+1 в среднем увеличится как раз за n_i+1 — n_i операций

Частный случай вероятностного счетчика это n_i = i, очевидно, что при такой последовательности счетчик будет обычным и вероятность прибавления его будет равна 1

Реализация

Теперь попробуем реализовать его на практике.
Реализовывать его будем на языке java.
Предположим, что у нас есть постоянной памяти только на 8-битный short. Так как он знаковый, то с помощью него можно вести счет до 127, но нам этого мало.
Встает вопрос какую последовательность использовать. Её выбор зависит от того до скольки вам нужно вести счетчик и сильно ли вы готовы пожертвовать точностью. В вашем распоряжении любые целочисленные возрастающие последовательности, например можно поискать их в Онлайн энциклопедии последовательностей ^[1].
Мы будем использовать числа Фиббоначи ^[2] и квадраты чисел ^[3].

У нас будет две основных функции. Первая будет увеличивать счетчик, вторая — возвращать i-ое число последовательности.

 private short counter = 0;

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

Здесь реализовано увеличение счетчика в зависимости от вероятности. Счетчик ничего не знает о последовательности и только возвращает i-ый элемент, в зависимости от успеха либо неуспеха события.

Вот последовательность из квадратов чисел

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

А вот из чисел Фиббоначи

 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;
    }

Эмулируем увеличение счетчика обычным циклом, предположим в 10 000 итераций.

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

Подведем итоги

для каждой из последовательностей я провел по 10 прогонов счетчика по 10 000 итераций

Как видно, погрешности весьма ощутимые, но если вам нужно на 8 битах считать больше чем до 10 000, то вероятностный счетчик является неплохим вариантом.

Литература:
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. — Алгоритмы. построение и анализ — 2005
Morris, R. Counting large numbers of events in small registers. Communications of the ACM 21, 10 (1977), 840–842

Автор: metrolog_ma

Источник ^[4]