|
2010-1-26[火] xorshift乱数のメモXorShift乱数は、こちらとかのように短い関数で紹介されるけれど、たいていシード固定で書かれていて、シードを外部から与えたい場合はどうしたら、と悩んでしまう. もちろん、ちょっとぐぐったらシード設定できるソース載せてるサイトあるし、 おおもとのpaper に all 0でなければよいようなことかいてあるようだけど、 どの程度適当でよいのか不安にもなる. で、今さらながら2chの擬似乱数2 をみたら76に解説&seed設定付ソースがあった. シードは極端な設定をすると不自然な部分列が出力されるからMTのを参考にしたとある. ありがたく、これ流用させていただくことに... と、よくよくみれば、ここの初期化とほぼ同じ(改良版)のよう. その他、検索したときのサイトメモ. mt-liteの実行速度に xorshiftを含む各種乱数の速度比較あり. 良い乱数・悪い乱数に XorShiftと他の乱数との速度比較とかSSE2使ったバージョンとかがある. 同サイトの こちらにもいろいろなコンパイラでの測定比較あり. xorshift.pdf 上記サイトで、"問題があると書かれている" とあったのでみた(翻訳ソフトでわからないなりに). 元のpaperより突っ込んだ性能テストをして、通過しないテストがいくつか(も)あるよう. （XorShiftは３つのシフト数の有効な値の組み合わせがいくつか(も)あるけれど、 組み合わせによって性能にばらつきがあるよう） あと改良版として256ビット版が載ってる. (周期のビット数だけでなく、計算でのシフト数も増やして精度をあげている)
XorShift乱数の速度擬似乱数2の 42 に 周期 32,64,96,128,160,192 ビット版のソースがあったので、 ちょっと速度比較してみた.
結果は以下. 環境は基本Phenom2 3GHz (玄箱HGは PowerPC 266MHz).
下３つは比較用. MT乱数(mt19937ar-cok.c)と 線形合同法を使った乱数とC標準ライブラリのrand()を使ったもの. コンパイラごとに癖はあるけれど、大筋は似た傾向.
paperの例では1.8GHzで4～6ナノ秒とあったので、
3GHzの環境(vcやg++)で 2～4ナノ秒は、そんなものかもしれない.
全体に周期32ビット版は他より遅くなっているのは、たぶん(アウトオブオーダーとかのレベルの)命令の並列化ができないためだろうか. 速度的には、 大筋ビット数が増えれば遅くなるけれど、32-192の範囲では 増える周期(質の改善)に比べ時間の増加はさほどでもないので、 どうせなら128でなく160や192あたりを使うのも手かもしれない. 256ビット版はプログラムが少々複雑になっているせいか 時間増加のよう. 128ビット版にくらべ2～3倍... MTと対して変わらない速度(場合によっては負ける)なので出番はないだろう.
でinline展開で速いのはいいけれど、
ビット数が大きいほど(ささやかとはいえ)コードサイズが膨れやすくなるので、
乱数の質が高くなくていいなら、ビット数少ないのを選ぶのもよいかもしれない. サイズきになるならinlineしない形に書いて160,192あたりを... もっとも、このソースの64,96,160(,192)は使ったパラメータがほんとにこれがいいのかわかっていないので 結局 128 を選んでおくのがベターな気はする.
あと、XorShiftの件とはずれるが、vcやg++でのcライブラリの rand()の速度が遅いのは、 マルチスレッド対応のオーバーヘッドのためだろうか. インライン展開された線形合同法の乱数の10倍前後なのは ペナルティが大きいとも、10数ナノ程度ならば大抵たいしたことないとも、どちらとも. 結局使用量/使用箇所しだい、だけれど、どっちにしろ精度のことを思えば、 とっとと XorShiftなりMTなり用意して用途別にインスタンスを管理したほうが、 楽になれると思う. (参考サイトにある SIMD版のSFMTとかが使える環境なら, そっちのほうがいいだろうな)
追記乱数の精度の評価についてはさっぱりなんですが (自分が使った処理において出目に不都合があるかどうかくらいなら、ともかく)、 同根のtest2をしたときの結果はあまりよいという感じではなかった.(この場合のテストとして適切かどうかもわかってないけど) まあ、たいていの場合の乱数の利用頻度や精度を思うと 普通は MT を選んどくのが無難だと思う.
この程度の速度差(時間差)やプログラムサイズ差が
ネックになるような利用頻度(仕様)やターゲット環境なんて
ゲームでもまずないだろうし. |