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

[Andrey Chernov]

This implementation of shifts&xors 32-bit and 64-bit PRNGs looks more
reliable than Mersenne primes and don't use Bignums:
http://wwwmaths.anu.edu.au/~brent/ftp/random/xorgens305.tar.gz
PDF article inside.

On 31.05.2016 14:30, Andrey Chernov wrote:
> 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.