CODEWITHSUNDEEP
c++randomc++20
PavelDev
PavelDev

Reputation: 683

How to correctly implement a function that will generate pseudo-random integers with C++20

I want to note that in C++ the generation of pseudo random numbers is overcomplicated. If you remember about old languages like Pascal, then they had the function Random(n), where n is integer and the generation range is from 0 to n-1. Now, going back to modern C++, I want to get a similar interface, but with a function random_int(a,b), which generates numbers in the [a,b].

Consider the following example:

#include <random>
namespace utils
{
namespace implementation_details
{
    struct eng_wrap {
        std::mt19937 engine;
        eng_wrap()
        {
            std::random_device device;
            engine.seed(device());
        }
        std::mt19937& operator()()
        {
            return engine;
        }
    };
    eng_wrap rnd_eng;
}

template <typename int_t, int_t a, int_t b> int_t random_int()
{
    static_assert(a <= b);
    static std::uniform_int_distribution<int_t> distr(a, b);
    return distr(implementation_details::rnd_eng());
}
}

You can see that the distr is marked with the static keyword. Due to this, repeated calls with the same arguments will not cause the construction of the type std::uniform_int_distribution.

In some cases, at the compilation time we do not know the generation boundaries. Therefore, we have to rewrite this function:

template <typename int_t> int_t random_int2(int_t a, int_t b)
{
    std::uniform_int_distribution<int_t> distr(a, b);
    return distr(implementation_details::rnd_eng());
}

Next, suppose the second version of this function is called more times:

int a, b;
std::cin>>a>>b;

for (int i=1;i!=1000000;++i)
    std::cout<<utils::random_int2(a,b)<<' ';

Question

  1. What is the cost of creating std::uniform_int_distribution in each iteration of the loop?
  2. Can you suggest a more optimized function that returns a pseudo-random number in the passed range for a normal desktop application?

Upvotes: 0

Views: 239

Answers (2)

Davis Herring
Davis Herring

Reputation: 40013

If you want to use the same a and b repeatedly, use a class with a member function—that’s what they’re for. If you don’t want to expose your rnd_eng (choosing instead to preclude useful multithreaded clients), write the class to use it:

template<class T>
struct random_int {
  random_int(T a,T b) : d(a,b) {}
  T operator()() const {return d(implementation_details::rnd_eng());}
private:
  std::uniform_int_distribution<T> d;
};

Upvotes: 1

Quuxplusone
Quuxplusone

Reputation: 27310

IMO, for most simple programs such as games, graphics, and Monte Carlo simulations, the API you actually want is

static xoshiro256ss g;

// Generate a random number between 0 and n-1.
// For example, randint0(2) flips a coin; randint0(6) rolls a die.
int randint0(int n) {
    return g() % n;
}

// This version is useful for games like NetHack, where you often
// want to express an ad-hoc percentage chance of something happening.
bool pct(int n) {
    return randint0(100) < n;
}

(or substitute std::mt19937 for xoshiro256ss but be aware you're trading away performance in exchange for... something. :))

The % n above is mathematically dubious, when n is astronomically large (e.g. if you're rolling a 12297829382473034410-sided die, you'll find that values between 0 and 6148914691236517205 come up twice as often as they should). So you may prefer to use C++11's uniform_int_distribution:

int randint0(int n) {
    return std::uniform_int_distribution<int>(0, n-1)(g);
}

However, again be aware you're gaining mathematical perfection at the cost of raw speed. uniform_int_distribution is more for when you don't already trust your random number engine to be sane (e.g. if the engine's output range might be 0 to 255 but you want to generate numbers from 1 to 1000), or when you're writing template code to work with any arbitrary integer distribution (e.g. binomial_distribution, geometric_distribution) and need a uniform distribution object of that same general "shape" to plug into your template.

The answer to your question #1 is "The cost is free." You will not gain anything by stashing the result of std::uniform_int_distribution<int>(0, n-1) into a static variable. A distribution object is very small, trivially copyable, and basically free to construct. In fact, the cost of constructing the uniform_int_distribution in this case is orders of magnitude cheaper than the cost of thread-safe static initialization.

(There are special cases such as std::normal_distribution where not-stashing the distribution object between calls can result in your doing twice as much work as needed; but uniform_int_distribution is not one of those cases.)

Upvotes: 0

Related Questions