Simpler unhackable random numbers

Правка en1, от snowmanonahoe, 2023-02-01 03:43:59

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, exclusive. 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

Теги c++, random

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский snowmanonahoe 2023-02-01 03:49:10 4 Tiny change: 'rguments, exclusive. T' -> 'rguments, inclusive. T'
en1 Английский snowmanonahoe 2023-02-01 03:43:59 2254 Initial revision (published)