Date: Sun, 2 Feb 2003 03:48:17 -0800 From: David Schultz <dschultz@uclink.Berkeley.EDU> To: "Andrey A. Chernov" <ache@nagual.pp.ru> Cc: Kris Kennaway <kris@obsecurity.org>, current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <20030202114817.GA41041@HAL9000.homeunix.com> In-Reply-To: <20030202090422.GA59750@nagual.pp.ru> References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
Thus spake Andrey A. Chernov <ache@nagual.pp.ru>:
> Yes, first value correlation is there, but old formulae have even worse
> effect "The random sequences do not vary much with the seed", as source
> file comments and whole discussion about old RNG bad effects shown. I.e.
> for different time+PID sequence, especially increased monotonically, like
> in common practice, you'l got the same random sequence with old formulae
> (which can't be called "works fine" because this fine work was the main
> reason for change). So, returning to old formulae is not an option.
>
> The real problem is not in formulae, but in srand() funclion. This simple
> patch can fix first value correlation, and I plan to commit it, if we all
> agree. I not find better value for NSHUFF right now, but think
> that something like 10 will be enough to fight corellation completely.
> Some generating picture tests needed.
Throwing away the first 10 numbers is probably not good enough to
eliminate randomness with respect to the initial seed. Knuth
suggests throwing away the first 2000, but he is conservative.[1]
But no amount of throwing away the initial sequence will help as
long as the generator itself doesn't look very random.
Specifically, rand() isn't very interesting in the lower-order
bits, and it spectacularly fails nearly all of Marsaglia's
randomness tests.[2] If rand() is a concern to someone, they
should either find LCG parameters that produce better behavior,
or research a replacement algorithm.
[1] His PRNG is available from
http://www-cs-faculty.stanford.edu/~knuth/programs/rng.c
[2] http://stat.fsu.edu/~geo/diehard.html (you need ports/lang/f2c)
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030202114817.GA41041>