[Development] CSPRNG vs DPRNG

[Thiago Macieira]

On quinta-feira, 12 de outubro de 2017 09:23:13 PDT Matthew Woehlke wrote:
> The last time I found myself in need of a graphic/game quality PRNG, I
> tried fiddling with both rand48 (POSIX) and C++11 MT, and ended up using
> this instead:
> 
>  m_seed = ( ( 19073486328125 * m_seed ) + 1 ) & 0x7fffffffffffffff;
>  return ldexp( static_cast< double >( m_seed ), -63 );
> 
> While I am not an expert in RNG's, from the bit of reading I did around
> the time, it was not obvious to me how MT is better than a well crafted LCG.
> 
> According to my notes, "empirical testing indicates that [the above] is
> about 30% faster than mt19937_64". I suppose, however, it's possible
> that the improvement has something to do with my final output being
> [0..1) real numbers rather than integers.

The conversion to double via ldexp is what generateDouble() does in the new 
class and is optional. Though I will take a look now to see if using ldexp() 
produces better code than

return double(generate64()) / (double((std::numeric_limits<quint64>::max)()) + 
1);

> (I don't recall any more where I got the constants for that particular
> LCG, but I believe that particular LCG is known as a "good"
> implementation. At any rate, I'm not the only person to use that
> particular LCG.)

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;

Your constants are:
  __a = 19073486328125
  __c = 1
  __m = 9223372036854775808

The C++ library's provided engines are:
minst_rand0
  __a = 16807
  __c = 0
  __m = 2147483647
minst_rand
  __a = 48271
  __c = 0
  __m = 2147483647

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.

One final note: libc++ has this:
  typedef minstd_rand0 default_random_engine;
libc++ has this:
 typedef minstd_rand default_random_engine;
MSVC has this:
 typedef mt19937 default_random_engine;

I wasn't planning on documenting that the deterministic PRNG would produce the 
same sequence on all platforms, but I was planning on providing it anyway. So 
we should choose the engine with care and not change.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel Open Source Technology Center