randomを比べてみる。
SFMTを含んでいるため、修正BSDライセンスです。
SFMTについては、260行目あたりを参照。
本当は↓からforkにしたかったけど、
http://wonderfl.kayac.com/code/feb94dc51f5dfdeb1aeef3d16b35c70661e6b963
ライセンス的にダメだったので方向転換。
◆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は今回くらいのテスト内容だと、
特にメリットが見いだせなかった。
それとも実装の問題なのだろうか、、、。
＝＝＝＝＝
最近、アルゴリズムの本を読んで気になっていたので、
random()を調べてみた。
コンピュータでは通常、完全にランダムな
値を作ることはできない。
実用上問題無いくらいにバラバラの値を
上手い計算方法で取り出して使っている。
これを疑似乱数（pseudo-random number）
という。
疑似乱数の計算方法はいくつも提案されているが、
その中でも特に使われているのは、
線形合同法のようだ。
ただし、線形合同法は設定値の組み合わせによって、
振る舞いが変わる。言語によってバラバラなので、
結果、良い線形合同法と悪い線形合同法が
できてしまっている。注意が必要だ。
また、疑似乱数では再現可能なしくみ、
乱数の種（randomSeed）を与えることができる。
疑似乱数はあくまでも計算結果なた
/*
SFMTを含んでいるため、修正BSDライセンスです。
SFMTについては、260行目あたりを参照。
本当は↓からforkにしたかったけど、
http://wonderfl.kayac.com/code/feb94dc51f5dfdeb1aeef3d16b35c70661e6b963
ライセンス的にダメだったので方向転換。
◆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は今回くらいのテスト内容だと、
特にメリットが見いだせなかった。
それとも実装の問題なのだろうか、、、。
＝＝＝＝＝
最近、アルゴリズムの本を読んで気になっていたので、
random()を調べてみた。
コンピュータでは通常、完全にランダムな
値を作ることはできない。
実用上問題無いくらいにバラバラの値を
上手い計算方法で取り出して使っている。
これを疑似乱数（pseudo-random number）
という。
疑似乱数の計算方法はいくつも提案されているが、
その中でも特に使われているのは、
線形合同法のようだ。
ただし、線形合同法は設定値の組み合わせによって、
振る舞いが変わる。言語によってバラバラなので、
結果、良い線形合同法と悪い線形合同法が
できてしまっている。注意が必要だ。
また、疑似乱数では再現可能なしくみ、
乱数の種（randomSeed）を与えることができる。
疑似乱数はあくまでも計算結果なため、
初期値が同じなら、同じ結果が得られるためだ。
例えば疑似乱数を使っての動作チェック時に、
「同じ組み合わせの疑似乱数で再テストをしたい」
ということはよくある。
この場合、randomSeedをメモしておいて、
再テスト時には、このrandomSeedを再び与えれば良い。
ASでは疑似乱数の生成方法が公開されておらず、
Math.random()にrandomSeedを与えることもできない。
注：
元のbitmapDataの色は0x000000であり、
計算結果により座標が得られると、そこの点が若干明るくなる。
次に同じ座標が得られた場合は、さらに明るくなる。
0x00から始まり、0xFFまで青が段々強くなっていく。
最終段階は目立ちやすいように赤0xFF0000にした。
SFMTについては、260行目あたりを参照。
参考
http://www.eqliquid.com/blog/2009/02/sfmt-actionscript-30.html
http://www001.upp.so-net.ne.jp/isaku/rand.html
http://hp.vector.co.jp/authors/VA004808/random1.html
http://d.hatena.ne.jp/keyword/%C0%FE%B7%C1%B9%E7%C6%B1%CB%A1
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
public class Main extends Sprite {
public var mySfmt:Sfmt = new Sfmt(1);
public var my00DrawBitmap:DrawBitmap = new DrawBitmap(this,0,0);
public var my01DrawBitmap:DrawBitmap = new DrawBitmap(this,0,1);
public var my02DrawBitmap:DrawBitmap = new DrawBitmap(this,0,2);
public function Main():void {
var time:Number = new Date().getTime();
benchMarkj(_a0);
benchMarkj(_a1);
benchMarkj(_a2);
benchMarkj(_a99);
my00DrawBitmap.txt(""+benchMarkj(_a0)/1000+"sec：Math.random");
benchDraw(_b0);
my01DrawBitmap.txt(""+benchMarkj(_a1)/1000+"sec：線形合同法");
benchDraw(_b1);
my02DrawBitmap.txt(""+benchMarkj(_a2)/1000+"sec：SFMT");
benchDraw(_b2);
}
//100万回関数を実行して、かかった時間を計っている。
private function benchMarkj(_fn:Function):int {
var time:Number = (new Date()).getTime();
_fn(1000000);
return (new Date()).getTime() - time;
}
//40万回関数を実行して、ビットマップの色を変える。
private function benchDraw(_fn:Function):void {
_fn(400000);
}
private function _a0(n:uint):void {
for (var i:int = 0; i < n; i++) {
Math.random();
}
}
private function _a1(n:uint):void {
for (var i:int = 0; i < n; i++) {
Mas.random();
}
}
private function _a2(n:uint):void {
for (var i:int = 0; i < n; i++) {
mySfmt.random();
}
}
private function _b0(n:uint):void {
for (var i:int = 0; i < n; i++) {
my00DrawBitmap.pxy(Math.random(),Math.random());
}
}
private function _b1(n:uint):void {
for (var i:int = 0; i < n; i++) {
my01DrawBitmap.pxy(Mas.random(),Mas.random());
}
}
private function _b2(n:uint):void {
for (var i:int = 0; i < n; i++) {
my02DrawBitmap.pxy(mySfmt.random(),mySfmt.random());
}
}
private function _a99(n:uint):void {
for (var i:int = 0; i < n; i++) {
zero();
}
}
private function zero():Number {
return 0;
}
}
}
import flash.display.Sprite;
import flash.display.BitmapData;
import flash.display.Bitmap;
import flash.text.TextField;
class DrawBitmap extends Sprite{
private var w:Number = 465;
private var h:Number = 142;
private var bmp_data:BitmapData = new BitmapData(w,h, false , 0x000000);
private var bmp:Bitmap = new Bitmap(bmp_data);
private var text_field:TextField = new TextField();
function DrawBitmap(ta:Object,_x:Number,_y:Number){
bmp.x = _x*w;
bmp.y = 155*_y+12;
ta.addChild(bmp);
text_field.x = _x*w;
text_field.y = 155*_y-2;
text_field.height=50;
text_field.width = w;
ta.addChild(text_field);
}
public function txt(_str:String):void{
text_field.text=_str;
}
public function pxy(numX:Number,numY:Number):void{
var _x:int = int(numX*w);
var _y:int = int(numY*h);
if(bmp_data.getPixel(_x,_y) < 0x11){
bmp_data.setPixel(_x,_y ,0x11);
}else if(bmp_data.getPixel(_x,_y) < 0x22){
bmp_data.setPixel(_x,_y ,0x22);
}else if(bmp_data.getPixel(_x,_y) < 0x33){
bmp_data.setPixel(_x,_y ,0x33);
}else if(bmp_data.getPixel(_x,_y) < 0x44){
bmp_data.setPixel(_x,_y ,0x44);
}else if(bmp_data.getPixel(_x,_y) < 0x55){
bmp_data.setPixel(_x,_y ,0x55);
}else if(bmp_data.getPixel(_x,_y) < 0x66){
bmp_data.setPixel(_x,_y ,0x66);
}else if(bmp_data.getPixel(_x,_y) < 0x77){
bmp_data.setPixel(_x,_y ,0x77);
}else if(bmp_data.getPixel(_x,_y) < 0x88){
bmp_data.setPixel(_x,_y ,0x88);
}else if(bmp_data.getPixel(_x,_y) < 0x99){
bmp_data.setPixel(_x,_y ,0x99);
}else if(bmp_data.getPixel(_x,_y) < 0xAA){
bmp_data.setPixel(_x,_y ,0xAA);
}else if(bmp_data.getPixel(_x,_y) < 0xBB){
bmp_data.setPixel(_x,_y ,0xBB);
}else if(bmp_data.getPixel(_x,_y) < 0xCC){
bmp_data.setPixel(_x,_y ,0xCC);
}else if(bmp_data.getPixel(_x,_y) < 0xDD){
bmp_data.setPixel(_x,_y ,0xDD);
}else if(bmp_data.getPixel(_x,_y) < 0xEE){
bmp_data.setPixel(_x,_y ,0xEE);
}else if(bmp_data.getPixel(_x,_y) < 0xFF){
bmp_data.setPixel(_x,_y ,0xFF);
}else{
bmp_data.setPixel(_x,_y ,0xFF0000);
}
}
}
/*
線形合同法
randomSeedを与えた場合は、100回実行して偏りを抑える。
参考
http://hp.vector.co.jp/authors/VA004808/random1.html
http://d.hatena.ne.jp/keyword/%C0%FE%B7%C1%B9%E7%C6%B1%CB%A1
*/
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;
}
}
/*
SFMT 簡易版クラス
author:kimura@sionnet.jp
http://www.eqliquid.com/blog/2009/02/sfmt-actionscript-30.html
から抜き出した。
umhrにより使いやすいようにごく一部修正した。
umhrによる修正や使い方によって、
重大な問題が発生している可能性があるので、
「SFMT 簡易版クラス」やSFMT自体の評価は別途行うこと。
以下、元のReadme_jp.txtよりコピペ
====================
SFMT 簡易版クラス
author:kimura@sionnet.jp
パッケージ:
jp.sionnet.utils.Sfmt
====================
概要:
要約すれば、高度な擬似乱数を発生するメルセンヌ・ツイスタの高速版がSFMTです。
このSFMTの各言語版を公開されているisakuさんの簡易版ライブラリをActionScript3.0に移植したものです。
内容はちっとも理解できてないので、間違いがあったらご指摘いただけると幸いです。
SFMT:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index-jp.html
乱数ライブラリ:
http://www001.upp.so-net.ne.jp/isaku/rand2.html
ライセンス:
SFMTのライセンスに依ります。2009年2月現在、修正BSDライセンスです。
====================
以上、元のReadme_jp.txtよりコピペ
*/
class Sfmt
{
private var index:int;
private var x:Vector.<int> = new Vector.<int>(624);//状態テーブル
/**
* コンストラクタ<br />
* 初期化する
* @param s 整数のシード
*/
public function Sfmt(s:int)
{
initMt(s);
}
private function genRandAll():void
{
var a:int = 0;
var b:int = 488;
var c:int = 616;
var d:int = 620;
var y:int;
var p:Vector.<int> = x;//Javaの振る舞い、処理の内容からシャローコピーと判断
do
{
y = p[a + 3] ^ (p[a + 3] << 8) ^ (p[a + 2] >>> 24) ^ ((p[b + 3] >>> 11) & 0xbffffff6);
p[a + 3] = y ^ (p[c + 3] >>> 8) ^ (p[d + 3] << 18);
y = p[a + 2] ^ (p[a + 2] << 8) ^ (p[a + 1] >>> 24) ^ ((p[b + 2] >>> 11) & 0xbffaffff);
p[a + 2] = y ^ ((p[c + 2] >>> 8) | (p[c + 3] << 24)) ^ (p[d + 2] << 18);
y = p[a + 1] ^ (p[a + 1] << 8) ^ (p[a] >>> 24) ^ ((p[b + 1] >>> 11) & 0xddfecb7f);
p[a + 1] = y ^ ((p[c + 1] >>> 8) | (p[c + 2] << 24)) ^ (p[d + 1] << 18);
y = p[a] ^ (p[a] << 8) ^ ((p[b] >>> 11) & 0xdfffffef);
p[a] = y ^ ((p[c] >>> 8) | (p[c + 1] << 24)) ^ (p[d] << 18);
c = d;
d = a;
a += 4;
b += 4;
if (b == 624) b = 0;
}
while (a != 624);
}
private function periodCertification():void
{
var work:int;
var inner:int = 0;
var i:int;
var j:int;
var parity:Vector.<int> = new Vector.<int>(4);
parity.push(0x00000001);
parity.push(0x00000000);
parity.push(0x00000000);
parity.push(0x13c9e684);
index = 624;
for (i = 0; i < 4; i++)
{
inner ^= x[i] & parity[i];
}
for (i = 16; i > 0; i >>>= 1)
{
inner ^= inner >>> i;
}
inner &= 1;
if (inner == 1) return;
for (i = 0; i < 4; i++)
{
for (j = 0, work = 1; j < 32; j++, work <<= 1 )
{
if ((work & parity[i]) != 0)
{
x[i] ^= work;
return;
}
}
}
}
/**
* 初期化
* @param s 整数のシード
*/
private function initMt(s:int):void
{
x[0] = s;
for (var p:int; p < 624; p++)
{
s = 1812433253 * (s ^ (s >>> 30)) + p;
x[p] = s;
}
periodCertification();
}
/**
* 32ビット符号あり整数乱数を返す
* @return 32ビット符号あり整数乱数
*/
public function nextMt():int
{
if (index == 624)
{
genRandAll();
index = 0;
}
return x[index++];
}
/**
* 0 以上 n 未満の整数乱数を返す
* @param n 乱数の上限値にする整数
* @return 0 以上 n 未満の整数乱数
*/
public function nextInt(n:int):int
{
var z:Number = nextMt();
if (z < 0) z += 4294967296.0;
return int(n * (1.0 / 4294967296.0) * z);
}
/**
* umhrによる追加
* 0 以上 1 未満の乱数(32ビット精度)を返す
* @return 0 以上 1 未満の乱数(32ビット精度)
*/
public function random():Number
{
var z:Number = nextMt();
if (z < 0){ z += 4294967296};
return z / 4294967296;
}
/**
* 0 以上 1 未満の乱数(53ビット精度)を返す
* @return 0 以上 1 未満の乱数(53ビット精度)
*/
public function nextUnif():Number
{
var z:Number = nextMt() >>> 11;
var y:Number = nextMt();
if (y < 0) y += 4294967296.0;
return (y * 2097152.0 + z) * (1.0 / 9007199254740992.0);
}
}