В недавнем ответе упоминалось использование генераторов случайных чисел Фортуны или Мерсенна Твистера ( RNG ) для создания симуляции Монте-Карло . Я не слышал о Фортуне раньше, поэтому я посмотрел его - похоже, он в основном предназначен для криптографического использования.
В настоящее время я использую Mersenne Twister в производственном коде для заполнения алгоритма K-Means.
Какой из них (Fortuna или Mersenne Twister) считается наилучшим для «алгоритмического посева» (например, посев Монте-Карло и K-Means)? Или это «подбрасывать» - т.е. использовать наиболее удобно.
С того места, где я сижу, «лучшие» должны обеспечивать случайные числа высшего качества, работать быстро и (возможно) иметь небольшой объем памяти. Из них качество, вероятно, является наиболее важным для большинства из нас.
RAND_MAX=32768возможные значения. В настоящее время я использую MT для симуляции трассировки Монте-Карло. Тем не менее, я не вижу MT в качестве узкого места производительности в моем профилировщике, вероятно, потому что я делаю «случайное» генерирование таких вещей, как направления лучей, в качестве предварительного процесса . Например, я мог бы сгенерировать массив из 100 000 лучей при запуске, сохранить их в массиве и произвольно выбрать начальную позицию массива во время выполнения (для сбора около 10 000 лучей или около того). Это имеет относительно высокую нагрузку на память в обмен на хорошее распределение случайных чисел.Ответы:
Ну, все это компромисс в том или ином виде. Для генераторов случайных чисел я группирую их по 3 основным категориям:
Линейные конгруэнтные PRNG (метод, который обычно применяется в большинстве библиотек) полностью относятся к категории 1. И Fortuna, и Mersenne Twister полностью относятся к категории 2.
Для интересной статьи о том, как испортить алгоритм перестановки может стоить вам ваша компания / казино, я рекомендую эту статью с 1999 года . Из-за гниения ссылок изображения исчезли, но на рисунке 4, на котором вы вычерчиваете следующее число из PRNG относительно предыдущего сгенерированного числа, это набор параллельных линий.
Как указывает JM, Фортуна идет медленно. Как вы указали, Мерсенн Твистер достаточно быстр.
источник
Я думаю, что по умолчанию в категории "криптография" выбрано Blum-Blum-Shub . Как уже сказано на странице википедии, это не подходит для симуляции, потому что это слишком чертовски медленно.
Если вы работаете в Unix-подобной системе, вы также можете рассмотреть возможность получения случайных чисел непосредственно из / dev / urandom , службы операционной системы, которая обеспечивает случайные числа хорошего (хотя и не обязательно крипто) качества. В зависимости от конкретной ОС, которую вы используете, это может использовать алгоритм Ярроу - вариант которого является Fortuna. Но самый интересный аспект заключается в том, что операционная система имеет доступ к некоторым истинным случайным числам: например, к тепловому шуму от внутренних датчиков температуры. Как правило, эти данные смешиваются в случайный пул всякий раз, когда они становятся доступными для сохранения непредсказуемости данных.
Эта концепция смешивания в случайности предполагает, что можно получить лучшее из обоих миров следующим образом. Используйте более быстрый, достаточно качественный генератор случайных чисел, такой как Mersenne, в качестве основного RNG. Также поддержите второй, более качественный генератор случайных чисел - например, Fortuna. Каждое число, скажем, 25, запускает одну итерацию лучшего ГСЧ и добавляет результат в состояние вашего основного ГСЧ. Таким образом, вы получите довольно высокую производительность и довольно качественные результаты. (Я думаю, это было бы бесполезно для криптографии, потому что сила этого составного генератора вполне могла бы быть силой самого слабого звена. Но для симуляций, когда у вас, как правило, нет злонамеренного противника, это может сработать.)
источник
Я хотел бы сказать, что недавно я прошел через этот процесс с помощью симуляции, и я должен отметить, что использование Fortuna не исключено, если это действительно необходимо. В нашем случае мы были обеспокоены тем, что энтропия МП была недостаточно высокой, что в нашей симуляции привело бы к смещению. Так что для нашего моделирования мы использовали Fortuna, вытащив из этого алгоритма около 65 миллиардов случайных чисел. Дело в том, что компьютеры работают быстро, если вам действительно нужно, вы можете использовать их, если у вас есть причина. Если вы просто делаете что-то вроде интеграции в Монте-Карло, придерживайтесь MT.
источник
Я думаю, что ответ во многом зависит от приложения, для которого вы собираетесь использовать ГСЧ. Я бы предложил четвертую категорию для грубой классификации Тангурены: «Хороший без реального выигрыша».
Для многих приложений это может просто не иметь значения, и должным образом криптографический ГСЧ может просто замедлить выполнение ваших задач без какого-либо соразмерного выигрыша в достоверности. Например, большая часть исследований, которые я провожу, требует многих, многих миллионов цифр, примерно из указанного мною распределения. Подойдет практически любая ГСЧ, поэтому мне нужен только такой, который не настолько катастрофически беден, чтобы быть бесполезным, как ГСЧ. Все остальное просто излишне замедляет работу. Я склонен использовать Mersenne Twister, но это просто потому, что он работает достаточно хорошо, у меня есть код, и он достаточно быстрый.
источник