Лучший способ посеять mt19937_64 для моделирования Монте-Карло

Ответ 1

Пусть recap (комментарии тоже), мы хотим генерировать разные семена, чтобы получить независимые последовательности случайных чисел в каждом из следующих случаев:

• Программа перезапускается на том же компьютере позже,
• Два потока одновременно запускаются на одной машине,
• Программа запускается на двух разных компьютерах одновременно.

1 решается с использованием времени с эпохи, 2 решается с помощью глобального атомного счетчика, 3 решается с помощью зависимого от платформы id (см. Как получить (почти) уникальный системный идентификатор в кросс-платформенный способ?)

Теперь самое лучшее, что можно комбинировать, чтобы получить uint_fast64_t (тип семян std::mt19937_64)? Я предполагаю, что мы не знаем априорного диапазона каждого параметра или слишком велики, чтобы мы не могли просто играть с битовыми сдвигами, получая уникальное семя тривиальным способом.

A std::seed_seq будет простым способом, однако его возвращаемый тип uint_least32_t не лучший выбор.

Хороший 64-битный хэшир - намного лучший выбор. STL предлагает std::hash под заголовком functional, возможность состоит в том, чтобы объединить три числа выше в строку и затем передать ее хэширу. Тип возврата - size_t, который на 64 машинах, скорее всего, будет соответствовать нашим требованиям.

Коллизии маловероятны, но, конечно же, возможны, если вы хотите быть уверенными, что не создавайте статистику, включающую последовательность более одного раза, вы можете хранить семена и отбрасывать повторяющиеся прогоны.

A std::random_device также может использоваться для генерации семян (коллизии могут все еще случаться, трудно сказать, если все чаще или меньше), однако, поскольку реализация зависит от библиотеки и может перейти к псевдослучайному генератору, это обязательно для проверки энтропии устройства и избегайте использования нулевого энтропийного устройства для этой цели, так как вы, вероятно, сломаете вышеописанные пункты (особенно пункт 3). К сожалению, вы можете обнаружить энтропию только тогда, когда вы загружаете программу на конкретную машину и проверяете ее с установленной библиотекой.

Ответ 2

Используйте std::random_device для генерации семени. Он будет предоставлять недетерминированные случайные числа, если ваша реализация поддерживает его. В противном случае это позволило использовать какой-либо другой механизм случайных чисел.

std::mt19937_64 prng;
seed = std::random_device{}();
prng.seed(seed);

operator() std::random_device возвращает unsigned int, поэтому, если ваша платформа имеет 32-разрядный int s, и вы хотите использовать 64-битное семя, вам нужно будет вызвать его дважды.

std::mt19937_64 prng;
std::random_device device;
seed = (static_cast<uint64_t>(device()) << 32) | device();
prng.seed(seed);

Другой доступный параметр использует std::seed_seq, чтобы засеять PRNG. Это позволяет PRNG вызывать seed_seq::generate, который создает невмешаемую последовательность в диапазоне [0 ≤ я < 2 ³²) с диапазоном выхода, достаточным для заполнения всего его состояния.

std::mt19937_64 prng;
std::random_device device;
std::seed_seq seq{device(), device(), device(), device()};
prng.seed(seq);

Я вызываю random_device 4 раза, чтобы создать начальную последовательность из 4 элементов для seed_seq. Тем не менее, я не уверен, что для этого лучше всего, в отношении длины или источника элементов в начальной последовательности.

Ответ 3

Насколько я могу судить по вашим комментариям, кажется, что вас интересует то, что если процесс запускает несколько ваших симуляций точно в одно и то же время, они получат разные семена.

Единственная существенная проблема, которую я вижу с вашим текущим подходом, - это условие гонки: если вы собираетесь одновременно запускать несколько симуляций, это должно быть сделано из отдельных потоков. Если это делается из отдельных потоков, вам необходимо обновить seed_count поточно-безопасным способом, или несколько симуляций могут закончиться тем же seed_count. Вы могли бы просто сделать это std::atomic<int>, чтобы решить эту проблему.

Помимо этого, это просто кажется более сложным, чем это должно быть. Что вы получаете, используя два отдельных таймера? Вы можете сделать что-то простое:

• при запуске программы, захватите текущее системное время (используя таймер с высоким разрешением) один раз и сохраните его.
• присваивать каждой симуляции уникальный идентификатор (это может быть просто целое число, инициализированное 0, которое должно быть сгенерировано без каких-либо условий гонки, как указано выше), которое увеличивается каждый раз, когда начинается симуляция, эффективно, как ваш seed_count.
• при посеве симуляции просто используйте первоначально созданную метку времени + уникальный идентификатор. Если вы это сделаете, каждое симуляция в процессе гарантирует уникальное семя.

Ответ 4

Как насчет...

Существует некоторый основной код, который запускает потоки, и есть копии функции, выполняемой в этих потоках, каждая копия которой имеет собственный Marsenne Twister. Я прав? Если это так, почему бы не использовать другой случайный генератор в главном коде? Он будет засеян штампом времени и отправит ему последовательные псевдослучайные числа, чтобы использовать экземпляры в качестве их семян.

Ответ 5

Функция POSIX gettimeofday(2) дает время с точностью до микросекунды.

Функция потока POSIX gettid(2) возвращает номер идентификатора текущего потока.

Вы должны иметь возможность объединить время в секундах с эпохи (которую вы уже используете), время в микросекундах и идентификатор потока, чтобы получить семя, которое всегда уникально на одной машине.

Если вам также необходимо, чтобы он был уникальным на нескольких компьютерах, вы могли бы также рассмотреть вопрос об имени хоста, IP-адресе или MAC-адресе.

Я бы предположил, что 32 бита, вероятно, достаточно, так как доступно более 4 миллиардов уникальных семян. Если вы не запускаете миллиарды процессов, что кажется маловероятным, вы должны быть в порядке, не дойдя до 64-битных семян.

Ответ 6

Из комментариев я понимаю, что вы хотите запустить несколько экземпляров алгоритма, один экземпляр для потока. И учитывая, что семя для каждого экземпляра будет генерироваться в значительной степени одновременно, вы хотите, чтобы эти семена были разными. Если это действительно то, что вы пытаетесь решить, ваша функция genSeed не обязательно гарантирует это.

На мой взгляд, вам нужен параллельный генератор случайных чисел (RNG). Это означает, что вам нужен только one RNG, который вы создаете с помощью только одного семя (которое вы можете генерировать с помощью вашего genSeed), а затем последовательности случайных чисел, которые как правило, переносится в последовательную среду, разделяется на X неперекрывающихся последовательностей; где X - количество потоков. Существует очень хорошая библиотека, которая предоставляет эти типы RNG в С++, следует стандарту С++ для RNG и называется TRNG (http://numbercrunch.de/trng).

Вот немного больше информации. Существует два способа достижения неперекрывающихся последовательностей в потоке. Предположим, что последовательность случайных чисел из a single RNG равна r = {r (1), r (2), r (3),...}, и у вас есть только два потока. Если вы заранее знаете, сколько случайных чисел вам понадобится для каждого потока, скажем M, вы можете передать первую M из r-последовательности в первый поток, то есть {r (1), r (2),..., r (M)}, а второй M ко второму потоку, т.е. {R (M + 1), r (M + 2),... r (2M)}. Этот метод называется blockplitting, поскольку вы разделяете последовательность в двух последовательных блоках.

Второй способ - создать последовательность для первого потока как {r (1), r (3), r (5),...}, а для второго потока - {r (2), r ( 4), r (6),...}, что имеет то преимущество, что вам не нужно заранее знать, сколько случайных чисел вам понадобится для каждой нити. Это называется скачкообразным преобразованием.

Обратите внимание, что оба метода гарантируют, что последовательности в потоке действительно не перекрываются. Ссылка, опубликованная выше, содержит много примеров, и сама библиотека очень проста в использовании. Надеюсь, мой пост поможет.