Andor wrote:
(snip)
> In the second edition of NR, they say that all LC PRNG are about
> equally non-random, and the quick and dirty solution above is just as
> good (or bad) as the others. As I wrote, in the current edition (3),
> they discourage the use of LC PRNGs all together.
>>A general Linear congruential RNG has the form X_{n+1} = (a*X_n + c)
>>mod m.
>>For the ANSI C RNG, m=2^32, a=1103515245, c=12345, and bits 30..16 are
>>returned.
> It makes sense only to return the higher bits. It can be shown that
> each bit in a sequence of LC PRNs has a period of at most 2^(bit
> position+1), eg. the LSB has a period of at most 2. I learned that the
> hard way :-).
This is true if m is a power of two. I believe it isn't necessarily
true if m is not a power of two. It is very common, though, for m
to be a power of two. Otherwise, if I need random low bits I divide
by a prime number sort of near sqrt(m) before using it.
-- glen
|
