2013-03-31

はてなブログに移行します。

突然ですが、心機一転、はてなブログに移行します。
アカウントも別のものになります。まあ中の人は同じですが。

Xion's Programming Notes

これまでの記事は、とりあえずこのまま残します。
新ブログに記事をインポートするかは未定です。

これまでありがとうございました。
そして、これからもよろしくお願い致します。

2013-03-26

続・擬似乱数の計算時間

c++ programming

前回の結果

前回の実験結果はこんな感じ。縦軸は1秒あたりの乱数生成回数です。
条件等は、前回の記事を参照してください。

考察っぽいこと

以下のことは、私の妄想かもしれません。嘘を言っている可能性も多分にあります。
ご注意ください。 # 詳しい人いたら教えてください(^q^)

最も速いsfmtは、1秒間に10億回近くも乱数を生成できます。
使用したCPUが3.5GHzなので、1秒で35億クロック分計算ができるということになります。
したがって、sfmtは3.5〜4clock程で計算できるということになります。
xorやmseqでも、5〜6clock、boostのメルセンヌ・ツイスタでも、8clock以下程度です。

今回は、forループを使って連続で乱数生成をしているので、キャッシュ効率とか最善の状況だと思いますので、実際にはもうちょっと遅くなるのでしょうが、これはなかなか驚異的な数値だと思います。

まとめ

SSEが使えるなら、sfmtを使う
数クロックの差が大きい場合、xorshiftやM系列乱数を使う
その他の場合は、周期のことを考えて、メルセンヌ・ツイスターを使っておけば、間違いない

2013-03-23

疑似乱数の計算時間

c++ programming

お久しぶりです．
実に1年と2ヶ月2週間ぶりの更新です．

リアルが忙しいという事もあったと言えばあったのですが，趣味のプログラミングに労力を割く気力がなかったといいますか，つまり五月病みたいなものですね…．

まあそんなネガティブな話はもう忘れてしまって，これからはちょいちょい更新していきたいと思います．

疑似乱数

さて，今回は疑似乱数のお話です．
代表的な疑似乱数生成方法としては，以下のようなものがあります．

線形合同法
メルセンヌ・ツイスタ
Xorshift
M系列乱数
Lagged Fibonacci

標準のCでは，線形合同法のrand()が用意されています．
でもこれはあんまり賢くない方法なので，大事なシミュレーションとかでは使わない方がいいみたいです．
とりあえずメルセンヌ・ツイスタを使っておけば間違いないようです．

疑似乱数生成器の速度比較

今回は，疑似乱数生成器の計算速度の比較をします．

実行環境は，こんな感じ．

CPU	Intel Core i7 2700K@3.5GHz
OS	Ubuntu 12.04 32bit
gcc	4.6.3

コンパイラオプションは，最適化とSSE2を使用する形で．
と言っても，SSE2を使うのは後述のsfmtだけです．

-O3 -msse2 -DHAVE_SSE2=1 -DSFMT_MEXP=19937

疑似乱数一覧

省略名	詳細	周期
std	C標準のrand関数	2^31-1
mt	Mersenne Twister	2^19937-1
sfmt	SIMD-oriented Fast Mersenne Twister	2^19937-1
boost	boostのMersenne Twister	2^19937-1
xor	Xorshift	2^128-1
mseq	M系列乱数	2^521-1