[Development] CSPRNG vs DPRNG

[Matthew Woehlke]

On 2017-10-12 13:06, Thiago Macieira wrote:
> libstdc++'s LCG does:
> 	_M_x = __detail::__mod<_UIntType, __m, __a, __c>(_M_x);
> 	return _M_x;
> 
> which is
> 
>  _M_x = (__a * _M_x + __c) % __m;

...and yet, for some reason when I tested it, it was *quite* slow.
Noticeably slower than MT, and *much* slower than my own implementation.
I was very surprised. (But maybe it's been fixed; I was trying on I
think gcc 4.8, if that.)

> I don't know anything about LCGs to be able to say if one is better than any 
> other, aside from the fact that yours requires 64-bit integer multiplication.

The constants do matter to an extend; different choices produce better
or worse "quality" of random numbers.

https://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf is a good
(and somewhat seminal, I think) read in the field.

64-bit math is sort of required, at least if you want the output to be
anything near 64 bits. (Mine produces I think 48; 63 bits go *int*
ldexp, but of course since the output is [0..1), not that many come
out... although if everything gets inlined "right" and you wind up using
80-bit FP registers, then maybe you would get all 63...)

If you don't have 64-bit math, you probably are not going to get better
than 32-bit output per step without a horrible performance penalty. (If
you only care about 32-bit output, then yeah, I would use different
constants for the LCG.)

-- 
Matthew