🍣
複数環境で再利用可能な疑似乱数 xorshift
ほとんどの言語で擬似乱数発生機能を標準的に持っているが、ソーシャルゲーム等で、幾つかの箇所（スマフォの中 AND サーバ）で同じ系列の乱数になったほうが都合がよいことがある。
必然的に、さまざまな言語で実装する必要があり、また乱数列の維持が少ないメモリで出来るのが望ましい。
疑似乱数としてはメルセンヌ・ツイスタが非常に有名で、様々な言語に標準的に実装されているが、2^19937-1 の長周期を誇る一方、2496バイトのワーキングメモリを要するため、本件のような需要には向かない。
そこでxorshift
代表的なものが xorshift で、最低でも 2^32-1 程度の周期が期待できる上に、32bit * n のデータを保存しておけば、完全に同一の乱数列が期待できる。 乱数の品質に妥協できるなら、十分に考慮の余地がある。
演算ビット長を意識しつつ、ビット演算子のある言語であれば、容易に実装できるだろう。後述のとおりbashですら可能である。
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 – びりあるの研究ノート
wikipediaに実に手頃なC言語のサンプル実装が載っている。
uint32_t xor(void) {
static uint32_t y = 2463534242;
y = y ^ (y << 13); y = y ^ (y >> 17);
return y = y ^ (y << 5);
}
uint32_t xor64(void) {
static uint64_t x = 88172645463325252ULL;
x = x ^ (x << 13); x = x ^ (x >> 7);
return x = x ^ (x << 17);
}
uint32_t xor96(void) {
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
uint32_t t;
t = (x ^ (x << 3)) ^ (y ^ (y >> 19)) ^ (z ^ (z << 6));
x = y; y = z;
return z = t;
}
uint32_t xor128(void) {
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t;
t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
それぞれ、staticの変数を持ち、その初期値が乱数列の種であり、すべての変数の値が毎回書き換わることに注意。
これらの変数をなんらかの方法で保存しておけば、疑似乱数列を任意のタイミングから再現可能となる。
標準 random.cs
C#/.NET の標準 Randomはあまり品質がよくないことで知られている。
簡易な代替策としては xorshift は有効だろう。
- How reliable is the C# random number generator? : csharp
- c# - What is the quality of Random class implementation in .NET? - Stack Overflow
xorshift実装
std.random - D Programming Language
nim-lang
標準では類似の xorshiro128+ を実装している
random
Xorshift のNimでの 実装（３２ビット版だけ） - Qiita
JS
function XRandom(seed) {
this.x = 123456789;
this.y = 362436069;
this.z = 521288629;
this.w = seed;
}
XRandom.prototype.rand = function () {
var t;
t = this.x ^ (this.x << 11);
this.x = this.y;
this.y = this.z;
this.z = this.w;
this.w = this.w=(this.w^(this.w>>19))^(t^(t>>8))
return this.w;
}
シード付き擬似乱数 Xorshift - JavaScript実用サンプルコード解説付き
'use strict';
(function() {
const _t = init('com.crocro.util');
// Xorshift | シード付き擬似乱数
// new Xors(n);でオブジェクトを作成して使います。
_t.Xorshift = function(n) {
let x, y, z, w;
// シード
this.seed = function(n) {
x = 123456789; y = 362436069; z = 521288629; w = 88675123;
if (typeof n === "number") {w = n;}
}
// ランダム
this.rnd = function() {
const t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w^(w>>19))^(t^(t>>8));
}
// 初回実行
this.seed(n);
};
// 初期化用関数
function init(p) {
try {return module.exports = {}} catch(e) {}
return ((o, p) => {
p.split('.').forEach(k => o = o[k]||(o[k]={}));
return o})(window, p);
};
})();
lua
-- XorShift: A random number generator
-- ported to Lua by gocha
module("xorshift", package.seeall)
require "bit"
local seed128 = {}
function randomseed(s)
for i = 0, 3 do
-- s = 1812433253 * (bit.bxor(s, bit.rshift(s, 30))) + i
s = bit.bxor(s, bit.rshift(s, 30))
local s_lo = bit.band(s, 0xffff)
local s_hi = bit.rshift(s, 16)
local s_lo2 = bit.band(1812433253 * s_lo, 0xffffffff)
local s_hi2 = bit.band(1812433253 * s_hi, 0xffff)
s = bit.bor(bit.lshift(bit.rshift(s_lo2, 16) + s_hi2, 16),
bit.band(s_lo2, 0xffff))
-- s = bit.band(s + i, 0xffffffff)
local s_lim = -bit.tobit(s)
-- assumes i<2^31
if (s_lim > 0 and s_lim <= i) then
s = i - s_lim
else
s = s + i
end
seed128[i+1] = s
end
end
function random_int32()
local t = bit.bxor(seed128[1], bit.lshift(seed128[1], 11))
seed128[1], seed128[2], seed128[3] = seed128[2], seed128[3], seed128[4]
seed128[4] = bit.bxor(bit.bxor(seed128[4], bit.rshift(seed128[4], 19)), bit.bxor(t, bit.rshift(t, 8)))
return seed128[4]
end
function random(...)
-- local r = xorshift.random_int32() * (1.0/4294967296.0)
local rtemp = xorshift.random_int32()
local r = (bit.band(rtemp, 0x7fffffff) * (1.0/4294967296.0)) + (bit.tobit(rtemp) < 0 and 0.5 or 0)
local arg = {...}
if #arg == 0 then
return r
elseif #arg == 1 then
local u = math.floor(arg[1])
if 1 <= u then
return math.floor(r*u)+1
else
error("bad argument #1 to 'random' (internal is empty)")
end
elseif #arg == 2 then
local l, u = math.floor(arg[1]), math.floor(arg[2])
if l <= u then
return math.floor((r*(u-l+1))+l)
else
error("bad argument #2 to 'random' (internal is empty)")
end
else
error("wrong number of arguments")
end
end
require "xorshift"
local randomseed = xorshift.randomseed
local random = xorshift.random
randomseed(os.time())
for i = 1, 10 do
local rf = random()
local ri = math.floor(rf * 10)
print(ri, rf)
end
go
Xorshift のGoでの実装 (３２ビット版だけ） - Qiita
package main
import "fmt"
type xorshift32 struct {
seed uint32
}
func (r *xorshift32) rand() uint32 {
y := r.seed
y = y ^ (y << 13)
y = y ^ (y >> 17)
y = y ^ (y << 5)
r.seed = y
return y
}
func uniform(generator xorshift32) func() float32 {
inner := func() float32 {
return float32(generator.rand()) / float32(^uint32(0))
}
return inner
}
func calcPi() {
xor32 := xorshift32{seed: 2463534242}
u01 := uniform(xor32)
N := 100000000
counter := 0
for i := 0; i < N; i++ {
x := u01()
y := u01()
if x*x+y*y < 1.0 {
counter += 1
}
}
fmt.Println(4 * float64(counter) / float64(N))
}
func test1() {
xor32 := xorshift32{seed: 2463534242}
for i := 0; i < 10; i++ {
fmt.Println(xor32.rand())
}
}
func main() {
test1()
calcPi()
}
Xorshift* 1024 (essential fragment) · GitHub
var s0 = [16]uint64{
0xEA221D1E5C8DB483,
0xF89369282348A220,
0x7022326276090608,
0x1618FCC12E583E30,
0xF7E7C005F85EFC69,
0x132B746F9C2FF047,
0x338324A69CBDC6B5,
0x2B91B21FAAB58FE0,
0x85CB192105B8B12B,
0x5A9EC4772C1B642D,
0xFEA936CB4A0CEA20,
0x6865516844ED9BBD,
0x16C12E5DCC3D7365,
0x0BBDE3B5363FA6E9,
0xD454C1D29E450885,
0x480EB817028DB197,
}
type xorshiftstar struct {
s [16]uint64
p uint8
}
// global instance
var (
s = s0 // copy reference init state.
xss = &xorshiftstar{s, 0} // global instance uses s
)
/// algorithm /////////////////////////////////////////////////////////////
// NOTICE-BEGIN - original source: Xorshift - wikipedia.org. adapted for Go.
const xss_magic = uint64(1181783497276652981)
const (
shift_A = 31 // 23
shift_B = 11 // 17
shift_C = 30 // 30
)
func (s *xorshiftstar) next() uint64 {
var s0 = s.s[s.p]
s.p = (s.p + 1) & 0xF
var s1 = s.s[s.p]
s1 ^= s1 << shift_A
s1 ^= s1 >> shift_B
s0 ^= s0 >> shift_C
// update state
s.s[s.p] = s0 ^ s1
return s.s[s.p] * xss_magic
}
// NOTICE-END - original source: Xorshift - wikipedia.org. adapted for Go.
/// api ///////////////////////////////////////////////////////////////////
C#
http://www.jstatsoft.org/v08/i14/paper · GitHub
using System;
namespace xorshift
{
public class XorShift
{
private static long _x = 123456789;
private static long _y = 362436069;
private static long _z = 521288629;
private static long _w = DateTime.Ticks;
/// <summary>
/// Initializes a new instance of the <see cref="xorshift.XorShift"/> class.
/// </summary>
public XorShift (){ Reseed(DateTime.Ticks%100);}
/// <summary>
/// Reseed field values.
/// </summary>
public void Reseed(int seed)
{
for (int i = 0; i < seed; i++) { xor128 (); }
}
/// <summary>
/// Generate 128bits random value
/// </summary>
public long xor128()
{
var t = _x ^ (_x << 11);
_x = _y; _y = _z; _z = _w;
return _w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
}
}
}
C
unsigned long xorshift() {
static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
unsigned long t;
t = (x ^ (x << 11));
x = y;
y = z;
z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w;
}
Haskell
-- CC0 http://creativecommons.org/publicdomain/zero/1.0/
import Data.Bits (xor, shiftL, shiftR)
import Data.Time.Clock.POSIX (getPOSIXTime)
import Data.Word (Word32)
import Data.IORef (newIORef, readIORef, writeIORef)
import Control.Monad (sequence_)
word32MaxNext :: Num a => a
word32MaxNext = 2 ^ 32
getSeed :: IO Word32
getSeed = do
t <- getPOSIXTime
let ret = floor $ t * 1e9 :: Word32
if ret == 0 then getSeed else return ret
getNext :: Word32 -> Word32
getNext seed = s3 where
s1 = seed `xor` (shiftL seed 13)
s2 = s1 `xor` (shiftR s1 17)
s3 = s2 `xor` (shiftL s2 5)
getFloat :: Fractional a => Word32 -> a
getFloat w32 = (fromIntegral w32) / word32MaxNext
rand :: Fractional a => Word32 -> IO (IO a)
rand seed = do
s <- newIORef seed
return $ do
oldSeed <- readIORef s
let newSeed = getNext oldSeed
writeIORef s newSeed
return $ getFloat newSeed
main :: IO ()
main = do
rnd <- rand =<< getSeed
sequence_ $ replicate 10 $ print =<< rnd
bash
シェルスクリプトで乱数生成を実装する(Xorshift32) - Qiita
xorshift32() {
# 計算途中の値はsetで位置パラメータ$1に再代入して無駄にグローバル変数を使わないようにしています
set -- $(( $1 ^ (($1 << 13) & 0xFFFFFFFF) ))
set -- $(( $1 ^ ($1 >> 17) ))
set -- $(( $1 ^ (($1 << 5) & 0xFFFFFFFF) ))
xorshift32=$1 # 計算結果をechoではなく変数で返しているのは遅いコマンド置換を避けるためです
}
state=2463534242
for i in $(seq 10000); do
xorshift32 "$state"
state=$xorshift32
echo "$state"
done
Discussion