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?