Вихрь Мерсенна повышения: как отобрать больше чем с одним значением?
Я использую повышение mt19937 реализация для моделирования.
Моделирование должно быть восстанавливаемым, и это означает хранить и потенциально снова использовать семена RNG позже. Я использую окна crypto API для генерации значений семени, потому что мне нужен внешний источник для семян и не из-за каких-то конкретных гарантий случайности. Вывод любого выполненного моделирования будет иметь примечание включая семя RNG - таким образом, семя должно будет быть довольно коротким. С другой стороны, как часть анализа моделирования, я буду сравнивать несколько выполнений - но быть уверенным, что эти выполнения на самом деле отличаются, я должен буду использовать различные семена - таким образом, семя должно будет быть достаточно длинным для предотвращения случайных коллизий.
Я решил, что 64 бита отбора должны быть достаточными; шанс коллизии достигнет 50% после приблизительно 2^32 выполнения - что вероятность является достаточно низкой, что средняя погрешность, вызванная им, незначительна мне. Используя всего 32 бита семени хитро; шанс коллизии уже достигает 50% после 2^16 выполнения; и это немного слишком вероятно для моих вкусов.
К сожалению, внедрение BOOST или отбирает с полным вектором состояния - который далек, слишком долго - или сингл, 32-разрядный неподписанный длинный - который не идеален.
Как я могу отобрать генератор больше чем с 32 битами, но меньше, чем полный вектор состояния? Я пытался просто дополнить вектор или повторить семена для заполнения вектора состояния, но даже поверхностный взгляд на результаты показывает, что это генерирует плохие результаты.
2 ответа
Ваши предположения ошибочны. Для моделирования вам не нужны криптостойкие семена. Фактически, использование семян 1, 2, 3, 4 и т. Д. Часто является лучшей идеей. Выходные значения Mersenne Twister не будут коррелированы, но никто не будет сомневаться, выбрали ли вы свои семена, чтобы получить желаемые результаты моделирования.
Для других людей, у которых действительно есть реальная потребность, один простой способ - отбросить первое (начальное число >> 32) сгенерированное значение. Это дает вам около log2 (seed >> 32) дополнительных бит состояния. Однако он работает эффективно только в том случае, если вам нужно несколько дополнительных бит. Добавление 32 бита таким способом, вероятно, будет слишком медленным.
Более быстрый алгоритм состоит в том, чтобы сгенерировать полный вектор состояния для хорошего генератора случайных чисел. Решения, упомянутые в вопросе (повторение или заполнение), не так хороши из-за ограниченной случайности в результирующем векторе состояния. Но если вы заполните вектор начального состояния из вывода mersenne_twister (seed1) ^ mersenne_twister (seed2) , это вообще не проблема.
Смотрим на boost исходники шаблона mersenne_twister:
void seed(UIntType value)
{
// New seeding algorithm from
// http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
// In the previous versions, MSBs of the seed affected only MSBs of the
// state x[].
const UIntType mask = ~0u;
x[0] = value & mask;
for (i = 1; i < n; i++) {
// See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106
x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
}
}
Для mt19937 UIntType - это uint32_t, w - 32. Для 64-битного семени, возможно, вы могли бы использовать младшие 32 бита для вычисления каждого четного индекса состояния (x) и старшие 32 бита для вычисления нечетных индексов состояния, используя такой алгоритм.
(Это культовое предложение)