From owner-freebsd-current Tue Feb 4 3:52:41 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 A99C337B401 for ; Tue, 4 Feb 2003 03:52:39 -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 2012143F3F for ; Tue, 4 Feb 2003 03:52:39 -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 h14BqbZh006627; Tue, 4 Feb 2003 03:52:37 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.6/8.12.5/Submit) id h14BqbRN006626; Tue, 4 Feb 2003 03:52:37 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Tue, 4 Feb 2003 03:52:37 -0800 From: David Schultz To: "Andrey A. Chernov" Cc: Kris Kennaway , current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <20030204115237.GA6483@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> <20030204054020.GA2447@HAL9000.homeunix.com> <20030204094659.GA87303@nagual.pp.ru> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20030204094659.GA87303@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 Mon, Feb 03, 2003 at 21:40:20 -0800, David Schultz wrote: > I don't try to make rand() good for high-quality pseudo-randomness, > because it can be done by price of speed and, more important, big state > size. Due to rand_r() restriction state size can be one word only, so we > can choose rand() algorithm only from those which pass this > restrictions. You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The section on LCGs suggests that the multiplier FreeBSD uses (7^5) is not particularly good, and points out some better values suggested by Knuth. I can't find the original discussion in TAOCP vol. 2, but I take N. Wagner's word that the numbers have been blessed by the holy hand of Knuth. I'm sure you can find more information if you search the literature. I apologize, but I don't have time to help you right now, and rand() isn't really a concern to me. > Returning to current algorithm, I am interested in good NSHUFF value in > the range 100-2000. Do you have any findings there? Well, if 0 doesn't work, and 10 doesn't work, and 100 doesn't work, then I'm not too hopeful about 2000. I appeal to Asimov's zero, one, infinity law. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message