仄暗いレートの底から

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

【ヌオーでもわかる乱数調整】RSにおけるID生成について【番外編】

ヌオーでもわかる(?)3gen乱数調整のコーナー、第0回目にして番外編です! いえーいぱちぱち。
今回はRSのID生成処理において、違うseedから同じIDの組み合わせが生成される条件について考えてみようと思います。

(約半月間、授業をまったく聞かずに考え続けた成果をメモ程度にでも残しておきたかっただけです…。)

■注意
・乱数調整のやり方については一切触れません。
・というか「乱数調整」の記事なのかすら怪しいです。3genの生成処理についての考察記事です。
・これを知っても、乱数調整をする上でなんのプラスにもならないと思います。

■始めに : RSにおけるIDの生成
SID,TIDの順に生成。

生成開始seedをr[n]とすると、
SID : r[n] >> 16
TID : r[n+1] >> 16
で生成。要するに16進数で表したときの上4桁。

データ上はPIDみたいな形で一緒になって格納されてるみたいです。

■ほんへ : 同じIDの組み合わせになるseed(上記r[n])の組についての考察

生成されるIDが同じとき、少なくとも生成に使われる2つのseedの値の差は0x0000FFFF以下である

上位16bitが一致するんですから当たり前ですね。
とりあえずこれを頼りに考えてみます。

あるseed R[n]に対し、seedの値がR[n] + dとなるseedをR[m]とおきます。
このとき、R[n+1]とR[m+1]の関係について考えてみましょう。

3genのLCGはX[n+1] = (A * X[n] + B) mod Mと書けるので (※A=0x41C64E6D,B=0x00006073,M=0x100000000。mod M はMで割った余りを示す)
R[n+1] = (A * R[n] + B) mod M
R[m+1] = (A * R[m] + B) mod M

R[m] = R[n] + dなので、これを代入します。

R[m+1] = {A * (R[n] + d) + B} mod M
= {(A * R[n] + B) + A * d} mod M
= R[n+1] + (A * d) mod M

R[n+1]とR[m+1]の差は(A * d) mod Mと表せることがわかりました。

TIDが一致するとき、R[n+1]とR[m+1]の差も、少なくとも0x0000FFFF以下になるはずです。

なので、
0 ≦ d ≦ 0xFFFF かつ 0 ≦ A*d mod M ≦ 0xFFFF
を満たすdを探してみたところ、d = 0, 0x67D3, 0xCFA6の3つが該当しました。
ただし、d = 0の場合、R[n] = R[m]となるので不適で、0xCFA6 = 2 * 0x67D3なので、d = 0x67D3とすれば良いでしょう。

では2つの生成開始seedの差が0x67D3ならいつでもTIDとSIDは一致するのでしょうか?

R[n]の下位16bitとdを足したとき、それが0x10000より大きくなると、桁上がりが生じてR[m]の上位16bitは(R[n]の上位16bit + 1)の値を取ることになってしまいます。
例)0x00003333 に 0x000067D3 を足すと 0x00009B06 ですが、0x0000FFFF に 0x000067D3を足すと0x000167D2となり、上位16bitが一致しません。
つまりR[n]の下位16bitが 0x10000 - 0x67D3 = 0x982Dより小さい、というのが条件の1つとなるようです。

また、R[n+1]とR[m+1]についても同じことを考えないといけません。
A * d mod M = 0x00007ED7なので、R[n+1]の下位16bitが 0x10000 - 0x7ED7 = 0x8129より小さくないといけません。

以上から、R[n] < R[m]である2つのseedが
1.R[m] - R[n] = 0x000067D3
2.R[n] mod 0x10000 ≦ 0x982C
3.R[n+1] mod 0x10000 ≦ 0x8129
を満たすとき、生成されるTID,SIDが一致すると言えます。

■あとがき
半月かけて考えた割りにまとめがお粗末ですね…すみません。。。
だからなんだって感じの内容ですが、欲しかった結論は「RSでは存在しないIDの組み合わせがある」ってことです。
調べてる途中で、「0x67D3の存在の時点で同じIDの組み合わせが存在してるから存在しない組み合わせもあるって証明できたんじゃ…」って思いましたが、気にせず続けました。
IDは乱数値をそのまま使っているので、個体値の組み合わせなんかにも応用が利くと思います。(あとがきを書きながら気づいた)

間違ってる箇所、わかりにくい箇所等あればご指摘ください。
2つの乱数とそれらを進めた乱数の関係については、oupoさんのブログを、穴が空くほど参考にさせていただきました。ありがとうございました。
スポンサーサイト

この記事に対するコメント


この記事に対するコメントの投稿

















Powered By FC2ブログ
Template By oresamachan
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。