2008年10月31日

ランダム

1ヶ月半ぐらい前、仕事がヒマだったので、ずっと擬似乱数について調べていた。

発端はもちろんあの(といってもだいぶ古い)Xbox360のカルドセプトだ。偶数奇数が順番に出るという、おそらくイケてないrand関数をそのまま使ったのであろうアレだ。俺もゲームを作る上で乱数を利用することはあるので、調べておいて損は無いどうせヒマだしー、ということで調べていた。

まず、カルドセプトで使われたどうしようもないrandをどうしても使わなければならないならば、下位ビットの剰余
a = rand() % 10;
で求めるのではなく、
a = ( int )( ( rand() / ( ( double )RAND_MAX + 1.0f ) ) * 10 );
ぐらいのことはしたほうが良いらしい。この場合、0〜9までの値を返す。赤字部分を適宜変更する。なお、コンパイラによってrandの中身は微妙に違うらしいが、どれもイケてないことに変わりはない。

次に、最近の流行りは『メルセンヌ・ツイスタ』。某後輩がメインプログラマをやったプロジェクトでは、これが使われていた。現時点では最強らしい。これの改造版の『SFMT』というものもある。倍精度浮動小数点擬似乱数が必要ならば『dSFMT』という姉妹版もある。現在最強という点で非常に惹かれるものがあるが、また別のものを見つけた。

『XorShift』。精度は『メルセンヌ・ツイスタ』に及ばないもの、計算にxorとビットシフトしか使わないということで、非常に高速との触れ込み。今回、自分のためにBorland C++ Builderで作ったソフト『ランダム値作成』の_lrand関数を、この『XorShift』に変えてみた。

改造するに当たって必要なのは、ぶっちゃけコピペで済むソース
unsigned long
xor128( void )
{
    unsigned long x = 123456789;
    unsigned long y = 362436069;
    unsigned long z = 521288629;
    unsigned long w = 88675123;
    unsigned long t;
    t = ( x ^ ( x << 11 ) );
    x = y;
    y = z;
    z = w;
    return( w= ( w ^ ( w >> 19 ) ) ^ ( t ^ ( t >> 8 ) ) );
}
なのだが、どうも初期化処理が書かれているページが見当たらない。初期化がないと常に同じ値になるのはソースを見なくても想像つく。探した。全力で探した。スタッフが全力で探しました。そして、初期化処理、見つかりました。(紳助)(徳光すすり泣き)

Klabo-Wiki
えーと、東北大河田研、かな。よくワカランけど。んで、内容はごくシンプル。
void
init_xorshift(
    unsigned int    s )
{
    for( int i = 1; i <= 4; i++ )
    {
        seed128[ i - 1 ] = s = 1812433253U * ( s ^ ( s >> 30 ) ) + i;
    }
}
と。変数seed128ってのは、unsigned int型の配列。上記の、x, y, z, wに相当する。x, y, z, w の初期値を固定で書くのはマズいので、seed128[ 4 ]の値を初期値として用いる。もちろん、s には、time( NULL ); を入れておけば良い。ということらしい。

ところで、上記東北大河田研では、s に入れる値を
time( NULL ) * getpid()
としている。うーん、これはちょっと冗長じゃないかなぁ・・・と思いつつも、明確に否定できる知識を持っている訳じゃない。気が向いたら調べてみよう。

さて、ゴチャゴチャしすぎたので整理。( u32 は、unsigned int 型 )
// 配列用意。
u32 gSeed128[ 4 ];

// 初期化
u32 s = time( NULL );
for( int i = 1; i <= 4; i++ )
{
    gSeed128[ i - 1 ] = s = 1812433253U *( s ^ ( s >> 30 ) ) + i;
}

// 実行部
u32 t = ( gSeed128[ 0 ] ^ ( gSeed128[ 0 ] << 11 ) );
gSeed128[ 0 ] = gSeed128[ 1 ];
gSeed128[ 1 ] = gSeed128[ 2 ];
gSeed128[ 2 ] = gSeed128[ 3 ];
return( gSeed128[ 3 ] = ( gSeed128[ 3 ] ^ ( gSeed128[ 3 ] >> 19 ) ) ^ ( t ^ ( t >> 8 ) ) );

終わり。

ちなみに、今回引用するにあたり全て俺式に書き直したが、上記東北大河田研のソースはムダに横長で美しくない。まぁ、このようなライブラリ部分は(完成しているならば)汚くても構わないっちゃあ構わない。

だが、あんまり横詰めにすると、1週間ぐらい経って見直したとき、に最初から解析しないと理解できないソースになったりすることがある。ゆえに控えたほうが良いと思う。

とはいえ、こういうの(プログラムの記述)は宗教戦争みたいなモンなんで、各々の信じる宗派に従って書けば良いとも思う。最悪なコーディングってのは、『知識が乏しいこと』『一貫性が無いこと』の2点であるから、ごく一部のソースを見て全てを否定するのは良くない。

しかしながら、横長はどうだろうか。それを信ずる宗派はかなり少ないのではないか、という思いはある(横長が有効な場合ももちろんあるが、今回はそれに該当しないと思う)。まぁ、他所様のことなんでどっちでも良いんですがね。


ラベル:XorShift 擬似乱数
posted by 小川 at 00:47| Comment(0) | TrackBack(0) | プログラム/マ | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。