Date: Mon, 3 Feb 2003 21:40:20 -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: <20030204054020.GA2447@HAL9000.homeunix.com> In-Reply-To: <20030203100002.GA73386@nagual.pp.ru> References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
Thus spake Andrey A. Chernov <ache@nagual.pp.ru>:
> On Sun, Feb 02, 2003 at 16:26:39 -0800, David Schultz wrote:
> >
> > 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.
>
> Since you already have running framework for that, could you please
> test it with NSHUFF picked from 100-2000 range?
Rather than me showing you more semi-meaningful numbers from
Marsaglia's tests, why don't you look at the following sequence,
which I get by taking the lowest four bits of the 201st number in
the rand() sequence for seeds of (0, 1, 2, ...).
f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9
6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f
c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5
2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b
8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1
e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7
4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d
a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3
0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9
6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f
Notice that 'f c 9' repeats in regular intervals and is always
followed by a 5 or 6. There is a similar pattern for 'e a 7'. I
think this pretty much demonstrates that the algorithm isn't good
enough to generate high-quality randomness with respect to
different seed values. I'm not suggesting that it absolutely must
be replaced, since most rand() implementations aren't very good in
the first place, but I'm pointing out that to do a good job of
fixing it once and for all is harder than you might think.
The program to generate this sequence follows. I ran this on a
several-month-old -CURRENT system with the new generator, but
without your latest patches.
#include <stdio.h>
#include <stdlib.h>
int main() {
int i, j;
for (i = 0; ; i++) {
srand(i);
for (j = 0; j < 200; j++)
rand();
printf("%x ", rand() & 0x0f);
if (i % 32 == 31)
putchar('\n');
}
}
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?20030204054020.GA2447>