Mersenne Twister - Есть ли способ перейти в конкретное состояние?

Question

Я немного не уверен в правильном форуме по этому вопросу. Это между теоретическим комп. Sci./math и программирование.

Я использую Mersenne-Twister для генерации псевдо случайных чисел. Теперь, начиная с данного семени, я хотел бы перейти к N -ному числу в последовательности.

Я видел это: http://www-personal.umich.edu/~wagnerr/mersennetwister.html, и одна схема может быть следующей:

Предположим, мне нужен только первый Не Числа в полной случайной последовательности из конкретного семени с.
Я разделил последовательность на п Последствия, пройдя все номера N и сохраните вектор состояния генератора случайных чисел в начале каждой последующей.
Теперь, чтобы достичь не-Т -номер, я посмотрю это не падает в k-Пу подпоследовательность, и я загрузите вектор состояния для этой последующей последовательности и генерируюсь м Последовательные случайные числа, где m-й число в последующей последовательности k-th такое же, что и N-Th в полной последовательности (n = m + (k-1) * n/p).

Но вектор штата составляет 624 х 4 байта длиной! Интересно, практически возможно перейти к произвольному элементу в последовательности, сгенерированной Мерсенном-Твистер.

Answer 1

Да, это возможно! Это называется Прыгнуть вперед.

Вы можете найти все детали, чтобы сделать это с Mersenne Twister на домашней странице авторов MT. Код доступен, а также научные публикации, объясняющие алгоритм:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/mt/jump/index.html

Answer 2

Сегодня есть способ сделать это, используя отказаться. Анкет Сложность линейна по количеству эквивалентных достижений.

Рабочий пример:

  std::mt19937 engine(0);
  std::uniform_int_distribution<int> dis(0, 9);
  auto generator = std::bind(std::ref(dis), std::ref(engine));

  qDebug() << "First sequence: ";
  for (int i = 0; i < 20; i++) {
    qDebug() << "Random value: " << generator();
  }

  engine.seed(0); // reset
  engine.discard(15); // discard the first 15 numbers from the first sequence
  qDebug() << "Last five numbers from first sequence: ";
  for (int i = 0; i < 5; i++) {
    qDebug() << "Random value: " << generator();
  }

Answer 3

The Mersenne Twister может быть представлен как (довольно большая) матрица над F₂ (Поле, содержащее два элемента 0 и 1). Переход к следующему состоянию является умножением на эту матрицу.

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

Answer 4

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