Mersenne Twister - ¿Existe una manera de saltar a un estado particular?

Question

Estoy un poco indeciso sobre el foro adecuado para esta pregunta. Está entre los teórico. sci./math y programación.

utilizo Mersenne Twister-para generar números pseudo aleatorios. Ahora, a partir de una semilla dado, me gustaría saltar al número n-ésimo en la secuencia.

he visto esto: http://www-personal.umich.edu/ ~ wagnerr / MersenneTwister.html , y un esquema podría ser el siguiente:

Supongamos, sólo la primera N números en la secuencia aleatoria completa de particular, semilla s .
necesario Me dividir la secuencia en a p subsecuencias, marcha a través de todos los números N y guarde el vector de estado del generador de números aleatorios en el comienzo de cada subsecuencia.
Ahora bien, para llegar a n -ésimo número, voy a ver que n cae en el k subsecuencia -ésimo y voy a cargar el vector de estado para esta subsecuencia y generar m números aleatorios consecutivos donde m-ésimo número en k-ésimo subsecuencia es la misma que n-ésimo número de la secuencia completa (n = m + (k-1) * N / p).

Sin embargo, el vector de estado es de 624 x 4 bytes de longitud! Me pregunto si es posible en la práctica para saltar a un elemento arbitrario en la secuencia generada Mersenne-Twister.

Answer 1

Yes it is possible! It's called Jump Ahead.

You can find all the details to do this with Mersenne Twister on the homepage of MT's authors. Code is available as well as scientific publications explaining the algorithm:

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

Answer 2

Today, there is a way to do this using discard. The complexity is linear in number of equivalent advances.

A working example:

  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 can be represented as a (rather large) matrix over F₂ (the field containing the two elements 0 and 1). A transition to the next state is a multiplication by this matrix.

To jump to some arbitrary position in the stream you can compute the corresponding power of this matrix by repeated squaring, and multiply it with your initial state.

Answer 4

I think what you are asking for would be against the definition of a cryptographically secure random number generator, so unfortunately I don't think it's possible.