疑似乱数２

**デフォルトの名無しさん** · 2007/10/17(水) 22:34:59

擬似乱数発生器について語ろうか。その２

前スレ
擬似乱数
http://pc11.2ch.net/test/read.cgi/tech/1146071975/

関連スレ
【危険】とんでもプログラム告発スレッド【悪質】
http://pc11.2ch.net/test/read.cgi/tech/1191860116/

SIMD-oriented Fast Mersenne Twister (SFMT):
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html

**デフォルトの名無しさん** · 2007/10/17(水) 22:53:56

で、いつになったらSFMTはboostに組み込まれるの？

**デフォルトの名無しさん** · 2007/10/17(水) 23:16:58

俺用メモ

18* 名前：デフォルトの名無しさん [] 投稿日：2006/04/28(金) 23:53:29
軽さで言えばXorShiftとか。

unsigned long xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

**デフォルトの名無しさん** · 2007/10/17(水) 23:35:36

>>3
せっかくだからURLも貼っとこう
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub218.html

**デフォルトの名無しさん** · 2007/10/17(水) 23:38:04

この手の乱数マジックナンバーでよくでてくる
123456789
なにふざけてるのかと思ってたら、
0.1234567891011121314… って超越数なんだな。
つまり123456789は、その超越数を10億倍して9桁の精度で切り落とした、
そこそこ質のよい数なのであった。
目からウロコ

**ヽ・´∀｀・,,）っ━━━━━━┓** · 2007/10/18(木) 00:42:09

マジックナンバーに0xDEADBEEFってよく見る

**デフォルトの名無しさん** · 2007/10/18(木) 01:51:23

SFMTはCPUの機能に最適化させてるメルセンヌツイスタですよね？
boostはテンプレートライブラリだからそれはいつまでたっても組み込まれないと自分は思います…。

**デフォルトの名無しさん** · 2007/10/18(木) 08:32:57

>>7意味不明

7 · 2007/10/18(木) 10:16:21

C++のテンプレートライブラリとして実装するものなのかなと思っただけです。

**デフォルトの名無しさん** · 2007/10/18(木) 12:38:11

独自の乱数発生器を組み込めるのがboost::randomのよいところ。
手直しは必要だが。

っていうか、boostがテンプレートライブラリだなんて誰が言ってるの？
STLの事じゃなくて？

**7=9** · 2007/10/18(木) 14:19:16

実際違いました…すみません。
boostの一部がSTLに移植されるとか書いてあったの見てたから勘違いかな…。
regexとかはテンプレートライブラリではなかったです。

あと、SFMTの情報斜め読みしてたから勘違いしてしまいました。申し訳ありません。

**デフォルトの名無しさん** · 2007/10/18(木) 19:08:52

RandomはTR1に入った、つまり標準ライブラリ入り内定ではある。

Regexは、テンプレートライブラリと呼ぶかどうかはともかく、
basic_regexなどテンプレートはよく使っている。

**ヽ・´∀｀・,,）っ━━━━━━┓** · 2007/10/19(金) 00:54:05

regexがプリコンパイル方式なのは型が最初から決まってるからじゃん。

**デフォルトの名無しさん** · 2007/10/19(金) 09:58:49

Xorshift RNGs

unsigned long xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

ttp://lucille.atso-net.jp/wiki/index.php?%CD%F0%BF%F4

**デフォルトの名無しさん** · 2007/10/19(金) 12:51:57

Boost はほとんどテンプレートだけど、
たまにテンプレートじゃないのがあるからな。

**デフォルトの名無しさん** · 2007/10/23(火) 01:38:55

http://www.nicovideo.jp/watch/sm1331242
歌詞を乱数で生成した歌

**デフォルトの名無しさん** · 2007/10/23(火) 04:40:30

(ax+b) mod M でいいよ…

**デフォルトの名無しさん** · 2007/10/23(火) 05:09:13

MT使え。
いじょ。
終了。

**デフォルトの名無しさん** · 2007/10/23(火) 08:01:20

再開

**デフォルトの名無しさん** · 2007/10/25(木) 23:12:25

初心者ですみません。

メルセンヌ・ツイスタって、COBOLに移植されてないでしょうか？
MTのページは見たのですがCOBOLはなかったorz

**デフォルトの名無しさん** · 2007/10/25(木) 23:15:18

COBOLで頑張ってもいいとはおもうけど（どっかに実装があるかもしれないけど）、
処理系の、Cの関数を呼び出す機能の利用を検討するのもありと思う

**デフォルトの名無しさん** · 2007/10/25(木) 23:27:05

>>21
ああ、おっしゃる通りですね。Cならすでにソースあるんだし。
その方向で検討します。ありがとうございました。

**デフォルトの名無しさん** · 2007/10/27(土) 11:24:36

COBOLで乱数が必要なのか？

**デフォルトの名無しさん** · 2007/10/27(土) 12:14:41

使えないとちょっとCOBOL

**デフォルトの名無しさん** · 2007/10/27(土) 19:27:33

コボルと困るを掛けた駄洒落か。なるほど。次の宴会で使おう。

**デフォルトの名無しさん** · 2007/10/28(日) 09:43:23

昔COBOLでなんちゃって正規分布乱数を作ったな

時計の1000分の一秒の値を種にして、中心極限定理を使ったはずだ
COBOLのシステムで何をするかしらんが、この程度で十分じゃねぇの？

**デフォルトの名無しさん** · 2007/10/28(日) 19:36:32

>>25
きっと誰かのビールがCOBOLる

**デフォルトの名無しさん** · 2007/10/28(日) 19:49:41

それは、すCOBOL、きついな。

**デフォルトの名無しさん** · 2007/10/29(月) 00:13:57

XorShiftのk=128では無いバージョン(32,64,96,160,192)について
誰か擬似コードor参考になるURL希望。

ググったが出て来なかった（多分やり方が悪いorz）

**デフォルトの名無しさん** · 2007/11/01(木) 01:20:36

>>29
ttp://www.jstatsoft.org/v08/i14/
ttp://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf

**デフォルトの名無しさん** · 2007/11/02(金) 15:50:53

ド素人なので突っ込みどころがあったら御教授くださいorz
rand()で生成した乱数をバイナリ形式で出力して
NIST SP800-22やdiehardテストに突っ込みたいんですけど・・・

↓のままだとdiehardどころかSP800-22にも引っかかってしまいます
#include <stdio.h>
#include <stdlib.h> // rand, srand使用
#include <time.h> // time使用
#define size 12000000 //bit列の長さ定義

↓

**デフォルトの名無しさん** · 2007/11/02(金) 15:52:35

main()
{
FILE *outputfile; // 出力ストリーム
unsigned long int m,i=0;
char bit[size];
srand((unsigned) time(NULL)); // time関数からシードをセット
outputfile = fopen("bit.dat", "w"); // ファイルを書き込み用にオープン
if (outputfile == NULL) { // オープンに失敗した場合
printf("cannot open\n"); // エラーメッセージを出して
exit(1); // 異常終了
}
for(i=0; i<size-1; i++){ // 乱数を発生させ剰余を計算
m=rand()%0xffff;
bit[i]=m;
}
fwrite(&bit,size,1,outputfile); //バイナリの書き込み
fclose(outputfile); // ファイルをクローズ
return 0;
}

↓公式ページ
NIST ttp://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
diehard ttp://stat.fsu.edu/pub/diehard/

**デフォルトの名無しさん** · 2007/11/03(土) 03:37:01

>>31
rand()は乱数としての性質があまりよろしくないという
当たり前のことを文句言われてもどうかと。

**デフォルトの名無しさん** · 2007/11/03(土) 12:45:15

>>32

> rand()%0xffff

一般論として、
剰余を取っても良質な疑似乱数列となっていることが保証されている
乱数生成系でない場合は、剰余ではなく商を取って一定の範囲に
切り詰めるべき。

歴史的に、システムのデフォルトの乱数生成系は品質の悪いものが
多いので、良い疑似乱数が必要なら、マニュアル等で良質な
乱数生成系を使っていることが確認できなければ、デフォルトの
生成系は使うべきでない。

**デフォルトの名無しさん** · 2007/11/03(土) 17:26:32

そんなのどうでもいいじゃん
だからまあ普通はラッパーかけて開発中はrand使って
あとで精度ほしくなったら差し替えるように作るわけだが

31 · 2007/11/03(土) 23:00:03

>>33-35
早速の返答ありがとうございます。
色々とマヌケな勘違いをしていましたorz

rand()は「暗号用乱数に相応しくない乱数」の一例として示すために用いました。
剰余をとったのは、良質なRNGならば下位bitの乱数性もまた良質だろう
ということを逆説的に示すためです。

NISTに同梱されている線形合同法のRNGはテストをパスし、
逆に上記のプログラムで生成した乱数列は全く話にならなかったので、
バイナリへの変換の仕方がマズかったのかと思っていました。

NISTは線形合同法くらいなら通ってしまうと聞いたので
てっきりrand()でもイケるものだと…orz

**デフォルトの名無しさん** · 2007/11/04(日) 05:32:17

>>36
実行はできてるんだね。
オレの環境だと>>31-32のコードは動かないんだけど。
# 原因はスタックに置くには配列サイズがでかすぎることみたいだけど。

乱数の質に絡みそうな部分というと型の選択がまずいんじゃね？
charじゃなくてunsigned charの配列にしたらどう？
それと剰余が違うんじゃね？
rand()%0xffff → rand()&0xffff でしょ。
あとループの回数も一回少ないと思う。

**デフォルトの名無しさん** · 2007/11/05(月) 02:14:18

RAND__MAXと0xffffってどっちが大きいか知ってる？

**デフォルトの名無しさん** · 2007/11/10(土) 21:14:12

RAND_MAXの値は実装にもよるかと。

そんなことより、rand()%0xffff → rand()&0xffff　　←こいつに誰か突っ込まんのか。

**デフォルトの名無しさん** · 2007/11/10(土) 21:27:10

うん

**デフォルトの名無しさん** · 2007/11/10(土) 21:39:02

そんなことよりxorshiftの話しよーぜ

**デフォルトの名無しさん** · 2007/11/11(日) 19:11:45

unsigned long xor32(){
static unsigned long y=2463534242;
yˆ=(y<<13);y=(y>>17);return (yˆ=(y<<5));}

unsigned long long xor64(){
static unsigned long long x=88172645463325252LL;
xˆ=(x<<13);xˆ=(x>>7);return(xˆ=(x<<17));}

unsigned long xor96(){
static unsigned long x=123456789,y=362436069,z=521288629;unsigned long t;
t=(xˆ(x<<20))ˆ(yˆ(y>>11))ˆ(zˆ(z<<27))ˆ(wˆ(w>>6));x=y;y=z;z=w;return(w=t);}

unsigned long xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;unsigned long t;
t=(xˆ(x<<11));x=y;y=z;z=w;return(w=(wˆ(w>>19))ˆ(tˆ(t>>8)));}

unsigned long xor160(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123,v=5783321;unsigned long t;
t=(xˆ(x>>7));x=y;y=z;z=w;w=v;return v=(vˆ(v>>6))ˆ(tˆ(t>>13));}

unsigned long xor192(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123,v=5783321,d=6615241;unsigned long t;
t=(xˆ(x>>2));x=y;y=z;z=w;w=v;v=(vˆ(v<<4))ˆ(tˆ(t<<1));return(d+=362437)+v;}
こんな具合か

42 · 2007/11/11(日) 19:16:33

コピペ丸張りで色々とおかしくなってることに気付く。
後悔はしていない。

**デフォルトの名無しさん** · 2007/11/11(日) 20:03:25

>>40
意味とランダム度が全然違うだろ。

**デフォルトの名無しさん** · 2007/11/11(日) 20:05:36

>>42
これってsrand()に相当する関数は自作しなきゃいかんよね？

**デフォルトの名無しさん** · 2007/11/13(火) 04:38:48

>>45
srand_xor(int hoge)
{
extern static int x;
x=hoge;
}
これでいいんとちゃう？ん？staticはexternできなかったっけ？

**デフォルトの名無しさん** · 2007/11/13(火) 08:50:49

>>46
アホかい。

**デフォルトの名無しさん** · 2007/11/13(火) 17:51:10

分からなかったらとりあえずクラス化→private属性のクラス内変数で（ｒｙ

**デフォルトの名無しさん** · 2007/11/16(金) 23:27:42

あるシードを使うと、得られる乱数を繋げたバイナリが
偶然たまたま迷走Mind.mp3 として読めるような
乱数ジェネレータを作ったらどうだろうか。

**デフォルトの名無しさん** · 2007/11/16(金) 23:44:09

確率的にありえない

**デフォルトの名無しさん** · 2007/11/17(土) 00:09:54

意図的に作るんなら偶然じゃないな

**デフォルトの名無しさん** · 2007/11/17(土) 00:27:25

PSG

**デフォルトの名無しさん** · 2007/11/17(土) 05:19:51

>>42 には間違いがあるので注意

**デフォルトの名無しさん** · 2007/11/17(土) 05:24:13

訂正したコードを示した方が有用なレスになると思うよ。

**デフォルトの名無しさん** · 2008/01/02(水) 19:12:39

>>42 の

unsigned long xor32(){
static unsigned long y=2463534242;
y?=(y<<13);y=(y>>17);return (y?=(y<<5));}

の y=(y>>17) は y^=(y>>17) とすべき

**デフォルトの名無しさん** · 2008/01/06(日) 13:04:45

XORってライブラリ化してないの？

**ヽ・´∀｀・,,）っ━━━━━━┓** · 2008/01/07(月) 00:17:55

めぼしいのはBoost.Randomにある

**デフォルトの名無しさん** · 2008/01/07(月) 12:16:11

団子あげ

**デフォルトの名無しさん** · 2008/01/13(日) 16:23:59

MTの別実装を作ってみました。
ttp://mt-lite.sourceforge.net/index.html.ja

基本のアルゴリズムはいじらず実装だけを作ったもので、
メモリ節約・リアルタイム性・スレッドセーフなどに一通り配慮したつもりです。

mt19937ar・SFMT・WELL・Xorshiftなどとの比較評価はこのあたりに:
ttp://mt-lite.sourceforge.net/doc/ja/evaluation.summary.html

**デフォルトの名無しさん** · 2008/01/14(月) 01:05:03

乙

**ヽ・´∀｀・,,）っ━━━━━━┓** · 2008/01/14(月) 01:28:22

SFMTのスレッドセーフ実装なら京大の人のページにあったぞ。SSE2だけだけど。

**デフォルトの名無しさん** · 2008/01/14(月) 01:48:05

XorShiftをseed使えるようにする場合、どうすればいいかな？＜何度もブン回す以外で