About Mersenne Twister generator's period

Question

I have read that Mersenne Twister generator has a period of 2¹⁹⁹³⁷ - 1, but I'm confused about why can that be possible. I see this implementation of the Mersenne Twister algorithm and in the first comment it clearly says that it produces values in the range 0 to 2³² - 1. Therefore, after it has produced 2³² - 1 different random numbers, it will necessarily come back to the starting point (the seed), so the period can be at maximum 2³² - 1.

Also (and tell me if I'm wrong, please), a computer can't hold the number (2¹⁹⁹³⁷ - 1) ~ 4.3×10⁶⁰⁰¹, at least in a single block of memory. What am I missing here?

Answer 1

Your confusion stems from thinking that the output number and the internal state of a PRNG have to be the same thing.

Some very old PRNGs used to do this, such as Linear Congruental Generators. In those generators, the current output was fed back into the generator for the next step.

However, most PRNGS, including the Mersenne Twister, work from a much larger state, which it updates and uses to generate a 32-bit number (it doesn't really matter which order this is done in for the purposes of this answer).

In fact, the Mersenne Twister does indeed store 624 times 32-bit values, and that is 19968 bits, enough to contain the very long period that you are wondering about. The values are handled separately (as unsigned 32-bit integers), not treated as one giant number in a single-step calculation. The 32-bit random number you get from the output is related to this state, but does not determine the next number by itself.

Answer 2

You are wrong at

Therefore, after it has produced 2³² - 1 different random numbers, it will necessarily come back to the starting point (the seed)...

That's right that the next number can be the same with one of the number already generated, but the internal state of the random number generator will not be the same. (Noone told you that every number in the range 2³² - 1 will be generated at the 2³² - 1th step.) So there's no bijection between the random number generated and the internal state of the generator. The random number generated can be calculated from the state but you don't even have to do it. You can step the internal state also without creating the random number.

And of course, the computer doesn't store the whole number sequence. It calculates the random number from the internal state. Consider a number sequence like 1, -1, 1, -1 ... you can generate the Nth number without storing number of N elements.