Как Роберт Моррис на 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-битный byte. Так как он знаковый, то с помощью него можно вести счет до 127, но нам этого мало.
    Встает вопрос какую последовательность использовать. Её выбор зависит от того до скольки вам нужно вести счетчик и сильно ли вы готовы пожертвовать точностью. В вашем распоряжении любые целочисленные возрастающие последовательности, например можно поискать их в Онлайн энциклопедии последовательностей.
    Мы будем использовать числа Фиббоначи и квадраты чисел.

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

     private byte 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 итераций

    Номер прогона значение counter для квадратов чисел Квадраты чисел значение counter для чисел Фибоначчи числа Фиббоначи
    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


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

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

    UPD. по просьбам добавил в таблицу два столбца, показывающих значения counter для каждой из последовательностей, но еще раз скажу, что значение самого счетчика получается не из counter а из функции getElementSequence с counter на вход.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 51

      +6
      Это что-то типа сжатия с потерями?
        +8
        да, его как раз и применяют для сжатия звука и данных
          0
          А можно поподробнее о том, как это можно применять для сжатия?
            0
            если честно, вменяемый пример использования этого счетчика для сжатия данных я вам не приведу.
          +23
          Что-то типа счетчика с потерями.
            0
            Всетаки сжатие, т.к. счетчик иногда не только «теряет» но и «преобретает» =)
          0
          Как Вы уложили все числа Фибоначчи в int? Первые 300 чисел.
            +1
            я не укладывал все числа Фибоначчи — переменная counter меняет свое значение не каждый раз же, поэтому до 300-ого числа Фибоначчи не доходит
            Можете запустить код и выводить номер числа Фибоначчи, когда счетчик срабатывает. поверьте там даже до 100-ого члена не доходит
              0
              Ели смотреть по таблице то 10946 это 21-ый член последовательности
                0
                Расскажите тогда, что в итоговой табличке.
                  0
                  Да, и почему для чисел Фибоначчи 6 765 повторяется много раз?
                    0
                    Наверное немного плохо написал что именно в таблице.
                    каюсь.

                    я запускал счетчик 10 раз с одной последовательностью и 10 раз с другой
                    если бы использовал обычный счетчик, то в каждой ячейке таблицы было бы значение — 10 000, так как счетчик дергался ровно 10 000 раз
                    но так как тут вероятностный, то значения теряют свою точность, вот я и хотел показать насколько сильный разброс у значений.
                      0
                      Неплохо было бы добавить столбцы с финальным значением 8-битного счетчика.
                        0
                        решил его не добавлять так как на самом деле значение counter не о чем не будет говорить, но раз нужно, то добавлю))
                +2
                Нельзя ли привести более корректный пример использования?
                Просто в вашем примере, чтобы воспользоваться счетчиком, считающим до ~10000, мы делаем другой счетчик, который считает ровно до 10000 и не укладывается в 8 бит.
                  +1
                  Предположим вам надо выполнить некую операцию приблизительно 10 000 000 раз, но у вас есть только 8 бит. Как только значение в счетчике будет 255, то ориентировочно она выполниться 10 000 000 раз, однако с некой погрешностью.

                  Поправьте, если не прав.
                    +4
                    Подозреваю, что Bazanra недоволен тем что расчеты чисел Фиббоначи и квадратов не получится всунуть в 8 бит.
                    0
                    цикл в main — это эмуляция счетчика, в цикле происходит его срабатывание.
                    у вас есть всего 8 бит, но считать надо вам куда дальше 127, вот вы вместо самого значения, храните номер члена из последовательности, которую заранее выбираете.
                    все остальное основывается на вычислении самого значения счетчика по номеру этого члена и срабатывании счетчика с определенной вероятностью.
                      0
                      Я вот тоже не понимаю (особенно после этого комментария), по идее этот 8-битный счетчик будет тем числом от некоего датчика (файла и т.п.). Т.е. именно его мы и будем наблюдать. В противном случае зачем такие усложнения. Но тогда возникает другой вопрос: как по этому 8-битному значению восстановить реальное значение счетчика?
                        0
                        извините, ответил на ваш комментарий не в ту ветку.
                    0
                    вызвать функцию getElementSequence с параметром counter — вернувшееся значение и будет значением самого счетчика
                    8-битное значение хранит только номер элемента в последовательности, в которой и находятся наши аппроксимированные значения счетчика
                      +5
                      Не понял, с какой целью выбирается определенная последовательность? Почему нельзя просто увеличивать счетчик, например, с вероятностью 0,01? Тогда число 100 в счетчике появится примерно через 10000 итераций.
                        0
                        мы используем последовательность чтобы перемещать по ней наш счетчик, через 10 000 нам нужно что то близкое к количеству итераций. Через 10 000 нам нужно значение счетчика не 100 а желательно поближе бы к 10 000
                          +2
                          Я имею в виду физическое значение счетчика, которое в пределах байта. Если надо сделать ~10000 итераций чего либо, имея только 8 бит, достаточно после каждой итерации увеличивать счетчик с вероятностью 0.01 и проверять, когда наш байт достигнет 100. А чтобы узнать текущее (примерное) значение реального количества итераций, просто умножить наш байт на 100. Без всяких последовательностей.
                            +3
                            так у вас получается просто используется последовательность i*100, так ведь?
                            выбирать последовательность нужно для того чтобы управлять зависимостью точности от максимальной границы счетчика и погрешностей счетчика на разных значениях счетчика( при малых значениях и при больших)
                              0
                              Ага, теперь ясно
                              +1
                              Последовательность выбирается такой, чтобы на всем диапазоне погрешность была «неплохой»

                              Например, ваш вариант (который, по сути, тоже последовательность — арифметическая прогрессия) плох тем, что на маленьких значениях очень врет: и 10 и 80 для него одно и то же, а на больших — наоборот слишком точный. Но это плохо только в общем случае, может быть такое поведение это как раз то, что нужно в конкретной задаче.
                          –2
                          Теоретически математика с плавающей точкой почти так же работает.
                            +3
                            Интереснейшый подход! Единственное, что тут, по моему мнению, критически необходимо — это достаточная энтропия источника RNG. А так — статья очень простая и занимательная, спасибо!
                              +2
                              Кстати, данный Моррис — дедушка известного червя. В смысле, отец того Морриса, что этого червя написал.
                                0
                                Не понял. Если есть только 1 байт, то куда поместить методы, которые возвращают квадраты? Или числа Фиббоначи?
                                  0
                                  8 бит имелось ввиду, что отводится для постоянного хранения, остальное можно вычислить и хранить незачем, то есть, если у вас будет объект «счетчик», то он будет состоять из заголовка объекта и одного 8-битного счетчика.
                                    0
                                    Так не бывает. Ведь нужно где-то хранить код, который считает квадраты? Почему бы вместо этого кода не сохранять там счетчик? Не могу придумать практический пример, где бы этот счетчик пригодился…
                                      +1
                                      Ну, теоретически можно представить ситуацию (и в 70-е такое могло действительно быть), когда счётчик находится на одном устройстве с очень маленькой памятью, а «расшифровка» значения производится потом, на более мощном.
                                        +1
                                        Пример: устройство со сравнительно вместительной памятью только для чтения, в которой можно хранить код, но ну очень небольшой памятью с поддержкой записи для данных (или же там таких счётчиков огромное множество).

                                        На ум приходит тот же BIOS записаный на EPROM (сейчас то они на flash-памяти) и хранение времени с питанием от батарейки, но там конечно не такие суровые ограничения по памяти.
                                    +4
                                    Я так понимаю, в публикации на которую вы ссылаетесь описан и теоретически проанализирован случай не любой последовательности, а только таких, где в счётчике хранится v(n)=log(1+n/a)/log(1+1/a) для некоторого a. Такой метод даёт постоянную (почти) относительную ошибку, независимо от количества событий. В связи с этим не понятно, почему вы рассматриваете последовательности i^2 (т.е. в счётчике храним sqrt(n)) и чисел Фибоначчи — для них анализа ошибки ни в той публикации, ни в вашей статье нет.

                                    Кстати, а какие есть реальные примеры применения такого метода? Что-то в голову не приходит, куда его можно использовать, ведь сейчас нет таких проблем с памятью, как во время публикации той статьи.
                                      +1
                                      Да, тут с вами согласен, в 80-ые годы эта проблема была более актуальна и сейчас использование такого счетчика по назначению трудно представить.
                                        0
                                        Выбор последовательности и их анализ это я решил не описывать в этой статье, так как и так достаточно объемной она получилась и я хотел просто показать на примере простейших последовательностей, как работает такой вид счетчиков
                                        Если сообществу интересно то в свободное время могу подробнее рассказать о выборе последовательностей и их анализе.
                                          0
                                          Хотите пример? Легко! Марсоходы, спутники. Кто угодно, у кого ограничена батарейка.
                                          И понятно, что в общем случае речь идёт не про 8 бит, а про некоторую более сложную конструкцию, основанную на том же принципе.
                                            0
                                            Едва ли в столь сложной аппаратуре будут полагаться на случайности.
                                              0
                                              В вопросах, в которых нужны точные вычисления — не будут. В вопросах, в которых точность не требуется, — легко. Например, выше в треде говорили про сжатие звука с потерями.
                                                0
                                                Возможно стоит привести конкретный пример сжатия? Даже необязательно сжатия, но желательно осовременный, а не 30-летней давности. Подход, безусловно, нестандартный, но на сегодня представляет лишь теоретический интерес.
                                          0
                                          Создавать объект Random каждый раз в increase() — не дело, его нужно создать единожды как член класса. В .net-аналоге тут, кстати, может вознукнуть проблема, т.к. там в качестве начального значения счётчика назначается значение часов невысокой точности.
                                            0
                                            Да. вы правы насчет единождого создания Random.
                                            0
                                            Если у нас так ограничены ресурсы, откуда возьмется PRNG? ;)

                                            Разве что внешний надежный источник энтропии есть.
                                              +3
                                              Мне кажется, этот метод сейчас более актуален не для 8-битных счётчиков, а для какого-нибудь uint32 для регистрации примерного числа очень частых событий (либо за очень большой промежуток времени), когда не хочется использовать медленную длинную арифметику.
                                                0
                                                В таком контексте интересно было бы посмотреть, как правильно реализовать операцию add(n).
                                                Пример: подсчёт приблизительного числа байтов, прошедших через небольшое непрерывно работающее устройство. Добавлять байты по одному, разумеется, совершенно неприемлимо. Точное число в теории хранить не очень сложно: достаточно взять GMP и использовать два счётчика — один оперативный для быстрого сложения, другой аккумулирующий для хранения общей суммы, используемый при переполнении оперативного.
                                                  0
                                                  Для этих целей придумали приставки кило, Мега, Гига и т.д.
                                                  Кстати, использование некоего аналога плавающей точки, но шириной в 8 бит, можно рассматривать как возможное решение поставленной проблемы.
                                                    0
                                                    Использовать отдельные счётчики для разных разрядов — это по сути своя узкоспециализированная реализация длинной арифметики. У поставленной проблемы много решений, мне интересно именно такое, которое относится к содержанию статьи. А именно как правильно обрабатывать операцию += n.
                                                    Про плавающую точку не понял.
                                                    0
                                                    А какой-нибудь uint64 позволит более 500 лет считать события с частотой 1 млрд в секунду обычным методом. Это так, для справки. А насчет add(n) интересная тема. Если в качестве последовательности выбрана арифметическая прогрессия, то думаю можно легко управлять вероятностью увеличения в зависимости от n, еще не думал как именно. С прогрессирующими последовательностями всё будет гораздо сложнее.
                                                0
                                                Спасибо за идею!
                                                Мне сразу пришла на ум мысль вычислять примерную длину получаемого XML-файла исходя из размеров уже принятых частей + глубины вложенности. Чтобы прогресс-бар пользователю рисовать. :-)
                                                Интересно посчитать вероятность того, что примерно попадем в реальную скорость :-)

                                                Чуть не забыл: все это при условии того, что длину передаваемого XML мы не знаем.

                                                Only users with full accounts can post comments. Log in, please.