Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
А. Ничего не понятно.
Источник непрерывной равномерно распределенной случайной величины это взаимодействие элемента с границей в модели твердых сфер.
Поясните, а то после этого дальнейшее чтение утрачивает смысл.
Б. Также не понятна сама постановка вопроса, что значит действительное число в компьютере? Есть числа с плавающей точкой, а действительных нет. Чтобы получить случайный float достаточно целочисленного генератора, т.к. битовое представление такого числа не только счётно, но и конечно.
Шарик ударяется о стенку сосуда, — событие на границе. Для уменьшения сложности вычислений, в алгоритме используется отражение центра шарика.
Для использования событий на поверхности сферы — границы или сосуда что содержит газ, используется дополнительное преобразование.
Я не знаю использовалось ли оно в UNIX системах, или использовались внутренние события, которые из-за влияния границы имеют плотность отличную от равномерной, сам генератор тогда требует большого времени разогрева, и еще ряд сложностей.
Я не знаю использовалось ли оно в UNIX системах, или использовались внутренние события, которые из-за влияния границы имеют плотность отличную от равномерной, сам генератор тогда требует большого времени разогрева, и еще ряд сложностей.
Есть числа с плавающей точкой, а действительных нет.
Паскаль Математика,… используют слово Real
Чтобы получить случайный float достаточно целочисленного генератора
Использование квантовых ям в аппаратных генераторах действительно создает целые числа, как правило 0 или 1 из которых потом собирается последовательность необходимой длинны, но если у вас такого устройства нет?
… allows you to generate random decimal fractions in the [0,1] interval. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.
Плюс я получаю значение целиком, не заботясь о битности или внутреннем устройстве чисел с плавающей точкой. Переносимость такого кода выше, хотя представить ситуацию когда высокоуровневый язык оказывается без возможности использования библиотек практически сложно.
Я не претендую на место в рынке по производительности или конкуренции с аппаратными устройствами, но мне лично был интересен вопрос о существовании источника для практически прямого получения именно случайных чисел с плавающей точкой.
теоретически это обеспечивается влиянием иррациональности при отражении элементов, плотность иррациональных чисел выше. Практически же это реализуется благодаря случайной величине на хвостах значений времени до столкновения, получающейся при операциях сложения и вычитания, потому можно сказать что данный генератор получает свойства класса TrueRandom благодаря дополнительной внешней связи с памятью.
Очень спорно. Иррациональных чисел в float нет, только рациональные. Алгоритм отражения шариков без изменения свойств можно реализовать в целых числах (и наоборот, выход любого генератора работающего с целыми числами можно просто умножить на машинное эпсилон и получить случайные вещественные числа). Ну и конечно никакого true random и внешней связи с памятью тут нет, т.к. младшие знаки хоть и выглядят случайными, тем не менее вполне детерминированы.
Алгоритм отражения шариков без изменения свойств можно реализовать в целых числах,пожалуйста приведите ссылку где такое реализовано для функции квадратного корня использующегося при вычислении времени до взаимодействия.
Ну и конечно никакого true random и внешней связи с памятью тут нет
занимательное утверждение, примерно как первое, на практике запуск двух генераторов с одинаковыми начальными параметрами приводит к их расхождению, запустив даже по идеальной траектории вписанного квадрата в окружности один элемент, если квадрат повернут на хоть какой нибудь угол, при численном моделировании вы получите уже на сотом столкновении отклонение разброс в траектории.
А теперь вместо квадрата случайное направление и порядка сотни элементов, которые в процессе еще и обмениваются импульсом после каждого взаимодействия с границей.
на практике запуск двух генераторов с одинаковыми начальными параметрами приводит к их расхождению
ну вот я взял вашу программу, сделал Rd = new Random(1); вместо Rd = new Random(); и результаты стали получаться одинаковыми. Т.е. эволюция системы полностью определяется зерном генератора использованного для начальной инициализации. Это и неудивительно — операции с вещественными числами детерминированы, принципиально числа с плавающей точкой отличаются от целых (точнее от чисел с фиксированной точкой) только тем что у них может «плавать» точность. Никаких внешних случайностей в расчетах с плавающей точкой нет.
хорошо, я дополню статью примерами последовательностей.
Проверил на 10^8 значениях, эта версия действительно держит одинаковость, при работе со списками в ранних версиях алгоритма компрессии ситуация отличалась. Но текст посвящен именно этой версии, потому упоминание TrueRandom убираю.
можете проверить на состоятельность исправленный текст, уважаемый критик.
Без претензии на true random всё становится ок, но и смысла в таком генераторе намного меньше. Ну т.е. да, про свойства проекции сферы на отрезок интересно, и то что смоделированное броуновское движение показывает хорошее распределение тоже интересно (хотя и предсказуемо), но на фоне современных ГПСЧ (pcg32, wyhash, xorshift) где скорость генерации измеряется единицами тактов процессора и нет проблем с надежностью практического смысла в нем не вижу.
Со смыслом тоже есть вопросы, пока я опираюсь только на то что заметил в литературе и в общении со специалистами. Для генерации именно float можно встретить рекомендации по использованию например атмосферных датчиков. Что это такое, маркетинговый ход или обоснованная необходимость, я точно выяснить не смог, знаю только то что на пуассоновские генераторы жалуются по функции корреляции, к слову эта часть в статье не показана.
Для меня генератор это побочный продукт, я не очень огорчаюсь если он где то не «супер пупер», что мне было важно, — близкая связь реальных наблюдаемых процессов и равномерного распределения и прямая работа с действительными числами, потому работа посвящена больше пониманию и значит методическая. Единственный посредник в получении распределения в виде гипотезы оказался даже занимательным и не уводит в дебри математики.
Так что помаленьку год за годом набираю для него доказательность и стандартизацию. Тот же набор тестов Diehard популярен именно благодаря пониманию, в статистике ведь уже наверное пол века как проверка гипотез разобрана достаточно подробно, но почему то используются именно они, не смотря на отсутствие в поверке прозрачной доказательности. Последнее я постарался в статье исправить, добавив более гибкую и прозрачную модификацию методику поверки.
Для меня генератор это побочный продукт, я не очень огорчаюсь если он где то не «супер пупер», что мне было важно, — близкая связь реальных наблюдаемых процессов и равномерного распределения и прямая работа с действительными числами, потому работа посвящена больше пониманию и значит методическая. Единственный посредник в получении распределения в виде гипотезы оказался даже занимательным и не уводит в дебри математики.
Так что помаленьку год за годом набираю для него доказательность и стандартизацию. Тот же набор тестов Diehard популярен именно благодаря пониманию, в статистике ведь уже наверное пол века как проверка гипотез разобрана достаточно подробно, но почему то используются именно они, не смотря на отсутствие в поверке прозрачной доказательности. Последнее я постарался в статье исправить, добавив более гибкую и прозрачную модификацию методику поверки.
Что касается тактов и быстродействия, в моей практике использование именно библиотечных функций ограничено, будь в вычислениях хотя бы два корня я бы уже использовал приближенное вычисление всего выражения. Удовольствие не из дешевых, но как по точности так и производительности подход существенно выигрывает в сравнении с последовательным расчетом выражения, даже будучи написанным на C, а на стадии первых версий и С++.
Претензию на true random прикрутить не сложно, здесь комментаторы предлагали использовать «конкуренцию потоков», но вполне можно использовать и загрузку процессора или сетевой поток для выбора элементов что обмениваются импульсом.
В алгоритме ведь меж элементное взаимодействие предельно упрощено, я бы даже сказал исключено, и оставлено его подобие в виде выбора для обмена импульсом соседей по номеру у взаимодействующего с границей элемента:
Именно в этом месте достаточно просто добавить «внешнюю связь».
В алгоритме ведь меж элементное взаимодействие предельно упрощено, я бы даже сказал исключено, и оставлено его подобие в виде выбора для обмена импульсом соседей по номеру у взаимодействующего с границей элемента:
//register event
EmtsRegEvt();
//Select two elements
int Ei = Rs.E < En - 1 ? Rs.E + 1 : 0;
int Ej = 0 < Rs.E ? Rs.E - 1 : En - 1;
//Interact selected elements
EmtsColSel(Ei, Ej);Именно в этом месте достаточно просто добавить «внешнюю связь».
Так что не скучайте, true random в публикацию вернулся, в виде предложения по модификации алгоритма.
Я все же считаю генератор полезным, «выпрямить» иррациональность для использования в равномерном распределении задача на мой взгляд не тривиальная, плюс получилась приемлемая производительность, но к сожалению минус — надежность. Запретить перейти на биения генератору может только «второй закон термодинамики».
Теперь что касается детерминистичности для точного решения и аналитики, период повтора траектории при зеркальном отражении элементов в сфере на множестве иррациональных и трансцендентных числах — бесконечность, формально подкоренному выражению ничто не мешает принимать и трансцендентные значения, откуда получаем что вычисление состояния генератора потребует знания функции последовательности иррациональных и трансцендентных чисел, что в действительности невозможно, потому если вы заботитесь про криптографическую стойкость, то она обеспечена аналитически, плюс как упомянуто в статье реализация дополняет поток внешними случайностями и тем усложняет поток, доводя до класса True Random.
Уже не раз использовал генератор в качестве поверочного, переписывание алгоритма для математического пакета операция временеемкая, в некоторых задачах теории игр оптимизация использовала именно целочисленную арифметику, повторное использование остатка от деления «выбивало» как C так и С# генераторы, в то время как приведенный алгоритм к таким арифметическим процедурам оказался устойчив. Позже для окончательного решения код все же был дублирован для математического пакета, и результаты вычислений с использованием этого генератора совпали. Из-за необходимости быстродействия в коде просто усложнили процедуры преобразования исключив ряд оптимизаций, но я только лишний раз убедился в своем эмпирическом выводе:
считать медленно но точно, или быстро но то что уже практически известно.
считать медленно но точно, или быстро но то что уже практически известно.
Этому тексту катастрофически не хватает запятых.
Все замечания постараюсь внести в содержание публикации, текст не прогонял через Главред , работаю напрямую редактором Харбр.
Некий простой рандом теоретически можно получить из многопоточной среды: есть же неопределенность с последовательностью действий выполняемых параллельными потоками. Надо создать борьбу между потоками за изменение одной и той же переменной, и читать данные из переменной не подряд. При доступе к переменной, потоки будут блочить друг друга, создавая рандом и т.д. Я не проводил исследований распределения, просто наблюдал кучу разных цифр в диапазоне переменной, мне кажется это достаточно простой способ «не найти решения».
«Некого» иногда недостаточно, статья именно про равномерное распределение, в криптографии и играх наличие выделенной области значений существенно влияет на конечные результаты.
Плюс вы переносите сложность получения состояния генератора на ограниченность доступа к свойствам системы, аппаратные генераторы на основе полупроводников тоже частично это используют. Но я намеренно не указывал в ключевых словах криптографию так как код алгоритма исполняется на стороне пользователя, и существенной сложности в получении состояния генератора нет. Помогает то что знание состояния не позволит получить повторяемости так как частично используются случайные данные из памяти, влияние которых не создает отклонений от равномерности получаемого распределения.
Плюс вы переносите сложность получения состояния генератора на ограниченность доступа к свойствам системы, аппаратные генераторы на основе полупроводников тоже частично это используют. Но я намеренно не указывал в ключевых словах криптографию так как код алгоритма исполняется на стороне пользователя, и существенной сложности в получении состояния генератора нет. Помогает то что знание состояния не позволит получить повторяемости так как частично используются случайные данные из памяти, влияние которых не создает отклонений от равномерности получаемого распределения.
Добавил Вашу идею использования загрузки процессора в качестве «внешней связи», для расширения возможностей генератора до ГСЧ.
Очень кратко изложена вторая оптимизация, она была получена для алгоритма компрессии и следует именно из него. Именно там она показала свою эффективность, в вики статье было указано что для размерностей выше четырех вычислительная сложность при расчете контактных чисел превосходит возможности машин, а оптимизация позволила эти числа получать прямо для восьми мерного пространства включительно.
Для меня генератор «побочный продукт», и объяснение я пока к сожалению вижу именно исходя из знаний про полную версию модели. Может со временем мне удастся оформить объяснение прямо и понятно именно для частного случая. Чтоб и школьник мог повторить создание кода осознанно.
Для меня генератор «побочный продукт», и объяснение я пока к сожалению вижу именно исходя из знаний про полную версию модели. Может со временем мне удастся оформить объяснение прямо и понятно именно для частного случая. Чтоб и школьник мог повторить создание кода осознанно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Одномерный генератор случайных действительных чисел