Xorshift#
Xorshift は疑似乱数列生成法の1つ。
排他的論理和とビットシフトのみで計算するため、計算が高速で、実装もしやすい。
Marsaglia, G. (2003). Xorshift rngs. Journal of Statistical software, 8, 1-6.
理論#
排他的論理和#
排他的論理和（XOR）は、2つの演算対象のうち片方だけが真（1）であれば真（1）になる演算。多くの言語で^が演算子になる。
x |
y |
XOR |
|---|---|---|
0 |
0 |
0 ^ 0 = 0 |
0 |
1 |
0 ^ 1 = 1 |
1 |
0 |
1 ^ 0 = 1 |
1 |
1 |
1 ^ 1 = 0 |
2進数の1桁だけを見る（変数が\(\{0,1\}\)のいずれかの値をとり、2になったら0になるとする）と、XORは足し算のようになっている。
x |
y |
XOR |
足し算 |
|---|---|---|---|
0 |
0 |
0 ^ 0 = 0 |
0 + 0 = 0 |
0 |
1 |
0 ^ 1 = 1 |
0 + 1 = 1 |
1 |
0 |
1 ^ 0 = 1 |
1 + 0 = 1 |
1 |
1 |
1 ^ 1 = 0 |
1 + 1 = 2 → 0 |
プログラミングでの表現#
2進数 0b0101 (=5)と 0b0011 (=3) のXORは 0b0110 (=6)になる
y = 0b0101 ^ 0b0011
print(y, bin(y))
6 0b110
ビットシフト#
ビットシフトは、ビット列の中身を左右に移動させる操作。
# 0b11 (=3) を左に1桁ずらして 0b110(=6) にする
0b11 << 1
6
Xorshift#
Xorshift内で用いられる基本的なシフト演算は
x ^ (x << a)
という演算になる（シフトは右シフトでもかまわない）
x = 10
a = 5
x ^ (x << a)
330
Xorshiftの数学的表現#
XOR演算のベクトル表現#
2進数のビット列をベクトルで表すと、XOR演算が足し算という話は、単純にベクトルの和の演算に対応する。
ビットシフトの行列表現#
ビット列をベクトルで表現し、ビットシフト演算を行列で表現することもできる。
例えば、1ビットの左シフトは
という行列で表される。
例えば、0b0110のベクトルに対して掛けると0b1100になる
Xorshiftの行列表現#
XORとビットシフトがベクトルや行列で表現できるため、Xorshiftの基本操作も行列で表すことができる。
ビット列のベクトル\(x, y\)についてのXOR演算 x ^ y のベクトル表現は\(x + y\)となる。
ビット列ベクトルを\(x\)とし、\(a\)ビットの左シフト演算を表す行列を\(L_a\)とすると、ビットシフト演算 x << a は \(L_a x\)で表すことができる。
なのでx ^ (x << a) は
となる。ここで\(I\)は単位行列。
\(T := (I + L_a x)\)とおくと、この行列\(T\)の性質が乱数生成器としての性質に関わる。
\(T\)が可逆なら出力値も一様である
\(T\)の位数（order、その行列を何回掛けたら単位行列になるか）が乱数の周期に関係する
などがある（Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 – びりあるの研究ノート）
実装#
Python#
class Xorshift64:
def __init__(self, seed: int = 0):
self.state = seed
def gen(self):
# https://www.cepstrum.co.jp/hobby/xorshift/xorshift.html にて「特性が良い」とされるパラメータ (3, 35, 14)を使用
x = self.state
x ^= (x << 3)
x ^= (x >> 35)
x ^= (x << 14)
self.state = x
return self.state
# 使用例
rng = Xorshift64(seed=42) # シードは非ゼロで初期化
for _ in range(5):
print(rng.gen())
6193530
732828797610
108066598636560197
12399238436484378965293
1828241189597628788155767877
JavaScript#
JSのMath.random()はseedを固定できないが、Xorshiftなどでseedが指定可能な疑似乱数生成を実装することでJSでも再現性のある乱数が利用可能になる
class Random {
constructor(seed = 88675123) {
this.x = 123456789;
this.y = 362436069;
this.z = 521288629;
this.w = seed;
}
// XorShift
next() {
let t;
t = this.x ^ (this.x << 11);
this.x = this.y; this.y = this.z; this.z = this.w;
return this.w = (this.w ^ (this.w >>> 19)) ^ (t ^ (t >>> 8));
}
// min以上max以下の乱数を生成する
nextInt(min, max) {
const r = Math.abs(this.next());
return min + (r % (max + 1 - min));
}
}
const seed = 1;
const random = new Random(seed);
console.log(random.nextInt(2, 10));
> 5
問題点#
乱数アルゴリズムXorshiftの弱点と改善案 #ゲーム制作 - Qiita
似たシードだと似た乱数が出てくる（Xorshiftに限らない疑似乱数のよくある弱点だが）
派生アルゴリズム#
-
xoshiro (xor-shift-rotate)
xoroshiro (xor-rotate-shift-rotate )
応用例#
GoogleのV8における Math.random() は32ビットのXorshiftを採用しているらしい