Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 51
Это что-то типа сжатия с потерями?
Как Вы уложили все числа Фибоначчи в int? Первые 300 чисел.
я не укладывал все числа Фибоначчи — переменная counter меняет свое значение не каждый раз же, поэтому до 300-ого числа Фибоначчи не доходит
Можете запустить код и выводить номер числа Фибоначчи, когда счетчик срабатывает. поверьте там даже до 100-ого члена не доходит
Можете запустить код и выводить номер числа Фибоначчи, когда счетчик срабатывает. поверьте там даже до 100-ого члена не доходит
Ели смотреть по таблице то 10946 это 21-ый член последовательности
Расскажите тогда, что в итоговой табличке.
Да, и почему для чисел Фибоначчи 6 765 повторяется много раз?
Наверное немного плохо написал что именно в таблице.
каюсь.
я запускал счетчик 10 раз с одной последовательностью и 10 раз с другой
если бы использовал обычный счетчик, то в каждой ячейке таблицы было бы значение — 10 000, так как счетчик дергался ровно 10 000 раз
но так как тут вероятностный, то значения теряют свою точность, вот я и хотел показать насколько сильный разброс у значений.
каюсь.
я запускал счетчик 10 раз с одной последовательностью и 10 раз с другой
если бы использовал обычный счетчик, то в каждой ячейке таблицы было бы значение — 10 000, так как счетчик дергался ровно 10 000 раз
но так как тут вероятностный, то значения теряют свою точность, вот я и хотел показать насколько сильный разброс у значений.
Нельзя ли привести более корректный пример использования?
Просто в вашем примере, чтобы воспользоваться счетчиком, считающим до ~10000, мы делаем другой счетчик, который считает ровно до 10000 и не укладывается в 8 бит.
Просто в вашем примере, чтобы воспользоваться счетчиком, считающим до ~10000, мы делаем другой счетчик, который считает ровно до 10000 и не укладывается в 8 бит.
Предположим вам надо выполнить некую операцию приблизительно 10 000 000 раз, но у вас есть только 8 бит. Как только значение в счетчике будет 255, то ориентировочно она выполниться 10 000 000 раз, однако с некой погрешностью.
Поправьте, если не прав.
Поправьте, если не прав.
цикл в main — это эмуляция счетчика, в цикле происходит его срабатывание.
у вас есть всего 8 бит, но считать надо вам куда дальше 127, вот вы вместо самого значения, храните номер члена из последовательности, которую заранее выбираете.
все остальное основывается на вычислении самого значения счетчика по номеру этого члена и срабатывании счетчика с определенной вероятностью.
у вас есть всего 8 бит, но считать надо вам куда дальше 127, вот вы вместо самого значения, храните номер члена из последовательности, которую заранее выбираете.
все остальное основывается на вычислении самого значения счетчика по номеру этого члена и срабатывании счетчика с определенной вероятностью.
Я вот тоже не понимаю (особенно после этого комментария), по идее этот 8-битный счетчик будет тем числом от некоего датчика (файла и т.п.). Т.е. именно его мы и будем наблюдать. В противном случае зачем такие усложнения. Но тогда возникает другой вопрос: как по этому 8-битному значению восстановить реальное значение счетчика?
вызвать функцию getElementSequence с параметром counter — вернувшееся значение и будет значением самого счетчика
8-битное значение хранит только номер элемента в последовательности, в которой и находятся наши аппроксимированные значения счетчика
8-битное значение хранит только номер элемента в последовательности, в которой и находятся наши аппроксимированные значения счетчика
Не понял, с какой целью выбирается определенная последовательность? Почему нельзя просто увеличивать счетчик, например, с вероятностью 0,01? Тогда число 100 в счетчике появится примерно через 10000 итераций.
мы используем последовательность чтобы перемещать по ней наш счетчик, через 10 000 нам нужно что то близкое к количеству итераций. Через 10 000 нам нужно значение счетчика не 100 а желательно поближе бы к 10 000
Я имею в виду физическое значение счетчика, которое в пределах байта. Если надо сделать ~10000 итераций чего либо, имея только 8 бит, достаточно после каждой итерации увеличивать счетчик с вероятностью 0.01 и проверять, когда наш байт достигнет 100. А чтобы узнать текущее (примерное) значение реального количества итераций, просто умножить наш байт на 100. Без всяких последовательностей.
так у вас получается просто используется последовательность i*100, так ведь?
выбирать последовательность нужно для того чтобы управлять зависимостью точности от максимальной границы счетчика и погрешностей счетчика на разных значениях счетчика( при малых значениях и при больших)
выбирать последовательность нужно для того чтобы управлять зависимостью точности от максимальной границы счетчика и погрешностей счетчика на разных значениях счетчика( при малых значениях и при больших)
Последовательность выбирается такой, чтобы на всем диапазоне погрешность была «неплохой»
Например, ваш вариант (который, по сути, тоже последовательность — арифметическая прогрессия) плох тем, что на маленьких значениях очень врет: и 10 и 80 для него одно и то же, а на больших — наоборот слишком точный. Но это плохо только в общем случае, может быть такое поведение это как раз то, что нужно в конкретной задаче.
Например, ваш вариант (который, по сути, тоже последовательность — арифметическая прогрессия) плох тем, что на маленьких значениях очень врет: и 10 и 80 для него одно и то же, а на больших — наоборот слишком точный. Но это плохо только в общем случае, может быть такое поведение это как раз то, что нужно в конкретной задаче.
Теоретически математика с плавающей точкой почти так же работает.
Интереснейшый подход! Единственное, что тут, по моему мнению, критически необходимо — это достаточная энтропия источника RNG. А так — статья очень простая и занимательная, спасибо!
Кстати, данный Моррис — дедушка известного червя. В смысле, отец того Морриса, что этого червя написал.
Не понял. Если есть только 1 байт, то куда поместить методы, которые возвращают квадраты? Или числа Фиббоначи?
8 бит имелось ввиду, что отводится для постоянного хранения, остальное можно вычислить и хранить незачем, то есть, если у вас будет объект «счетчик», то он будет состоять из заголовка объекта и одного 8-битного счетчика.
Так не бывает. Ведь нужно где-то хранить код, который считает квадраты? Почему бы вместо этого кода не сохранять там счетчик? Не могу придумать практический пример, где бы этот счетчик пригодился…
Ну, теоретически можно представить ситуацию (и в 70-е такое могло действительно быть), когда счётчик находится на одном устройстве с очень маленькой памятью, а «расшифровка» значения производится потом, на более мощном.
Пример: устройство со сравнительно вместительной памятью только для чтения, в которой можно хранить код, но ну очень небольшой памятью с поддержкой записи для данных (или же там таких счётчиков огромное множество).
На ум приходит тот же BIOS записаный на EPROM (сейчас то они на flash-памяти) и хранение времени с питанием от батарейки, но там конечно не такие суровые ограничения по памяти.
На ум приходит тот же BIOS записаный на EPROM (сейчас то они на flash-памяти) и хранение времени с питанием от батарейки, но там конечно не такие суровые ограничения по памяти.
Я так понимаю, в публикации на которую вы ссылаетесь описан и теоретически проанализирован случай не любой последовательности, а только таких, где в счётчике хранится v(n)=log(1+n/a)/log(1+1/a) для некоторого a. Такой метод даёт постоянную (почти) относительную ошибку, независимо от количества событий. В связи с этим не понятно, почему вы рассматриваете последовательности i^2 (т.е. в счётчике храним sqrt(n)) и чисел Фибоначчи — для них анализа ошибки ни в той публикации, ни в вашей статье нет.
Кстати, а какие есть реальные примеры применения такого метода? Что-то в голову не приходит, куда его можно использовать, ведь сейчас нет таких проблем с памятью, как во время публикации той статьи.
Кстати, а какие есть реальные примеры применения такого метода? Что-то в голову не приходит, куда его можно использовать, ведь сейчас нет таких проблем с памятью, как во время публикации той статьи.
Да, тут с вами согласен, в 80-ые годы эта проблема была более актуальна и сейчас использование такого счетчика по назначению трудно представить.
Выбор последовательности и их анализ это я решил не описывать в этой статье, так как и так достаточно объемной она получилась и я хотел просто показать на примере простейших последовательностей, как работает такой вид счетчиков
Если сообществу интересно то в свободное время могу подробнее рассказать о выборе последовательностей и их анализе.
Если сообществу интересно то в свободное время могу подробнее рассказать о выборе последовательностей и их анализе.
Хотите пример? Легко! Марсоходы, спутники. Кто угодно, у кого ограничена батарейка.
И понятно, что в общем случае речь идёт не про 8 бит, а про некоторую более сложную конструкцию, основанную на том же принципе.
И понятно, что в общем случае речь идёт не про 8 бит, а про некоторую более сложную конструкцию, основанную на том же принципе.
Создавать объект
Random каждый раз в increase() — не дело, его нужно создать единожды как член класса. В .net-аналоге тут, кстати, может вознукнуть проблема, т.к. там в качестве начального значения счётчика назначается значение часов невысокой точности.
Если у нас так ограничены ресурсы, откуда возьмется PRNG? ;)
Разве что внешний надежный источник энтропии есть.
Разве что внешний надежный источник энтропии есть.
Мне кажется, этот метод сейчас более актуален не для 8-битных счётчиков, а для какого-нибудь uint32 для регистрации примерного числа очень частых событий (либо за очень большой промежуток времени), когда не хочется использовать медленную длинную арифметику.
В таком контексте интересно было бы посмотреть, как правильно реализовать операцию add(n).
Пример: подсчёт приблизительного числа байтов, прошедших через небольшое непрерывно работающее устройство. Добавлять байты по одному, разумеется, совершенно неприемлимо. Точное число в теории хранить не очень сложно: достаточно взять GMP и использовать два счётчика — один оперативный для быстрого сложения, другой аккумулирующий для хранения общей суммы, используемый при переполнении оперативного.
Пример: подсчёт приблизительного числа байтов, прошедших через небольшое непрерывно работающее устройство. Добавлять байты по одному, разумеется, совершенно неприемлимо. Точное число в теории хранить не очень сложно: достаточно взять GMP и использовать два счётчика — один оперативный для быстрого сложения, другой аккумулирующий для хранения общей суммы, используемый при переполнении оперативного.
Для этих целей придумали приставки кило, Мега, Гига и т.д.
Кстати, использование некоего аналога плавающей точки, но шириной в 8 бит, можно рассматривать как возможное решение поставленной проблемы.
Кстати, использование некоего аналога плавающей точки, но шириной в 8 бит, можно рассматривать как возможное решение поставленной проблемы.
Использовать отдельные счётчики для разных разрядов — это по сути своя узкоспециализированная реализация длинной арифметики. У поставленной проблемы много решений, мне интересно именно такое, которое относится к содержанию статьи. А именно как правильно обрабатывать операцию += n.
Про плавающую точку не понял.
Про плавающую точку не понял.
А какой-нибудь uint64 позволит более 500 лет считать события с частотой 1 млрд в секунду обычным методом. Это так, для справки. А насчет add(n) интересная тема. Если в качестве последовательности выбрана арифметическая прогрессия, то думаю можно легко управлять вероятностью увеличения в зависимости от n, еще не думал как именно. С прогрессирующими последовательностями всё будет гораздо сложнее.
Спасибо за идею!
Мне сразу пришла на ум мысль вычислять примерную длину получаемого XML-файла исходя из размеров уже принятых частей + глубины вложенности. Чтобы прогресс-бар пользователю рисовать. :-)
Интересно посчитать вероятность того, что примерно попадем в реальную скорость :-)
Чуть не забыл: все это при условии того, что длину передаваемого XML мы не знаем.
Мне сразу пришла на ум мысль вычислять примерную длину получаемого XML-файла исходя из размеров уже принятых частей + глубины вложенности. Чтобы прогресс-бар пользователю рисовать. :-)
Интересно посчитать вероятность того, что примерно попадем в реальную скорость :-)
Чуть не забыл: все это при условии того, что длину передаваемого XML мы не знаем.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как Роберт Моррис на 8-ми битах до 10 000 считал