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

в 16:55, , рубрики: java, Алгоритмы, вероятность, рандом, счетчик, метки: , , ,

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

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

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

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

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

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

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

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

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

Реализация

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

У нас будет две основных функции. Первая будет увеличивать счетчик, вторая — возвращать 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 итераций

Номер прогона Квадраты чисел числа Фиббоначи
1 8 649 6 765
2 12 321 6 765
3 11 025 6 765
4 10 609 10 946
5 9 216 10 946
6 8 836 17 711
7 8 639 4 181
8 11 236 4 181
9 10 810 10 946
10 8 836 6 765

Как видно, погрешности весьма ощутимые, но если вам нужно на 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

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js