svn commit: r300956 - head/lib/libc/stdlib

[Pedro Giffuni]

(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.