0
$\begingroup$

On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the current process. When this timer is in milliseconds or nanoseconds for example, you will get a good random number seed. But the time datatype is usually a 64-bit integer, so in problems concerning randomized algorithms algorithms, can we assume that the RNG they use is simply a map $f: \Bbb{Z}/{2^{64}}\to \Bbb{Z}/{2^{64}}$? Or must we always assume that it's $f: \Bbb{N} \to \Bbb{Z}/2^n$ where $n$ is the word size, could be ${64}$?

I think the first version lends itself to better analytical methods because there is then really only a finite number of possible RNG's at ("inductive stage") $n$, where inductive stage simply refers to the obvious method of induction you could then employ on $n$ in proofs concerning randomized algorithms. For example, it is still an open problem whether or not any randomized polynomial-time algorithm can be derandomized into a deterministic polynomial-time algorithm.

$\endgroup$

1 Answer 1

1
$\begingroup$

There is no single answer to this. It all depends on the PRNG.

The most common case is that the seed is of fixed length, i.e., it is in $\{0,1\}^c$ for some constant $c$ (e.g., $c=64$). You can think of this as $\mathbb{Z}/2^c\mathbb{Z}$ instead of $\{0,1\}^c$ if you prefer; they are isomorphic.

It is implementation-dependent how a PRNG is seeded. Don't assume it is necessarily the time of day. For instance, it might be seeded with rdrand, /dev/urandom, or any number of other possibilities.

I am commenting above about PRNGs in practice. If you are more interested in theory, PRNGs can be formalized precisely in several ways. If you are interested in theoretical foundations and asymptotics, I recommend learning about cryptographic pseudorandom generators, which have a precise formalization.

$\endgroup$
1
  • $\begingroup$ Thank you! This is very interesting! $\endgroup$ Jan 28, 2022 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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