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 / ~ м-мат / MT / ПЕРЕХОД / index.html

Answer 2

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

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

  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

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

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

Answer 4

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