Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 3.06.2014 | нет комментариев

Как все знают с поддержкой 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

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB