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

[Andrey Chernov]

On 31.05.2016 12:58, Bruce Evans wrote:
> On Tue, 31 May 2016, Andrey Chernov wrote:
> 
>> On 31.05.2016 9:48, Bruce Evans wrote:
>>>> Perhaps you can find some ideas, answers and PRNG comparison in the
>>>> original paper:
>>>> http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
>>>
>>> The ones with Mersenne primes and tweaked Mersenne primes in the
>>> reference
>>> (lanl?) given by pfg@ seem OK.
>>
>> It should be again correctly implemented to not overflow 64bit (as any
>> other 64bit generator too).
>>
>> Moreover, it have visible patterns in the low order bits. This one from
>> the same site is better
>> http://nuclear.llnl.gov/CNP/rng/rngman/node7.html
>> but still have some pattern too and 61-bit. Next one does not suffer
>> from the pattern at all
>> http://nuclear.llnl.gov/CNP/rng/rngman/node8.html
>> but is 2^64-2^10+1.
> 
> That's the tweaked Mersenne prime one.
> 
> Surely there is a pattern in the bits for all of these, and the better
> ones just hide the pattern better from normal uses and tests?

Excepting bad first one from pfg@
http://nuclear.llnl.gov/CNP/rng/rngman/node4.html
as I understand, they not hide (i.e. drop) the pattern but mix it with
other part in calculations, it cause whole range reduced.

>> You can download SPRNG library implementing all of them here:
>> http://www.sprng.org/RNG/
>> For me it is overcomplicated.
> 
> The general case is certainly too complicated.  It would let the user
> specify all the parameters for the LCG and generate optimal code for
> the choice on the fly.  Maybe also change the parameters with the seed.
> But even most implementors don't know how to choose the parameters.
> That's just for the not so good LCG family of RNGs.

All mentioned PRNGs with exact parameters (info.h) can be found in the
subdirs under SRC, f.e. lcg64 or pmlcfg. They are still looks
complicated and use GMP Bignum library for calculations.

>> For fixups, see full
>> explanation in the comment of stdlib/div.c
> 
> That was what I was complaining about.  div.c is for C90 (misspelled
> "ANSI").  div.c hasn't caught up with C99.  C99 broke this by changing
> the rules for integer division to disallow correct rounding for and
> require consistently incorrect rounding.  Correct rounding for a
> positive divisor is towards minus infinity so that the remainder is
> not negative.  This is modulo arithmetic and has good algebraic
> properties.  C99 requires rounding minus infinity, at least for positive
> divisors, under the extension "reliable integer division".  In C90,
> the rounding is implementation- defined, so it may be correct, but it
> is "unreliable" since it can be anything.
> 
> In C90, div() is specified as giving "reliable" division, and that is
> what the fixups implement.  This now wastes time to change nothing.
> If the hardware does correct rounding, then the compiler already
> had to do the fixup and id should have produced good MD code for this.
> The C code then adds not so good MI code.

It seems POSIX says nothing about any fixup and negative results:
"These functions shall compute the quotient and remainder of the
division of the numerator numer by the denominator denom. If the
division is inexact, the resulting quotient is the long integer (for the
ldiv( ) function) or long long integer (for the lldiv( ) function) of
lesser magnitude that is the nearest to the algebraic quotient. If the
result cannot be represented, the behavior is undefined; otherwise, quot
* denom+rem shall equal numer."
Does it mean that this fixup should be removed?