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 = 0x3FFFFFFF;
    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; }

参考文献

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