xorshift の乱数を逆順で巻き戻す

xorshift について

xorshift はビットシフトと排他的論理和だけで構成される軽量な疑似乱数生成アルゴリズムです。32ビット版と64ビット版があります。

C言語での32ビット版は以下のコードです。

// シード
uint32_t s;

uint32_t xorshift()
{
    s ^= (s << 13);
    s ^= (s >> 17);
    s ^= (s << 5);
    return s;
}

入力はシード値のみで、生成された疑似乱数が次のシード値となります。得られた疑似乱数列は0以外の32ビット空間の値を重複なく全て巡回します。つまり、周期は2³²-1です。 シードの初期値は0以外である必要があります。(シードが0だと0が生成される)

シフト数 (上記のコードの << 13, >> 17, << 5) はいくつか別パターンがありますが、ここでは上記の組で説明します。

逆順に巻き戻す

先に結論を書くと、逆順で巻き戻すコードは以下です。

// シード (正順のものと共通)
uint32_t s;

uint32_t xorshift_rev()
{
    s ^= (s << 5) ^ (s << 10) ^ (s << 15) ^ (s << 20) ^ (s << 25) ^ (s << 30);
    s ^= (s >> 17);
    s ^= (s << 13) ^ (s << 26);
    return s;
}

どうしてこれで元に戻るのかを詳しく見ます。

xorshift のアルゴリズムは

(s を入力)

1. t1 = s ^ (s << 13)
2. t2 = t1 ^ (t1 >> 17)
3. t3 = t2 ^ (t2 << 5)

(t3 を出力)

の3つの手順で構成されています。 まず、最後の手順3を巻き戻す方法を考えます。

	31~30	29~25	24~20	19~15	14~10	9~5	4~0
t2	?	?	?	?	?	?	?
t2 << 5	?	?	?	?	?	?	O
t3	G	F	E	D	C	B	A

O は0埋めされたビットを表しています。 今、t3 は生成された乱数値であるため既知で、t3 から t2 を求めることを考えます。t3 の0から4ビット目までを A、1から5ビット目までを B、というように置きます。

t3 は t2 と t2 << 5 を xor したもので、上記の表で上の2段を xor したら下の段になります。したがって、0~4ビット目に注目すると、? ^ O == A となります。 したがって、この ? は A であることがわかります。(∵ A ^ O == A)

これで該当する場所を埋めます。

	31~30	29~25	24~20	19~15	14~10	9~5	4~0
t2	?	?	?	?	?	?	A
t2 << 5	?	?	?	?	?	A	O
t3	G	F	E	D	C	B	A

次に、5~9ビット目に注目すると、? ^ A == B であるため、この ? は A ^ B であることがわかります。(∵ (B ^ A) ^ A == B)

	31~30	29~25	24~20	19~15	14~10	9~5	4~0
t2	?	?	?	?	?	B^A	A
t2 << 5	?	?	?	?	B^A	A	O
t3	G	F	E	D	C	B	A

同様に上のビットに対しても繰り返していくと、最終的に以下のようになります。

	31~30	29~25	24~20	19~15	14~10	9~5	4~0
t2	G^F^E^D^C^B^A	F^E^D^C^B^A	E^D^C^B^A	D^C^B^A	C^B^A	B^A	A
t2 << 5	F^E^D^C^B^A	E^D^C^B^A	D^C^B^A	C^B^A	B^A	A	O
t3	G	F	E	D	C	B	A

30~31ビット目に関しては5ビットのうちの溢れてしまう上位3ビットは無視して下位2ビットのみを表していると考えてください。

これでt2の全てのビットが分かりました。したがって、手順3 t3 = t2 ^ (t2 << 5) の逆は

t2 = t3 ^ (t3 << 5) ^ (t3 << 10) ^ (t3 << 15) ^ (t3 << 20) ^ (t3 << 25) ^ (t3 << 30)

となることがわかりました。

これで、手順2、手順1についても同様に逆手順を考えると、手順2 t2 = t1 ^ (t1 >> 17) の逆は

t1 = t2 ^ (t2 >> 17);

となり、手順1 t1 = s ^ (s << 13) の逆は

s = t1 ^ (t1 << 13) ^ (t1 << 26)

となります。これで、最初に示した xorshift を巻き戻すコードが得られました。

利用例

例えば、N問あるクイズをランダムで出題するとして、出題したクイズをメモリ上に記憶せずに、前の問題に戻れるようにしたいとか。

特に有用な利用法はないですが、巻き戻せるということを覚えておけば何かに役立つかもしれないですね。