複数環境で再利用可能な疑似乱数 xorshift

ほとんどの言語で擬似乱数発生機能を標準的に持っているが、ソーシャルゲーム等で、幾つかの箇所（スマフォの中 AND サーバ）で同じ系列の乱数になったほうが都合がよいことがある。

必然的に、さまざまな言語で実装する必要があり、また乱数列の維持が少ないメモリで出来るのが望ましい。

疑似乱数としてはメルセンヌ・ツイスタが非常に有名で、様々な言語に標準的に実装されているが、2^19937-1 の長周期を誇る一方、2496バイトのワーキングメモリを要するため、本件のような需要には向かない。

メルセンヌ・ツイスタ - Wikipedia

そこでxorshift

代表的なものが xorshift で、最低でも 2^32-1 程度の周期が期待できる上に、32bit * n のデータを保存しておけば、完全に同一の乱数列が期待できる。 乱数の品質に妥協できるなら、十分に考慮の余地がある。

演算ビット長を意識しつつ、ビット演算子のある言語であれば、容易に実装できるだろう。後述のとおりbashですら可能である。

Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 – びりあるの研究ノート

wikipediaに実に手頃なC言語のサンプル実装が載っている。

Xorshift - Wikipedia

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

XorShift.js · GitHub

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

LuaでXorShiftかいてみたよ - ごちゃログぴこっ

-- 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

XorShift · GitHub

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

Xorshiftを移植してみた - Qiita

Repl.it - Xorshift32

-- 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