Thus spake Andrey A. Chernov <[EMAIL PROTECTED]>:
> On Sat, Feb 01, 2003 at 23:06:50 -0800, Kris Kennaway wrote:
> > FreeBSD's rand() implementation has been broken for the past 23
> > months, since the following commit:
>
> > i.e. the first value returned from rand() is correlated with the seed
> > given to srand(). This is a big problem unless your seed is randomly
> > chosen over its entire integer range. I noticed this because awk
> > exhibits the same problem, and the script seeds the generator with a
> > PID. The script works fine under 4.x since the rand() implementation
> > does not have this "feature".
>
> 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.
The correlation is still present with your patch and NSHUFF set to
10. For instance, try seeding rand() with contiguous monotonically
increasing integers, and observe the four lowest-order bits.
Just for the heck of it, I ran Marsaglia's tests on the rand()
implementation in -CURRENT. The arc4random() implementation
passed with flying colors as expected, whereas rand() seems to
have some slight defects, particularly in the lowest and highest
order bits. When I looked at rand()'s behavior with respect to
different seeds, it failed miserably, both with and without your
patch. The results are available at
http://www.csua.berkeley.edu/~das/marsaglia/
I'm not necessarily advocating changing the algorithm at all,
given that it's well known that many rand() implementations are
not very random. But I also don't buy the argument that ``rand()
should never ever change.'' If someone wants to do the work to
improve the algorithm, that's fine with me. David Wagner has
collected some links on randomness that might be helpful:
http://www.cs.berkeley.edu/~daw/rnd/index.html
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
