ホーム > libalgo

乱数 (xor-shift)

概要

乱数を発生させる.周期は $2^{128} - 1$.rand より速い.

実装

#ifdef _MSC_VER
#include <process.h>
#else
#include <sys/types.h>
#include <unistd.h>
#endif

struct xor128_random {
    uint32_t seed;
    xor128_random(uint32_t s = 0) {
        if (s)
            seed = s;
        else {
#ifdef _MSC_VER
            seed = (uint32_t)time(0) + _getpid() + 1145141919;
#else
            seed = (uint32_t)time(0) + getpid() + 1145141919;
#endif
        }
        for (int i = 0; i < 10; ++i) next();
#ifdef DEBUG
        cerr << "rand seed : " << seed << endl;
#endif
    }

    uint32_t next() {
        static uint32_t x = 123456789, y = 362436069, z = 521288629, w = seed;
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return w;
    }

    int32_t operator()() { return next(); }

    int32_t operator()(int32_t r) { return next_int(r); }

    int32_t operator()(int32_t l, int32_t r) { return next_int(l, r); }

    int32_t next_int(int32_t l, int32_t r) { return l + next() % (r - l + 1); }

    int32_t next_int(int r) { return next() % r; }

    template <int MOD>
    int32_t next_int() {
        return next() % MOD;
    }

    double next_double() { return next() * 0.00000000023283064365386962890625; }

    double next_double(double r) { return next() * 0.00000000023283064365386962890625 * r; }
};

xor128_random rng;

参考文献

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