From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:32:08 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 D1466190 for ; Tue, 17 Mar 2015 18:32:08 +0000 (UTC) Received: from nm9-vm0.bullet.mail.bf1.yahoo.com (nm9-vm0.bullet.mail.bf1.yahoo.com [98.139.213.154]) (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 874E36AD for ; Tue, 17 Mar 2015 18:32:07 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426617121; bh=OpG+3HnjCtRUGp0a0hxwjcpGwZJYcusMu80UQTmyGi0=; h=Date:From:To:CC:Subject:References:In-Reply-To:From:Subject; b=YdjeeuvWBGTFahrXk5zGh6za3uP1cJtkSX30vk/MUVakpP0dE1dQUpPVALj1oQxdc9xLobf3rk7JpIu8fnUYUot5TNZV2fNixa46KPngHs/izXG5PCWcgsK6s4I9qqIv2pI4wBb1PRoI4O7OylsTIZYF0TnjpvJVABN3LIUCDZDJieTFldSuO2HcK/Xu/fCAJM36XlofErSx3z0fLMduRu8k4gM652sRoadjgXnIe3FB/5T40PF9sdI9Gfm7kzCCM0+I7HasUYO/6OjMaRHB2nQJNntTa/o/doDe7ioB1Y7+y2DvGnlmdszviN9xtHHhkfWO8IoyiZ2ef3PsbUfvvA== Received: from [66.196.81.173] by nm9.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:32:01 -0000 Received: from [98.139.211.198] by tm19.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:32:01 -0000 Received: from [127.0.0.1] by smtp207.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:31:57 -0000 X-Yahoo-Newman-Id: 594839.31495.bm@smtp207.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: CEKAuWMVM1meLbndl5aXIqHtQcRGV7m5MmWi.PrI9FKl4EJ G4JWFDikstGcnwiIdUrc0RitD9W3DBFTyeGciWLWU0oSVVt4c9Jr.ZeJ9u._ U0Tsir548ZrwCz3odSp4SWYmRVltOZ0o7CoPwqpT8tVQ0CnHsfGyJsXWB18S sRSmIZhb3p35rSOWn_a0g6dUuFtPxN.OIXqn0LjtEYq_NdxrvkZBPZXA_XWg 5UMg9OcP1Ewc9rREIVtsMjO9BjhDChe0gfNkfKu6EMlujHKUe5.8enSEPgwB ei_Nhl6a8XRHFeiyJ5ycwArP49kF68x3QQaT6JPi4VK.WzHyVqKu1Uk8eSlj xmhMf.qLD8JHYWD3VFV3XhSJCNmsD8ZCj2v_LEJUJVM.2xN.lWgsipH8VErU 23c4HMtQrMmoDeEqCIHojdGqAynfhm0rli59iU0ribvvHZoEsyvtbN_bhYcB 9jwF5lv4rrxS6mUzQ5rlAWzsfU2yhaiv_493egrDE_YT0GLNyyRgfmZuBLzM L7_m.srPx6jxXe3xmO9Btxl0srYbTv3om X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Message-ID: <55087331.4060709@FreeBSD.org> Date: Tue, 17 Mar 2015 13:32:17 -0500 From: Pedro Giffuni User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: Steve Kargl Subject: Re: Random number generators References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <20150317170737.GA24682@troutmask.apl.washington.edu> In-Reply-To: <20150317170737.GA24682@troutmask.apl.washington.edu> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit 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 18:32:09 -0000 On 03/17/15 12:07, Steve Kargl wrote: > On Tue, Mar 17, 2015 at 07:10:46AM -0500, Pedro Giffuni wrote: >>> 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. >>> >> 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?t looked at the >> base random generator there (I?ve heard the glibc one is not good at all). >> > GM's kiss generator has a period of 2**123. The manpage > for random(3) claims a period of about 2**35. The rand(3) > manpage does not give a period, but I suspect it is well > short of 2**123. I just started to look at the original KISS. It appears to be a combination of three different pseudo random generators. In particular it uses static unsigned long Q[4194304] and seeds it with CNG+XS. I am tempted to just seed it with a crypto random source instead of using an LCG. This is not for libc, just for entertainment purposes though :). > The code that follows my sig uses. a Lehmer LCG generator to > provide the 4 seeds needed for kiss. The Lehmer LCG takes a > single 32 bit seed. If reseed() is not called prior to calling > kiss(), then a default set of seeds is used. If the argument > to reseed() is 0 or 1, then the default set of seeds is used. > It should be straight forward to map reseed() to srand() and > kiss() to rand(). Do note that range kiss() is (0,UINT_MAX], > so one needs to subtract 1 to get [0,UINT_MAX-1) if 0 needs > to be in the range. > > To use this code in preference to random(3) (and in violation of > POSIX?), initstate() and setstate() would need to muck with the > internal state of kiss(). This is certainly possible, but I > don't do it below. > Interesting. I don't really want to break POSIX but we have 3 pseudo random generators: rand(), random() and rand48(). It would be really nice if we could change one to be modern (and fast) although not crypto friendly. FWIW, the Playstation 4 carries Mersenne Twister in their credits along with FreeBSD's libc and kernel so someone has a use for a faster pseudo-random generator and a better period than those we carry in libc. Pedro.