I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I noticed there were two ways to seed the MT: with a single integer seed or an array of integer seeds. What is the point in seeding with an array? Does it produce a better distribution or a longer period?

Also, I would appreciate it if somebody could explain to me what is meant by the "state" of the RNG, as I am seeing that word all over the source code. Is it like a finite state machine in a way?

Thanks for your time!


A random number generator has the following simplified pseudocode:

state S;

int random() {
  S = advance_state(S);
  return extract_integer(S);

The random number generator maintains an internal state, which in the case of MT consists of an array of words and an index. Every time you want to generate a new number, two things happen: (1) the state is modified in some devious way; (2) the state is compressed to the output word. The entire random number generator is thus a finite state machine which proceeds deterministically from state to state (there is no "input"), while also producing output.

MT is implemented slightly differently by generating several output words at once, but this is just an optimization - you can also implement it in just the way I described.

Here is a simple naive example. The internal state S is a 32-bit word. It is updated by increasing it by 1. The output is the least significant bit. If S is seeded by 0, then the first few outputs are 0, 1, 1, 0, 1, 0, 0, 1, ... (the first $2^{32}$ bits in the Thue-Morse sequence).

How does the internal state get initialized? There are two ways. One way is to give the entire internal state. The other way is to give a smaller "seed", and from the seed generating an internal state in some devious way. If we do it deviously enough, then the function associating a seed with the resulting internal state will look like a random function (in other words, it will seem as we're selecting $2^{32}$ different random internal states, when the seed is a 32-bit integer).

The cryptographic strength of the second way is only 32 bits - you only need to try all $2^{32}$ different seeds in order to complete a given sequence. If you care about that and the seed is too short for your taste, you can use the first method and come up with an entire internal state, though that's usually not necessary, and certainly isn't necessary if all you want is random numbers for simulation purposes. (If you want cryptographically secure random numbers, please don't use MT.)

Other ways of seeding a random number generator, which sit on top of these methods, include using a password or passphrase (which is converted to a seed using a hash function) and using random data from your computer (which again passes through a hash function which functions as a randomness extractor).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.