Как Роберт Моррис на 8-ми битах до 10 000 считал
Как все знают с помощью n-бит, можно реализовать счетчик считающий до 2n-1, но если у вас очень ограниченные ресурсы, или вам просто хочется поэкспериментировать и объединить в одно целое последовательности, вероятности, рандом и увеличение счетчика, то прошу под кат.
В этой статье мы увидим как работает, так называемый вероятностный счетчик.
Впервые он был представлен Робертом Моррисом в 1977 году, шифровальщиком, работающим в BellLabs, известного своей фразой «Три золотых правила для обеспечения компьютерной безопасности: не владейте компьютером, не включайте его и не используйте его».Подробнее о счетчике
В нашем распоряжении есть t бит.
Выбираем какую-либо неотрицательную возрастающую последовательность ni (i лежит в промежутке от 0 до 2t — 1), заходя немного вперед скажу, что значения ni это и будут наши значения счетчика.
Теперь самое интересное — прибавление счетчика на 1 происходит с вероятностью 1/(ni+1 — ni)
Например наша последовательность это 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
