Date: Mon, 30 May 2016 11:12:54 -0500 From: Pedro Giffuni <pfg@FreeBSD.org> To: Bruce Evans <brde@optusnet.com.au>, "Andrey A. Chernov" <ache@freebsd.org> Cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r300956 - head/lib/libc/stdlib Message-ID: <c9e9ddbc-8e53-366a-96c0-8195c3e0a6ac@FreeBSD.org> In-Reply-To: <20160530110541.I924@besplex.bde.org> References: <201605291357.u4TDv6No071840@repo.freebsd.org> <20160530110541.I924@besplex.bde.org>
next in thread | previous in thread | raw e-mail | index | archive | help
(Interesting discussion)
On 05/29/16 21:17, Bruce Evans wrote:
> On Sun, 29 May 2016, Andrey A. Chernov wrote:
>
>> Log:
>> 1) Unifdef USE_WEAK_SEEDING since it is too obsolete to support and
>> makes
>> reading hard.
>
> Good.
>
>> 2) Instead of doing range transformation in each and every function
>> here,
>> do it single time directly in do_rand(). One "mod" operation overhead
>> is not
>> a big deal, but the code looks nicer and possible future functions
>> additions
>> or PRNG change do not miss range transformations neither have
>> unneeded ones.
>
> The whole implementation is silly. It is manually optimized for 1980's
> compilers. More below.
>
>> 3) Use POSIX argument types for visible functions (cosmetic).
>
> Not sure I like type changes.
>
>> Modified: head/lib/libc/stdlib/rand.c
>> ==============================================================================
>>
>> --- head/lib/libc/stdlib/rand.c Sun May 29 12:21:54 2016 (r300955)
>> +++ head/lib/libc/stdlib/rand.c Sun May 29 13:57:06 2016 (r300956)
>> @@ -48,14 +48,6 @@ __FBSDID("$FreeBSD$");
>> static int
>> do_rand(unsigned long *ctx)
>> {
>> -#ifdef USE_WEAK_SEEDING
>> -/*
>> - * Historic implementation compatibility.
>> - * The random sequences do not vary much with the seed,
>> - * even with overflowing.
>> - */
>> - return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX +
>> 1));
>
> This is a good implementation of a not very good LCG, made very bad by
> botching RAND_MAX. The magic numbers except for RAND_MAX are copied
> from the example in the C90 spec. I think they are good enough there.
> The comment in at least the C99 spec says "// RAND_MAX assumed to be
> 32767". This means that these magic numbers were chosen to work with
> this value of RAND_MAX. (unsigned) longs are used to give a period
> much longer than RAND_MAX and for technical reasons. Taking the modulo
> to many fewer bits than the minimum of 32 for an unsigned long then
> disguises the linearity. The BSD version almost completly breaks this
> on arches with 32 bit longs by taking the modulo to 31 bits (mod 32 bits
> would give complete breakage). Arches with 64-bit longs accidentally
> work a bit better, by the coefficients are poorly chosen -- they should
> be 64 bits and the arithmetic 128 bits.
>
FWIW, there are coefficients for a 64 bit LCG here:
http://nuclear.llnl.gov/CNP/rng/rngman/node4.html
It would be interesting to have a LCG optimized for modern platforms,
even if we cannot produce more than 31 bits due to the standards.
Pedro.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?c9e9ddbc-8e53-366a-96c0-8195c3e0a6ac>