Date: Tue, 17 Mar 2015 07:10:46 -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: <F6137E2C-FDF2-46B3-BFC2-1975AFA40951@FreeBSD.org> In-Reply-To: <20150317060310.GA21975@troutmask.apl.washington.edu> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
> Il giorno 17/mar/2015, alle ore 01:03, Steve Kargl = <sgk@troutmask.apl.washington.edu> 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 = <http://git.musl-libc.org/cgit/musl/commit/?id=3D20d01d83b5a13c77805976e7c= 520f566244ba3ff> >>=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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?F6137E2C-FDF2-46B3-BFC2-1975AFA40951>