CODEWITHSUNDEEP
c++c++11random
ThomasMcLeod
ThomasMcLeod

Reputation: 7769

C++ numerics lib: std::uniform_int_distribution<>, change bounds of distribution between calls

I have code similar to the following:

    vector<int> vec;
    // stuff vector here

    random_device rd;
    minstd_rand generator(rd());
    uniform_int_distribution<unsigned> dist(0 , vec.size() - 1);
    while (vec.size() > 0)
    {
       auto it = vec.begin() + dist(generator);
       // use *it for something
       swap(*it, *(vec.end() - 1));
       vec.pop_back();
   }

I know I can construct/destruct a local distribution inside the loop. But I'd rather just adjust the bounds of dist inside the loop. Can I do this?

Upvotes: 1

Views: 661

Answers (2)

Columbo
Columbo

Reputation: 60989

What about param?

dist.param( decltype(dist)::param_type(otherMin, otherMax) );

C++11 standard (and following ones), [rand.req.dist]/9:

For each of the constructors of D taking arguments corresponding to parameters of the distribution, P shall have a corresponding constructor subject to the same requirements and taking arguments identical in number, type, and default values.

Upvotes: 3

DarthGizka
DarthGizka

Reputation: 4675

<random> has some decent parts, and the generators it contains are at least servicable for many purposes. However, the library and its interfaces are very far from mature. Hence you need to build your own header/library to supply the missing parts, or roll out big guns like boost or the code from Numeric Recipes.

One quick and easy way of obtaining uniform integer derivates is to multiply uniform floats in the range [0,1) with the modulus and truncating. That spreads the bias all over the range and it is good enough for many off-the-cuff uses.

By contrast, the standard method of taking the remainder of an integer derivate modulo the range collects the bias at the beginning of the range. E.g. the famous rand() % modulus.

Case in point: if your modulus happens to be 2/3 of the derivate's natural modulus (e.g. 0xAAAAAAAAu for 2^32) then all results in the first half the result range are exactly twice as likely as those in the upper half of the result range. Not recommended for quality code.

To get an unbiassed integer derivate, use the rejection method. Here is one example that uses a full-size random integers as a basis. You can template it on word size and generator, stuff it in your 'fix-the-std' header and be done for all time:

uint64_t random_uint64 ();

uint64_t random_uint64 (uint64_t modulus)
{
   if (modulus)
   {
      for ( ; ; )
      {
         uint64_t raw_bits = random_uint64();
         uint64_t result = raw_bits % modulus;
         uint64_t check = uint64_t(raw_bits - result + modulus);

         if (check >= raw_bits || check == 0)
         {
            return result;
         }
      }
   }

   return 0;
}

std::uniform_int_distribution<> does something very similar internally... but there the logic is well protected against industrial esponiage by the usual hundreds of lines of fluff, and the awkward interface ensures that people cannot simply use that functionality just because they feel like it.

Just for completeness, here's a simple and fast generator of excellent, proven quality (Sebastiano Vigna's xorshift64*) that makes a nice all-round generator when the extremely long period of a big gun like xorshift1024* is not needed:

uint64_t random_seed64 = 42;

uint64_t random_uint64 ()
{
   uint64_t x = random_seed64;

   x ^= x >> 12;  x ^= x << 25;  x ^= x >> 27;

   random_seed64 = x;

   return x * 2685821657736338717ull;
}

The generators included in the standard all have their peculiarities and problems, you have to know their strengths and weaknesses in order to make a good choice. If you're not aiming for a PhD in random number generation and computational statistics then you might be better off using tried and trusted code that is of proven quality.

Upvotes: 1

Related Questions