Is there "good" PRNG generating values without hidden state?
Posted
by actual
on Stack Overflow
See other posts from Stack Overflow
or by actual
Published on 2010-05-20T08:36:50Z
Indexed on
2010/05/20
8:40 UTC
Read the original article
Hit count: 241
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 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 for 2^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 generator, 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 (period become much longer).
Am I wanting too much?
© Stack Overflow or respective owner