I need some good pseudo random number generator that can be computed like a pure function from its previous output without any state hiding. Under "good" I mean:
I must be able to parametrize generator in such way that running it for
2^n
iterations with any parameters (or with some large subset of them) should cover all or almost all values between0
and2^n - 1
, wheren
is the number of bits in output value.Combined generator output of
n + p
bits must cover all or almost all values between0
and2^(n + p) - 1
if I run it for2^n
iterations for every possible combination of its parameters, wherep
is the number of bits in parameters.
For example, LCG can be computed like a pure function and it can meet first condition, but it can not meet second one. Say, we have 32-bit LCG, m = 2^32
and it is constant, our p = 64
(two 32-bit parameters a
and c
), n + p = 96
, so we must peek data by three ints from output to meet second condition. Unfortunately, condition can not be meet because of strictly alternating sequence of odd and even ints in output. To overcome this, hidden state must be introduced, but that makes function not pure and breaks first condition (long hidden period).
EDIT: Strictly speaking, I want family of functions parametrized by p
bits and with full state of n
bits, each generating all possible binary strings of p + n
bits in unique "randomish" way, not just continuously incrementing (p + n)
-bit int. Parametrization required to select that unique way.
Am I wanting too much?