Boost Mersenne Twister: как посеять более одного значения?

Question

Я использую реализацию boost mt19937 для симуляции.

Имитация должна быть воспроизводимой, а это означает, что позже необходимо будет хранить и потенциально повторно использовать семена ГСЧ. Я использую windows crypto api для генерации начальных значений, потому что мне нужен внешний источник для начальных значений, а не из-за каких-либо конкретных гарантий случайности. Вывод любого прогона моделирования будет иметь примечание, включая начальное значение ГСЧ, поэтому начальное число должно быть достаточно коротким. С другой стороны, в рамках анализа моделирования я буду сравнивать несколько прогонов - но чтобы быть уверенным, что эти прогоны на самом деле разные, мне нужно использовать разные семена - поэтому семена должны быть достаточно длинными чтобы избежать случайных столкновений.

Я определил, что 64-битного заполнения должно быть достаточно; вероятность столкновения достигнет 50% после примерно 2^32 запусков - эта вероятность достаточно мала, поэтому средняя ошибка, вызванная ею, для меня незначительна. Использовать только 32-битное начальное значение сложно; вероятность столкновения достигает 50% уже после 2^16 пробежек; и это слишком вероятно для моих вкусов.

К сожалению, реализация Boost либо затравливает с полным вектором состояния - который слишком длинный, слишком длинный - или с одиночным 32-разрядным длинным без знака - что не идеально.

Как я могу заполнить генератор более чем 32-битным, но меньшим, чем вектор полного состояния? Я попытался просто заполнить вектор или повторить начальные числа, чтобы заполнить вектор состояния, но даже беглый взгляд на результаты показывает, что это приводит к плохим результатам.

Answer 1

Ваши предположения ошибочны. Для симуляции вам не нужны криптографически сильные семена. На самом деле, лучше использовать семена 1,2,3,4, и так далее. Выходные значения Mersenne Twister будут некоррелированными, но никто не будет сомневаться в том, выбрали ли вы семена для вишни, чтобы получить желаемые результаты моделирования.

Для других людей, у которых есть реальная потребность, один простой способ - отбросить первые (начальные значения >>32) сгенерированные значения. Это дает вам log2(seed>>32) дополнительные биты состояния. Тем не менее, он работает эффективно только если вам нужно несколько дополнительных битов. Добавление 32 битов таким образом, вероятно, слишком медленно.

Более быстрый алгоритм заключается в генерации вектора полного состояния для хорошего генератора случайных чисел. Решения, упомянутые в вопросе (повторение или заполнение), не так хороши из-за ограниченной случайности в результирующем векторе состояния. Но если вы заполните начальный вектор состояния из вывода mersenne_twister(seed1) ^ mersenne_twister(seed2)это не проблема вообще.

Answer 2

Рассматривая источники повышения шаблона 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 бита для вычисления нечетных индексов состояния, используя этот алгоритм.

(Это предложение о культе груза)