Заполнить пул генераторов случайных чисел с генератором случайных чисел
Для курса я пытаюсь реализовать параллельное моделирование Монте-Карло. Одним из требований проекта является то, что точные результаты должны быть повторяемыми. В моем текущем дизайне реализована «очередь» заданий, реализованная экземпляром std::default_random_engine и набор рабочих. Работник берет «работу» и использует ее в качестве начального числа для своего собственного rng (также является примером std::default_random_engine) и запускает симуляцию с использованием этого экземпляра.
Хотя результаты действительно повторяемы, у меня остаются некоторые вопросы:
- Создает ли использование rng для создания пула rngs какое-то смещение? Если это зависит от того, какой rng используется (и, вероятно, так и есть), какой мне следует использовать?
- С этим дизайном все в порядке или есть альтернативы?
—edit— После изучения этого немного дальше, я заметил следующее: std::default_random_engine использует простой линейный конгруэнтный генератор. Его состояние просто является его предыдущим значением. Это означает, что результаты моего пула Rngs точно такие же, но смещены на единицу. Твистер Мерсенна (который имеет большее внутреннее состояние) не показывает такое поведение:
#include <iostream>
#include <random>
int main(int argc, char** argv)
{
std::default_random_engine e1(1);
std::default_random_engine e2(e1());
std::cout << e1() << ",\n" << e2() << '\n';
std::mt19937_64 e3(1);
std::mt19937_64 e4(e1());
std::cout << e3() << ",\n" << e4() << '\n';
}
какие выводы:
282475249,
282475249
2469588189546311528,
5601807455758261240
Решение
Создает ли использование rng для создания пула rngs какое-то смещение? Если это зависит от того, какой rng используется (и, вероятно, так и есть), какой мне следует использовать?
С хорошим качеством rng (любой из недавно представленных C ++ 11, но не старый rand()), звучит основная идея, но вы не захотите использовать тот же ГСЧ для генерации семян других ГСЧ. Причина в следующем: скажем, ваш «основной» ГСЧ генерирует последовательность ABCD, а другие RNG заполняются с помощью AB и CD: первый затем переходит на BC D …, второй на CD и т. Д .: в основном каждый создает ту же последовательность, начиная еще одну. Если вы используете другой ГСЧ для ведущего, это произойдет только в том случае, если некоторые из ваших значений ABC по совпадению близко совпадают в другой последовательности ГСЧ, так что один ГСЧ в конечном итоге начинает повторять последовательность другого. Период некоторых из RNG C ++ 11 настолько велик, что вряд ли у них будут столкновения во всех, кроме самых требовательных симуляциях, и такое повторение не обязательно так уж плохо — зависит от симуляции.
Кроме того, вы можете убедиться, что одно и то же начальное значение не используется дважды. (Конечно, любая данная последовательность, которую вы повторяете, может быть статистически не типичной или — потенциально одинаково проблемной — может не охватывать нетипичные крайности, но это неизбежно, если вы хотите повторяемость.)
С этим дизайном все в порядке …
Звучит хорошо, как вы это описали.
Другие решения
Это зависит. PRNG фактически генерирует очень длинную последовательность
детерминированные (неслучайные) значения, основанные на его внутреннем состоянии.
Если PRNG, используемый для посева, связан с PRNG, он
посев, в зависимости от того, как семя инициализирует внутреннее состояние,
каждый из отобранных генераторов мог легко генерировать шаг за шагом,
с первым значением последнего является вторым
рядом с последним и тд.
На практике вы, вероятно, лучше, просто увеличивая
семян для каждого генератора, а не с помощью PRNG, чтобы получить
следующее семя Это должно работать, если только те PRNG, которые вы используете
прирост также (что было бы очень плохим PRNG).
Как указывает PJS в комментарии, если вы сделаете это, выкиньте первое сгенерированное случайное число. Некоторые генераторы используют очень детерминированную формулу для преобразования начального числа во внутреннее состояние и возвращают значение, основанное на старый состояние, когда они генерируют случайное число.
Просто используйте PRNG с внутренним вектором состояния, настолько большим, что риск попадания в перекрывающиеся последовательности достаточно близок к нулю. MT, на 2496 байтов внутреннего состояния, безусловно, квалифицируется. Заполните каждый с полным 2496-байтовым начальным числом, взятым из хорошего аппаратного источника, такого как / dev / urandom или random.org, и шансы корреляции будут нулевыми для практических целей. Я не знаю, позволяет ли ваша библиотека использовать полноразмерное семя, так что если нет, найдите тот, который делает.
Честно говоря, даже при большом внутреннем состоянии никто не может гарантировать, что последовательности не будут перекрываться. Кроме того, существует вопрос об отладке, которая требует воспроизводимости проблемы. Таким образом, ответ таков: каждое событие начинается со своего собственного и стабильного (на другом оборудовании / узле / запусках) начального числа. Это делает результат воспроизводимым и отлаживаемым.
Хорошо известный код Монте-Карло MCNP5 + хорошо использовал эту схему, работает на многоядерных процессорах и MPI. Для его реализации вам понадобится RNG с функцией быстрого пропуска (a.k.a. leapfrog or discard). И их немало. Они основаны на быстром вычислении экспоненты, работе Ф. Брауна, «Генерация случайных чисел с произвольным шагом», Trans. Am. Nucl. Soc. (Ноябрь 1994 г.) По сути, пропустить вперед — это log (N) с подходом Брауна.
Простейшая версия, примерно такая же, как MCNP5, здесь https://github.com/Iwan-Zotow/LCG-PLE63
Более сложный (и более медленный, но более качественный) RNG здесь http://www.pcg-random.org/