[Development] CSPRNG vs DPRNG
mwoehlke.floss at gmail.com
Thu Oct 12 19:39:26 CEST 2017
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.)
More information about the Development