COMS W4995 C++ Deep Dive for C Programmers

Random Number Generators

Lecture outline

rand1

1. Random number generation in C - code walk-thru

   • Basically calling random() but arranged in C++ style
   • Seeding the generator with current time

2. Random number generation in C++ - code walk-thru

   • std::random_device
     • implementation-dependent non-deterministic random number generator
     • random_device::entropy() returns 0 if it’s deterministic
     • uses /dev/urandom in Linux
   • STL provides numerous engines and distributions

rand2

1. Generating normal-distributed random numbers

   • normal_distribution<> distro { 0.0, 3.5 };
   • code walk-thru

2. Mersenne Twister engine

   • mt19937: predefined specializations of the mersenne_twister_engine class template

   • Mersenne Twister

     • reference: https://en.wikipedia.org/wiki/Mersenne_Twister
     • its period length is a Mersenne prime, 2^19937 - 1
     • fast, but heavy state storage requirement

3. (A little detour to the) Danger of narrowing conversion

   • Subtle bug without lround()

     int x { distro(engine) }; // we get a compiler warning at least
     int x = distro(engine);   // we don't even get a warning here
     

4. Stateful functor

   • Binding engine to distro:

     //int x = lround( distro(engine) );
     
     auto generator = bind(distro, engine);
     int x = lround( generator() );
     

     • Why the same number million times?

   • We can fix it by moving the generator object outside the loop!

   • Alternatively, we can fix it by using std::ref():

     auto generator = bind(distro, ref(engine));
     

     • This will make bind() hold the engine by reference.
     • std::ref() pseudocode overview

   • Or capture distro and engine in a lambda:

     auto generator = 
         //[distro, engine] () { return distro(engine); };           // (1)
         //[distro, engine] () mutable { return distro(engine); };   // (2)
         //[=] () mutable { return distro(engine); };                // (3)
         //[&distro, &engine] () { return distro(engine); };         // (4)
         //[&] () { return distro(engine); };                        // (5)
     int x = lround( generator() );
     

     • (1) does not compile - lambda’s operator() is const by default
     • (2) mutable makes operator() non-const - same as non-working bind
     • (3) is the same as (2); “=” means capture all variables by value
     • (4) and (5) capture by reference, and fix the problem

rand3

1. Very stateful functor

   • Why was it so slow when engine was being copied in the loop?
   • default_random_engine is linear_congruential_engine