Date: Tue, 17 Mar 2015 13:32:17 -0500 From: Pedro Giffuni <pfg@FreeBSD.org> To: Steve Kargl <sgk@troutmask.apl.washington.edu> Cc: freebsd-numerics@FreeBSD.org Subject: Re: Random number generators Message-ID: <55087331.4060709@FreeBSD.org> In-Reply-To: <20150317170737.GA24682@troutmask.apl.washington.edu> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <F6137E2C-FDF2-46B3-BFC2-1975AFA40951@FreeBSD.org> <20150317170737.GA24682@troutmask.apl.washington.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?55087331.4060709>