random()、線形合同法 – 水玉製作所

アルゴリズムの本を読んで気になっていたので、random()を調べてみた。

コンピュータでは通常、完全にランダムな値を作ることはできない。実用上問題無いくらいにバラバラの値を上手い計算方法で取り出して使っている。これを疑似乱数（pseudo-random number）という。

疑似乱数の計算方法はいくつも提案されているが、その中でも特に使われているのは、線形合同法のようだ。randomにも良し悪しがある、というのは聞いてはいたがActionScriptのMath.random()が悪いほうなのかどうかが気になっていた。

今回はさらにSFMTも並べて計算速度、偏り具合を見てみた。
　
　

●Math.random()と線形合同法とSFMTの三つをを比較してみた。

　
それぞれを実行時間(sec)を計るために100万回実行し、取り出した値の偏りを視覚的に確認するために、40万の点の座標をx,yで作り画像に埋めていった。計算結果に偏りがある場合はムラやパターン、筋が現れるはず。

◆結果

MacOSX10.5.7/2.4GHzCore2Duo、FlashPlayer10,0,22,87では
0.587sec：Math.random
0.037sec：線形合同法
0.515sec：SFMT
確認画像では、三つともほぼ同じ程度のムラとなった。

◆結論

理屈で言えば、完全に均一な面ができればいいのだろうが、そうはなっていない。
しかしこれくらいであれば実用上問題になることはまず無いだろう。

・Math.randomについて
速度が遅くて困るとかは無いと思う。ほとんどの場合これで足りる、ということを確認できた。

・線形合同法について
randomSeedを与えられる、計算が速いという理由で、ひと手間かけてもいい場合には、この線形合同法が良い。

・SFMTについて
SFMTは今回くらいのテスト内容だと、特にメリットが見いだせなかった。それとも実装の問題なのだろうか。
　
　

●さらに詳しい話。

◆線形合同法（LCG:Linear congruential generator）

線形合同法の一般式は以下。

	num = (num*A+C)%M;

1	num = (num*A+C)%M;

初期値numに設定値A、C、Mをかけたり足したりして、新たなnum値を作り出す。次回乱数が必要なときは、この「新たなnum値」を元に次の乱数を作る。

今回は以下のようなコード（extends SpriteはFlashCS4のコンパイラバグ対策のため）。

class Mas extends Sprite{
	private static var num:Number = 1;
	public static function randomSeed(s:Number):void{
		num = s;
		for (var i:int = 0; i < 100; i++) {
			random();
		}
	}
	public static function random():Number{
		num = (num*1664525+1013904223)%0x100000000;
		return num/0x100000000;
	}
}

class Mas extends Sprite{

private static var num:Number = 1;

public static function randomSeed(s:Number):void{

num = s;

for (var i:int = 0; i < 100; i++) {

random();

}

public static function random():Number{

num = (num*1664525+1013904223)%0x100000000;

return num/0x100000000;

}

randomSeedで初期値を設定できる（get/setで作ったり、randomの呼び出し回数をカウントしたほうが使いやすいとかあるかも）。randomSeedを与えた場合には100回実行して偏りを抑える。

A= 1664525,C= 1013904223,M=0x100000000を設定値としている。計算の結果を32Bitの幅に値を収めるために、0x100000000（0xFFFFFFFFの長さ）であまりを出す。返り値として0以上1未満に収めるために0x100000000で割っている。

線形合同法は設定値の組み合わせによって振る舞いが変わる。言語によってバラバラなので、結果、良い線形合同法と悪い線形合同法ができてしまっており、また、randomSeedに対する擬似乱数が言語依存になってしまいがちだ。「線形合同法は駄目」という文章はネット上にたくさんあるが、文脈、どの線形合同法について述べているかを注意したほうが良さそうだ。

今回採用した値の組み合わせ（1664525、1013904223、0x100000000）は、Knuth先生が線形合同法の中では最上とお墨付きを与えたものらしい。どれくらいそれが確かなのかはわからないけど、、（笑）。

numをNumber型にしているが、uintにすると定義上32bit内に収まるので%0x100000000の必要が無くなる。ただし、テストした中ではuintにすると速度が遅かったのでNumber型にしてある。

◆randomSeed

多くの疑似乱数では再現可能なしくみ、randomSeed（乱数の種）を初期値として与えることができる。疑似乱数はあくまでも計算結果なため、初期値が同じなら同じ結果が得られるためだ。

例えば疑似乱数を使っての動作チェック時に、「同じ組み合わせの疑似乱数で再テストをしたい」ということはよくある。この場合、randomSeedをメモしておいて、再テスト時には、このrandomSeedを再び与えれば良い。ゲームのリプレイではrandomSeedを保っておけば、敵の出現率、モブの動きなどrandomに頼った部分も再現できる。

ナムコの「ドルアーガの塔」というゲームでは、階数をrandomSeedとした擬似乱数で迷路を作ったという。よって、異なるマシンへの移植の際には異なった迷路が生成されたらしい。
http://druaga.to/qanda_tod.html

◆AS3のMath.random()

ActionScriptでrandomの計算方法が非公開、randomSeed設定不能なのは恐らく、将来も含めていろいろなCPUで動作させること前提にしているので、CPU依存の仕様は避けているためだろう。ちなみに、AS3でMath.random()*0x100000000とやると結果は偶数の整数になる。疑似乱数の生成方法に由来しているはずだ。

◆SFMT（SIMD-oriented Fast Mersenne Twister）

メルセンヌ・ツイスタというかっこいい名前の擬似乱数用の計算式があって、それの高速版がSFMT。
SFMTの性質、要点を解説できるほど知らないので、興味がある人は解説サイトを見てほしい。

今回は「SFMT 簡易版クラス」から抜き出した。
http://www.eqliquid.com/blog/2009/02/sfmt-actionscript-30.html
wonderflで使いやすいように一部修正した。
この修正や使い方によって、重大な問題が発生している可能性があるので、「SFMT 簡易版クラス」やSFMT自体の評価は別途行うこと。
また、このコードは修正BSDライセンスなので、注意。