Home > libalgo > 乱数 (xor-shift)

乱数 (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>()];
}

参考文献

焼きなまし法ライブラリ2 - nodchipの日記