From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 12:10:56 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 1CDA091C for ; Tue, 17 Mar 2015 12:10:56 +0000 (UTC) Received: from nm14-vm0.bullet.mail.bf1.yahoo.com (nm14-vm0.bullet.mail.bf1.yahoo.com [98.139.213.164]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id C7B19609 for ; Tue, 17 Mar 2015 12:10:55 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426594248; bh=pM/RzuNzOHAXpTYQ3cf1W60sBiszFC7ZBooDt+EWs9o=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From:Subject; b=C5v30Ya21z5FjBzkZIez+cX11GOQYrC/Jhg+fvSyet+rA6cKJ1PIeKepXOK+U35Uue+te950t01jnvFaYWJm3SC9q6Y5p8dC3NqYRGmhz40yginLj98r3k+X6atyJskbfS2Ue8vuopR8PbMVk4QUUjcJuUURiSxseWTt84paFtD0udZ//xqU6I/zt9EQDrTSLRBf9OsHvL93cLwUF2K1UaFzv7aWPOJuj37Iwd8rC0YRMbkdvLPdxDzhs6dOHgCJtr0iKIin0GUPQj8ic3oYDvsIWA0KLp/Jkxzx5PZYg83Evedgjlrh/ZbRZBO4BSrw8h56Kez/gHHOTdp73p449w== Received: from [66.196.81.174] by nm14.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 12:10:48 -0000 Received: from [68.142.230.64] by tm20.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 12:10:48 -0000 Received: from [127.0.0.1] by smtp221.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 12:10:48 -0000 X-Yahoo-Newman-Id: 652752.87660.bm@smtp221.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: bXf2rgMVM1kCw7ohrs4pK11Gf6QBGegKoN13.kdV32znkma bfsuJvQ8vNz2ZLrwS1HalmhRjEfLUsNIg0wnUNh81Tepr__28mFMDm2dAIvq 3cWKQmYG_FjFl0BFQpAZH9vqwQz77umgMpzWREyeuB5Y3_DJqPfscoyxXT5C 0jfTnYvMnb2Ds7fHoHaduAv6mqoORpcHMIS6x12pDgSlKM05yuL9Qsjl1q.l .hV6GAQlKYwyROD35WsFXHR9Va8eEF56FzD56ZQ5iimFiEELx7qTyMuKWVjD MS1TwrRyVm8mnEhG.Sg7PNXaVWNjEwRJA5U8iKAMEHjLLI4o3FyRmAiEefKD OV55a7o4jghbUXMl5Ll8_tbYiT9ApLV_d.eJzrIwTfIBnJdndDWwFSjzoZe7 MMwpHu2UXw_FVas0R4kRUGdPtxg1_uGUiHx2KFA6xl3MBJdNaLSIQnfIrOiK 1d2ws22Tpv.Qmwau62AHiYqKBcrDCx9Jap5thdSuKmqa25FPpav.QYrLnr9T .LMQ6hJuhVqPEmPHt6GWgColpLxpDKZe.l7CwJt0_uk9kqUtS1eXD7LunL6H DH_fmd5BXpVWq3J96MMLzbORXW_osI213pX_B8Asy7yqTafXy0IsFbsvkPu4 eiU8_HN9xo8jaE.1yF5gc.1nmp2.FycvbRrfxTjkQ_Vq3qjUK55WIbtEBzi3 oXmlF7HeymXJlHWdIfsbbSP3NTjJB8X6ZRH5WMZ49RAlh0Hkt5DDDkzOxyBA NksrcozaSXOzbdBxweTGQOhFQJZNBqcGOrg-- X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) Subject: Re: Random number generators From: Pedro Giffuni In-Reply-To: <20150317060310.GA21975@troutmask.apl.washington.edu> Date: Tue, 17 Mar 2015 07:10:46 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> To: Steve Kargl X-Mailer: Apple Mail (2.2070.6) 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 12:10:56 -0000 > Il giorno 17/mar/2015, alle ore 01:03, Steve Kargl = ha scritto: >=20 > On Mon, Mar 16, 2015 at 11:22:31PM -0500, Pedro Giffuni wrote: >> Hi; >>=20 >> 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. >>=20 >> 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: >>=20 >> = http://git.musl-libc.org/cgit/musl/commit/?id=3D20d01d83b5a13c77805976e7c5= 20f566244ba3ff = >>=20 >> 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. >>=20 >> Pedro. >>=20 >> [1[ http://www.tedunangst.com/flak/post/random-in-the-wild >>=20 >>=20 >=20 > I suppose it depends on what you want to accomplish. MT > can be a horrible thing to use. See the history of=20 > 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.=20 >=20 Oh, absolutely, I am considering something like this for OpenOffice. Apache OpenOffice (and LibreOffice, I think) is using MT (from Boost) but the seeding is not done properly. > 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. >=20 Yes, the problem is the that libc requires a single 32 (or 31) bit seed. Given that restriction, our existing generator is not bad. Enforcing = something better breaks the API and is not really practical to get crypto-grade = randomness for stuff like refreshing a slide in a presentation anyways. The musl libc approach seemed reasonable but I haven=E2=80=99t looked at = the base random generator there (I=E2=80=99ve heard the glibc one is not = good at all). Pedro.