乱数 (xor-shift)
概要
乱数を発生させる.周期は $2^{128} - 1$.rand
より速い.
実装
struct xorshift128 {
// If you need a simple implementation, copy from here...
using result_type = uint_fast32_t;
static constexpr result_type MASK = 0x7FFFFFFF;
result_type x, y, z, w;
result_type rnd() {
result_type t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w & MASK;
}
// to here.
xorshift128(result_type seed = 0) : x(123456789), y(987654321), z(1000000007) {
if (seed == 0) {
std::random_device rnd;
seed = rnd();
}
w = seed;
for (int i = 0; i < 50; ++i) rnd();
}
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return MASK; }
result_type operator()() { return rnd(); }
};
using my_random_engine = xorshift128;
my_random_engine engine(28);
void srnd(unsigned s) { engine = my_random_engine(s); }
int rnd() { return engine(); }
int rnd(int r) { return rnd() % r; }
int rnd(int l, int r) { return l + rnd(r - l + 1); }
template <unsigned MOD>
int rnd() {
return rnd() % MOD;
}
double rndf() { return (double)rnd() / my_random_engine::max(); }
double rndf(double r) { return rndf() * r; }
template <typename C>
typename C::value_type sample(const C &c) {
return *std::next(c.begin(), rnd(c.size()));
}
template <typename C, size_t N>
C sample(const C (&c)[N]) {
return c[rnd<N>()];
}