Could PRNGs make use of more internal state?

Question

In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing):

Pseudo-random number generators (PRNGs) must have a period since they only have finitely many internal states.

At least for the PRNGs we see in the class, this is certainly a valid argument (assuming a finite target interval). But it begs the question: why do they not use more memory resp. internal state?

Going through this list, it seems to be the case that all PRNGs do indeed use only a few numbers from the target interval (plus some magic constants).

• Most use one to $\approx$ 5 of the most recently generated numbers.
• Some have parameter that controls how many values to store ("$r$-lag").
• A few use rather many numbers (but still constantly many).

The one I can't quite place is Naor-Reingold; I can't tell how it would be used to generate an actual sequence of pseudo-random numbers.

So while the memory usage (i.e. internal state size) of known/used PRNGs depends on the target interval and internal constants, it does not on the amount of (already) generated numbers.

Have there been any attempts to use more memory in order to obtain better generators? If so, why does it not help or not work at all?

Answer 1

Because, for any practical purpose, a PRNG with sufficiently, but finitely many states is indistinguishable from one with infinitely many. Mersenne Twister has a period of $2^{19937} - 1$, [insert your favorite argument about why $2^{19937}$ is a somewhat large number here].

Answer 2

Once the internal state is large enough, the period is long enough to be infinite for all intents and purposes. Besides, larger state means more memory used (important if you need very many completely independent random number streams, some applications use tens of thousands), more state means more data to maul to get the next state and random number (makes the generator slower).