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

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

6 голосов
/ 26 мая 2010

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

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

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

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

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

Ответы [ 2 ]

3 голосов
/ 27 мая 2010

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

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

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

3 голосов
/ 27 мая 2010

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

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

...