From owner-freebsd-current Mon Feb 3 21:40:24 2003 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 6D2D837B401 for ; Mon, 3 Feb 2003 21:40:22 -0800 (PST) Received: from HAL9000.homeunix.com (12-233-57-224.client.attbi.com [12.233.57.224]) by mx1.FreeBSD.org (Postfix) with ESMTP id B291843F43 for ; Mon, 3 Feb 2003 21:40:21 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: from HAL9000.homeunix.com (localhost [127.0.0.1]) by HAL9000.homeunix.com (8.12.6/8.12.5) with ESMTP id h145eLZh004930; Mon, 3 Feb 2003 21:40:21 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.6/8.12.5/Submit) id h145eKSM004929; Mon, 3 Feb 2003 21:40:20 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Mon, 3 Feb 2003 21:40:20 -0800 From: David Schultz To: "Andrey A. Chernov" Cc: Kris Kennaway , current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <20030204054020.GA2447@HAL9000.homeunix.com> Mail-Followup-To: "Andrey A. Chernov" , Kris Kennaway , current@FreeBSD.ORG References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20030203100002.GA73386@nagual.pp.ru> Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG Thus spake Andrey A. Chernov : > 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 #include 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