From owner-freebsd-current Mon Feb 3 22:53:39 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 5C28837B401 for ; Mon, 3 Feb 2003 22:53:38 -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 98AB943F3F for ; Mon, 3 Feb 2003 22:53:37 -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 h146rXZh005179; Mon, 3 Feb 2003 22:53:33 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.6/8.12.5/Submit) id h146rXb8005178; Mon, 3 Feb 2003 22:53:33 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Mon, 3 Feb 2003 22:53:33 -0800 From: David Schultz To: Eric Hodel Cc: freebsd-current@freebsd.org Subject: Re: rand() is broken Message-ID: <20030204065332.GB5050@HAL9000.homeunix.com> Mail-Followup-To: Eric Hodel , freebsd-current@freebsd.org References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru> <20030204054020.GA2447@HAL9000.homeunix.com> <20030204063049.GU46498@segment7.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20030204063049.GU46498@segment7.net> 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 Eric Hodel : > David Schultz (dschultz@uclink.Berkeley.EDU) wrote: > > > 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. > > A littele modification shows just how similar these sequences are :) Yeah, I saw the periodicity when I asked less(1) to select particular subsequences. I guess it's a bit more impressive when you select the right modulus. ;-) To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message