1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Naor-Rheingold appears to be fairly straightforward. See the example on the wikipedia page: f(5) = 4 and you can trivially calculate f(6), but you can't calculate f_inv(4) = 5 other than brute-forcing it. Thus, you can't predict what follows 4. $\endgroup$ – MSalters Jan 13 '16 at 12:24
4
$\begingroup$

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].

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ The crucial point would not be to have legions of objects to get (independent random numbers) from, but to have (streams of random numbers) individually repeatable. $\endgroup$ – greybeard Jan 13 '16 at 7:25
  • $\begingroup$ Period isn't everything, now is it? From what I gather, many PRNGs have one or the other problem. It'd be interesting to find out if any of these could be addressed using more state. $\endgroup$ – Raphael Mar 10 '16 at 21:17

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.