Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 10
Вот в одном абзаце у вас есть два по отдельности истинных утверждения:
В действительности же применяются статистически-качественные ГПСЧ, чаще всего что-либо из семейства XorShift (период от 2^128-1 до 2^1024-1) либо Mersenne Twister — там уже от 2^19937 и более. А стандартные Math.rand(), которые в 85% случаев есть вариации на тему линейных конгруэнтных генераторов, да в каких-либо серьёзных симуляциях… Шутите? Вы бы еще RANDU вспомнили!
Чаще всего для вычислений по методу Монте-Карло применяют датчики псевдослучайных чисел.и
В стандартных датчиках случайных чисел период чаще всего не превосходит 2 в степени разрядности операционной системы, а то и еще меньше.… но из этого можно сделать ложный вывод, что «для вычислений по методу Монте-Карло чаще всего применяют стандартные датчики случайных чисел, период которых чаще всего не превосходит 2 в степени разрядности операционной системы, а то и еще меньше».
В действительности же применяются статистически-качественные ГПСЧ, чаще всего что-либо из семейства XorShift (период от 2^128-1 до 2^1024-1) либо Mersenne Twister — там уже от 2^19937 и более. А стандартные Math.rand(), которые в 85% случаев есть вариации на тему линейных конгруэнтных генераторов, да в каких-либо серьёзных симуляциях… Шутите? Вы бы еще RANDU вспомнили!
Спасибо, за комментарий. Полностью с вами согласен. Последние замечания в статье направлены больше на студенческую аудиторию. Например, я в студенческие годы (лет 13 назад) был удивлен результатом моделирования (при N>10^10).
Добавлю, что вариаций на тему генераторов случайных чисел очень много. Например, я часто использую для таких целей хорошо изученные криптографические алгоритмы (например, наши ГОСТы).
Добавлю, что вариаций на тему генераторов случайных чисел очень много. Например, я часто использую для таких целей хорошо изученные криптографические алгоритмы (например, наши ГОСТы).
Вспомнилось… В студенческие годы, и кстати примерно 13 лет назад напоролся на Modulo Bias (см.там соотв.параграф). Очень долго тупил: не мог понять, а что же я сделал не так с этим Math.rand() % m, ну типа всё очевидно же, получаем случайное число от 0...n, а нам надо 0...m, но ежели m < n, то поделим нацело, возьмем остаток, быстро, качественно, недорого, херак-херак и в продакшн. Результат был, как бы немного предсказуем (см.статью по ссылке)… И неважно, взял бы я тогда стандартный сишный rand (он кстати и был), MT19937 или детектор космических лучей.
Держу пари, что на этом «Modulo Bias» при симуляциях методом Монте-Карло гораздо больше народу споткнулось, чем на использовании негодных ГПСЧ.
Держу пари, что на этом «Modulo Bias» при симуляциях методом Монте-Карло гораздо больше народу споткнулось, чем на использовании негодных ГПСЧ.
Аналогичные грабли возникают, когда нужны случайные числа в плавающей точке, а ГПСЧ возвращает целые числа. Появляется желание просто поделить на RAND_MAX, но при этом есть неожиданные тёмные углы.
А чего MISER и VEGAS забыли?
Да, и оставлю тут
www.gnu.org/software/gsl/manual/html_node/Monte-Carlo-Integration.html
Да, и оставлю тут
www.gnu.org/software/gsl/manual/html_node/Monte-Carlo-Integration.html
Указанные алгоритмы несколько выходят за рамки данной заметки.
Vegas — алгоритм или лучше сказать, конкретное решение, приближающее распределение используемой случайной величины к |g(x)| / I. Иными словами выбирает плотность распределения пропорционально |g(x)| на сколько это возможно. О необходимости этого я говорил.
MISER — алгоритм, разбивает область интегрирования на две части рекурсивно до некоторой глубины. К каждой полученной области, применяется метод Монте-Карло. А количество итераций алгоритма в каждой области выбирается так, чтобы суммарная дисперсия получаемой оценки была минимальной.
Но, возможно, ссылка на библиотеку кому-то пригодится.
Vegas — алгоритм или лучше сказать, конкретное решение, приближающее распределение используемой случайной величины к |g(x)| / I. Иными словами выбирает плотность распределения пропорционально |g(x)| на сколько это возможно. О необходимости этого я говорил.
MISER — алгоритм, разбивает область интегрирования на две части рекурсивно до некоторой глубины. К каждой полученной области, применяется метод Монте-Карло. А количество итераций алгоритма в каждой области выбирается так, чтобы суммарная дисперсия получаемой оценки была минимальной.
Но, возможно, ссылка на библиотеку кому-то пригодится.
> и построить свой генератор
Зачем изобретать велосипед, когда есть PCG32? Ну или можно взять любой готовый блочный шифр и шифровать им числа от 0 до обеда.
Зачем изобретать велосипед, когда есть PCG32? Ну или можно взять любой готовый блочный шифр и шифровать им числа от 0 до обеда.
> и построить свой генератор
Да, не удачно выразился. Не о велосипеде речь. Хотел сказать, что-то типа «найти подходящий генератор (проверенный, с нужными свойствами), отличный от стандартного, и реализовать его в своей программе», а получилось, как всегда.
Зачем изобретать велосипед, когда есть PCG32?
Я не хотел совсем касаться темы конкретных генераторов ПСЧ, хотелось только обратить внимание на важность их выбора.
Что касается конкретного генератора.
Тут выбор богатый, и PCG32 — это всего лишь один из многих. Если бы в решении этой задачи (генерации ПСЧ) все было бы так просто, то было бы ровно одно решение.
Каждый выбирает, то что ему подходит лучше для решения конкретной задачи. Это мое мнение, возможно оно ошибочно, но пока такая концепция меня не подводила.
> Если бы в решении этой задачи (генерации ПСЧ) все было бы так просто,
Сейчас там действительно уже всё просто — если не известно, какой алгоритм использует стандартная библиотека, то надо на всякий случай взять готовую реализацию любого современного алгоритма (Mersenne Twister, PCG32) или блочного шифра (ChaCha20, Speck). Они все гарантированно проходят все тесты и отличаются только сложностью реализации и скоростью работы.
Преимущество PCG32 и Speck в том, что их реализация укладывается в несколько строчек, поэтому не нужно тянуть новую зависимость.
> то было бы ровно одно решение.
Не обязательно. Много решений существует по историческим причинам из из-за синдрома «изобретено не здесь». Языков человеческих вон тоже много существует, хотя они все одну и ту же функцию выполняют и примерно с одинаковым успехом.
Сейчас там действительно уже всё просто — если не известно, какой алгоритм использует стандартная библиотека, то надо на всякий случай взять готовую реализацию любого современного алгоритма (Mersenne Twister, PCG32) или блочного шифра (ChaCha20, Speck). Они все гарантированно проходят все тесты и отличаются только сложностью реализации и скоростью работы.
Преимущество PCG32 и Speck в том, что их реализация укладывается в несколько строчек, поэтому не нужно тянуть новую зависимость.
> то было бы ровно одно решение.
Не обязательно. Много решений существует по историческим причинам из из-за синдрома «изобретено не здесь». Языков человеческих вон тоже много существует, хотя они все одну и ту же функцию выполняют и примерно с одинаковым успехом.
Как будто скушано часть смволов, если возможно отредактируйте пожалуйста статью
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Метод Монте-Карло и его точность