From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 06:03:19 2015 Return-Path: Delivered-To: freebsd-numerics@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id BF1F11B4; Tue, 17 Mar 2015 06:03:19 +0000 (UTC) Received: from troutmask.apl.washington.edu (troutmask.apl.washington.edu [128.95.76.21]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "troutmask", Issuer "troutmask" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 6F0683B6; Tue, 17 Mar 2015 06:03:16 +0000 (UTC) Received: from troutmask.apl.washington.edu (localhost [127.0.0.1]) by troutmask.apl.washington.edu (8.14.9/8.14.9) with ESMTP id t2H63A3D022045 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Mon, 16 Mar 2015 23:03:10 -0700 (PDT) (envelope-from sgk@troutmask.apl.washington.edu) Received: (from sgk@localhost) by troutmask.apl.washington.edu (8.14.9/8.14.9/Submit) id t2H63AMV022044; Mon, 16 Mar 2015 23:03:10 -0700 (PDT) (envelope-from sgk) Date: Mon, 16 Mar 2015 23:03:10 -0700 From: Steve Kargl To: Pedro Giffuni Subject: Re: Random number generators Message-ID: <20150317060310.GA21975@troutmask.apl.washington.edu> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> User-Agent: Mutt/1.5.23 (2014-03-12) Cc: freebsd-numerics@FreeBSD.org X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: "Discussions of high quality implementation of libm functions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 17 Mar 2015 06:03:19 -0000 On Mon, Mar 16, 2015 at 11:22:31PM -0500, Pedro Giffuni wrote: > Hi; > > FreeBSD libc random functions are not too bad but in general I was having some thoughts about how the random generator functions in libc are slow and predictable and how just about every application nowadays is including "Mersenne Twister" or similar algorithms (which are fast and better in every way but can?t be adapted for the C API) in their applications. > > OpenBSD did something drastic about it [1], breaking standards and compatibility and whatnot. > I wouldn?t go there and I don?t think there is any real ?solution? for this. The musl libc guys tried something interesting though. They took the tempering function from MT: > > http://git.musl-libc.org/cgit/musl/commit/?id=20d01d83b5a13c77805976e7c520f566244ba3ff > > It should be something relatively easy to try on our implementation too, if someone feels like running the tests and measuring if there is a difference. > > Pedro. > > [1[ http://www.tedunangst.com/flak/post/random-in-the-wild > > I suppose it depends on what you want to accomplish. MT can be a horrible thing to use. See the history of libgfortran/intrinsics/random.c (svn r82443) where I ripped MT out many years ago in favor of George Marsaglia's KISS generator. The KISS generator that I used was his 32-bit version. GM has a 64-bit generator as well. The 32-bit version passed all of GM's diehard tests. I haven't read a report on the 64-bit generator's diehard result. One big issue is saving internal state. IIRC, MT requires 623-bit of internal state. KISS requires 4 32-bit int. Thus, if you want to reseed the generator, KISS requires far less effort. -- Steve