snowmanonahoe's blog

Simpler unhackable random numbers
By snowmanonahoe, history, 15 months ago, In English

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';
}

Try it

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.

Documentation

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
15 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I personally added the following in my template:

mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}

Then I just call rnd(l, r) to get a random integer between $$$l$$$ and $$$r$$$ inclusive.

→ Reply
»
15 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Are there any problems with this?

mt19937 rnd(time(NULL));

for(int i = 0; i < 10; i++)
    cout << rnd() % 10 << ' ';
→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply