mersenne twister - is there a way to jump to a particular state?

Question

I am a little unsure about the right forum for this question. It is between theoretical comp. sci./math and programming.

I use Mersenne-Twister to generate pseudo random numbers. Now, starting from a given seed, I would like to jump to the n-th number in the sequence.

I have seen this: http://www-personal.umich.edu/~wagnerr/MersenneTwister.html, and one scheme could be as follows:

Suppose, I need only the first N numbers in the complete random sequence from particular seed s.
I split the sequence in to p subsequences, march through all the N numbers, and save the state vector of the random number generator at the beginning of each subsequence.
Now to reach n-th number, I'll see that n falls in the k-th subsequence and I'll load the state vector for this subsequence and generate m consecutive random numbers where m-th number in k-th subsequence is the same as n-th number in the complete sequence ( n = m + (k-1) * N/p ).

But the state vector is 624 x 4 bytes long! I wonder if it is practically possible to jump to an arbitrary element in the mersenne-twister generated sequence.

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.