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

Question

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

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

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

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

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

Answer 1

Да, это возможно! Это называется Jump Ahead.

Вы можете найти все подробности, чтобы сделать это с 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

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

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

Answer 4

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