seed 上位1bitの話 - oupoの日記

2010-04-18 - 東方錆恋録〜Slipping Rusted Magnemite〜

を読んで。
二つのseedの上位1bit以外が一致している場合 row(PID) xor high(PID) って常に一致するんだなー。今までPIDのbit15 xor bit31が一致すればいいから50%だと思いこんでた。

x=0〜0x7fffffff
1つ目の乱数でPID下位16bitが決定、2つ目の乱数でPID上位16bitが決定される。

seed = x のとき、rowの上位1bitは0。
seed = (x | 0x80000000) のとき、rowの上位1bitは1。

next(x)の上位1bitが1のとき、next(x | 0x80000000)の上位1bitは常に0、
next(x)の上位1bitが0のとき、next(x | 0x80000000)の上位1bitは常に1である。

なぜならば
next(x | 0x80000000) = next(x) + uint32(0x80000000 * 0x41c64e6d)
だから。
この式を変形すると next(x | 0x80000000) = next(x) xor 0x80000000 となる。
（0x80000000足すのは0x80000000とxorをとるのと同じ）

よって xと(x | 0x80000000)で(rowの上位1bit xor highの上位1bit)は常に一致する。

追記 (2010-04-29T18:48:14+09:00)

ってこれ後から考えてみると当たり前だなー。
もしこれが成り立たなかったら、上位1bitが違うだけの2つのseedそれぞれの次のseedが同じになるってことが起こってしまう。