It's well known that rand() is evil. The consensus appears to be to use the STL Mersenne twister, and the STL millisecond(?) precision clock as a seed. This is all fine and dandy, but there's a problem, as appears in the linked blog:
for (int i = 1; i < N; i++)
swap(permutation[i], permutation[uniform_int_distribution<int>(0, i)(rng)]);
There's so many words. uniform_int_distribution
is like, 2 really big words. And I hate big words. Fortunately, there's a solution:
#include <bits/stdc++.h>
#include <experimental/random>
// Note: experimental headers are not included by bits/stdc++.h
using namespace std;
int main() {
experimental::reseed(chrono::steady_clock::now().time_since_epoch().count());
for (int i = 0; i < 10; i++)
cout << experimental::randint(0, 10) << '\n';
}
randint uses an STL PRNG to return a number in the range of the 2 arguments, inclusive. The PRNG used appears to be implementation-defined (meaning it might be the subtract-with-carry or linear congruential generator), but that's ok, because what we may lose in RNG quality is made up for by the fact that a hacker won't know which generator is being used. (Note: the documentation says the state of the "per-thread" RNG is unpredictable at the beginning of execution. This does not appear to be the case on Codeforces after some cursory testing. Calling reseed()
is still necessary.)
Defined in the experimental/random
header is also experimental::shuffle()
and experimental::sample()
, which both work like their non-experimental counterparts, using the implementation-defined RNG instead of having to make one to pass as argument.
This does have some drawbacks.
Isn't a function object, can't be passed to one of the couple of STL functions that want one
PRNG used is implementation-defined
Experimental header
For these reasons, I see it as a convenient middle ground to a Mersenne twister, when you really just need one number for, say, a hash function.
I personally added the following in my template:
Then I just call
rnd(l, r)
to get a random integer between $$$l$$$ and $$$r$$$ inclusive.Are there any problems with this?
time(NULL) is hackable if someone puts a lot of effort in. In addition, modulo is more likely to give lower vs. higher numbers. Pretend rnd() returns a number between 0 and 11. It is easy to see why 0 and 1 are twice as likely a result than the other numbers.