疑似乱数２

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

前スレ
擬似乱数
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

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

俺用メモ

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)) );
}

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

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

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

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

>>7意味不明

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

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

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

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

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

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

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

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

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

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

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

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

MT使え。
いじょ。
終了。

再開

初心者ですみません。

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

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

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

COBOLで乱数が必要なのか？

使えないとちょっとCOBOL

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

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

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

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

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

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

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

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

ド素人なので突っ込みどころがあったら御教授ください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列の長さ定義

↓

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/

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

>>32

> rand()%0xffff

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

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

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

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

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

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

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

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

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

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

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

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

うん

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

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;}
こんな具合か

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

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

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

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

>>46
アホかい。

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

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

確率的にありえない

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

PSG

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

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

>>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) とすべき

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

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

団子あげ

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

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

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

乙

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

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

http://web.comlab.ox.ac.uk/oucl/work/richard.brent/random.html

>>63
thx

/* xor128()をSSE2で実装してみました。XorShift は SIMD に向かない事がわかりました。*/
#include <stdio.h>
#include <time.h>
#include <emmintrin.h>
unsigned long xor128(void){
static unsigned long x=123456789UL,y=362436069UL,z=521288629UL,w=88675123UL;
unsigned long t;t=(x^(x<<11));x=y;y=z;z=w;return(w=(w^(w>>19))^(t^(t>>8)));}

unsigned long xor128sse2(void){
static union{unsigned long v[4];__m128i m;}u={123456789UL,362436069UL,521288629UL,88675123UL};
__m128i x=u.m, w, t, r; r=_mm_slli_epi32(x,11);t=_mm_xor_si128(x,r); w=_mm_srli_si128(x,12);
x=_mm_srli_si128(x,4); r=_mm_srli_epi32(w,19);w=_mm_xor_si128(w,r); r=_mm_srli_epi32(t,8);
t=_mm_xor_si128(t,r); w=_mm_xor_si128(w,t); r=_mm_slli_si128(w,12);x=_mm_or_si128(x,r);
_mm_store_si128(&u.m,x);return(u.v[3]);}

void main(void){long i,c;
for(i=0;i<16;i++)printf("%8lx %8lx\n",xor128(),xor128sse2());
c=clock();for(i=0;i<50000000L;i++)xor128(); printf("xor128(): %4lu msec\n",clock()-c);
c=clock();for(i=0;i<50000000L;i++)xor128sse2();printf("xor128sse2():%4lu msec\n",clock()-c);}

32 行書けるんだからもうちょっと綺麗におながいします

上のほうでrand()をダイハードに食わせるとかいってた人がいたのでオチを教えておきます。
p=1.0頻発します。テストの種類によっては部分がすべてp=1.0　あわせてp=1.0みたいな。

xor128（）って、例の論文に載ってるコードを組み込む場合、ライセンスはPD扱いですか？

>>65
こりゃ無茶だろ．こういう使い方は．．．
別の種の乱数を４個同時に生成するのが正解

>>62
xor128内部で使われてる変数x,y,z,wの中のxに、デフォルトの数値(123456789)の変わりに
与えられたseed値を代入するようにしてみた。
一応ちゃんと動作してるっぽいが統計的に良いのか悪いのかはよく分からん

>>69
初期値ってあの値じゃなくても良かったのね。
乱数の質がどの程度変わるのかが気になるが

やっつけでtimeの値入れたり

SEED値を入れるならxよりwの方がいい気がする

/* >>68 さん。的確なアドバイスありがとうございます。>>68 さんの方法で書いてみました。*/
/* 種で初期化する関数付き。XorShift の SSE2 による高速化はあきらめるしかないのか！ */
#include <stdio.h>
#include <time.h>
#include <emmintrin.h>
unsigned long xor128(void) {
static unsigned long x=123456789UL,y=362436069UL,z=521288629UL,w=88675123UL;
unsigned long t;t=(x^(x<<11));x=y;y=z;z=w;return(w=(w^(w>>19))^(t^(t>>8)));}

int idx=4; union { unsigned long v[4]; __m128i m; }
x={123456789,123456789,123456789,123456789},y={362436069,362436069,362436069,362436069},
z={521288629,521288629,521288629,521288629},w={ 88675123, 88675123, 88675123, 88675123};

void sxor128x4(unsigned long s)
{int i; for (idx=4,i=0;i<16;i++) x.v[i]=s=1812433253*(s^(s>>30))+i; }

unsigned long xor128x4(void) { __m128i t,r,s;
if (idx==4) { r=_mm_slli_epi32(x.m,11); t=_mm_xor_si128(x.m,r); x.m=y.m; y.m=z.m;
s=z.m=w.m; r=_mm_srli_epi32(s,19); s=_mm_xor_si128(s,r); r=_mm_srli_epi32(t,8);
t=_mm_xor_si128(t,r); s=_mm_xor_si128(s,t); w.m=s; idx=0; }
return(w.v[idx++]); }

void main(void){ long i,c;
for (i=0;i<9;i++) printf("%8lx %8lx %8lx %8lx %8lx\n",
xor128(),xor128x4(),xor128x4(),xor128x4(),xor128x4() );
for (sxor128x4(1),i=0;i<9;i++)
for (printf("\n"),c=0;c<4;c++) printf("%8lx ",xor128x4() );
for (c=clock(),i=0;i<100000000L;i++) xor128();
printf("\n(xor128():%lu msec), ",clock()-c );
for (c=clock(),i=0;i<100000000L;i++) xor128x4();
printf("(xor128x4():%lu msec)\n",clock()-c ); }

>>73
その種の使い方、MTと全く同じだな

XorShiftの正しいシードの設定方法を教えてくれ！

論文の６ページ目に xor128 の seed set は全て０の場合を除いて、どの
ように設定してもよいと書いてある。しかし、極端な設定をすると不自然
な部分列が出力される。そこで初期化の方法はＭＴを参考にした。ｉを０
からではなく１から始めた理由は０を種にしたときに最初の２つの出力が
似た値にならないようにするためである。配列を使っているが、スピード
はオリジナルとほとんど変わらない。コンパイラによっては、こちらの方
が速くなる場合もある。デフォルトの初期ベクトルは rand,srand になら
って種を１としたときと同じである。

unsigned long MyVec128[4]=
{ 1812433254UL, 3713160357UL, 3109174145UL, 64984499UL };

void MySeed128(unsigned long s)
{
int i;
for (i=1;i<=4;i++) MyVec128[i-1]=s=1812433253UL*(s^(s>>30))+i;
}

unsigned long MyXor128(void)
{
unsigned long *a=MyVec128, t=a[0], w=a[3];
a[0]=a[1]; a[1]=a[2]; a[2]=w;
t^=t<<11; t^=t>>8; w^=w>>19; w^=t; a[3]=w; return w;
}

なるほど、どんな初期値であっても、2^128-1のどこかの部分列になってるのか

>>61について誰か詳しく頼む

ん？　何が分からなかった？

遅いんだよ
もういい

はやっ

こんな過疎スレで遅い言われても

自分がいくら張り付いてるからって、ね。

>>61のソースの所在教えてくれ
パクる

dSFMTだったごめん。
http://nct.brain.riken.jp/~takekawa/softwares.xhtml


あとこんなのもあった。
http://charles.karney.info/random/

thx

ダンゴさんはSSEネタには造詣が深いな。

じゃあ上げとこ

シミュ板、数学板に乱数スレ発見。
乱数
http://science6.2ch.net/test/read.cgi/sim/1100375806/
乱数の生成方法を必死になって考えるスレ　
http://science6.2ch.net/test/read.cgi/math/1203153071/

あげ

XORSHIFTって、その出力の剰余を取った場合も
良質なランダム性があるって言われているのでしょうか？

XORSHIFTは良質ではないと思います

工工エエエｴｴ（´Д｀）ｴｴエエエ工工

MTが一番良質と思います　XORは速度は速いです　用途によっては十分です

>>91です。
XORSHIFTで剰余を取った時の結果を載せてる
WEBページを見た気がするのですが、結果が
今一だったような記憶が・・・

自分でも試してみようと思っているのですが、
理論的には説明出来そうにないし。

>>95
そのWEBページのURL教えてくれ

>>96
個人のブログですが、確かここだったと思います。
ttp://d.hatena.ne.jp/Isoparametric/20070830/1188462129

今、改めて読んでみると、よく意味分からん・・・

たった100回回しただけなら偏りも出るだろう

はぐれめたるは捕まえられますか？

>>99
むり

単純に何の補正も無い相手に対して「捕まえられる」確率はどのくらいか。
そしてはぐれメタルが逃げない確率はどのくらいか。
その両方のデータをくれ。

乱数とどういう関係があるんだ

え？はぐれメタルの行動を決めている乱数テーブルの解析の話じゃないの！？

ここは「擬似乱数生成アルゴリズム」に関する議論のスレッドだ

PS2のドラクエ５では壁の衝突回数をカウントして乱数列の初期化してるようだ。
オラクルベリーの教会から一度も壁に衝突せずにカジノのスロットに直行すると
全く同じパターンが出てくるとか。

おそらくはぐれメタル捕獲にも何らかのパターンがあるかと

全然ちげーよ、ばかが

「ヽ・´∀｀・,,）っ━━━━━━┓」は放置推奨クソコテ

英語版MTを読んでいたらこんなのを見つけた。
ttp://en.wikipedia.org/wiki/Multiply-with-carry
で、cで実装してみた。
あんまり使えないと思うけど。

/* Complementary Multiply With Carry */
void initialize( unsigned long );
unsigned long cmwc( void );
enum { A = 3636507990, B = 0xffffffff, R = 1024 };
unsigned long seed[ R ], index, c;

void initialize( unsigned long n )
{
unsigned long i;
for (i=0; i<R; i++) {
seed[ i ] = n;
n = n * 1103515245 + 12345;
}
index = c = 0;
}
unsigned long cmwc( void )
{
unsigned long x;
unsigned long long t;
t = (unsigned long long)seed[ index ] * A + c;
x = B - (unsigned long)( t & B );
c = (unsigned long)( t >> 32 );
seed[ index ] = x;
if ( ++index >= R ) index = 0;
return x;
}

>>105
http://www.astr.tohoku.ac.jp/~ajiki/cheap_restaurant/GAME/SAGA2/saga2rand.html
サガ2の乱数発生器

DQ5もソース見れば多分判ると思うよ

DebianのOpenSSLライブラリに予測可能な乱数の生成を行う脆弱性 - ITmedia
ttp://www.itmedia.co.jp/enterprise/articles/0805/15/news023.html
↓
OpenSSLの脆弱性突くブルートフォース攻撃発生、簡単に暗号解読の恐れ - ITmedia
ttp://www.itmedia.co.jp/news/articles/0805/16/news019.html

Debian JPプロジェクトのアナウンス
ttp://www.debian.or.jp/blog/openssl_package_and_its_vulnerability.html

まとめ乙

保守

M系列という単語を見かけたので、理解してないまま保守リンク
http://pc11.2ch.net/test/read.cgi/tech/1158367586/751-

VBAで、dll使わずに高機能な乱数を実装する方法はないですか？
XorShiftを使うには、長桁計算しかないですか？

' Xorshift を VBA で書く場合、Double を使うと比較的シンプルになる
' VBA の演算子 Xor と関数 Fix は 31 bit までしか扱えないので
' 53 bit まで扱える関数 uFix、uXor を用意した。
Option Explicit
Public x, y, z, w As Double

Function uFix(ByVal x As Double) As Double
Const Base = 2# ^ 22
Dim y As Long
y = Int(x / Base): uFix = y * Base + Int(x - y * Base)
End Function

Function uXor(ByVal i As Double, ByVal j As Double) As Double
Const Base = 2# ^ 22
Dim u, v As Long
u = Int(i / Base): v = Int(j / Base): i = i - u * Base: j = j - v * Base
uXor = (u Xor v) * Base + (Int(i) Xor Int(j))
End Function

Function xor128() As Double
Dim t As Double
t = x * 2# ^ 11: t = t - Int(t / 2# ^ 32) * 2# ^ 32
t = uXor(x, t): x = y: y = z: z = w: t = uXor(t, uFix(t / 2# ^ 8))
w = uXor(uXor(w, uFix(w / 2# ^ 19)), t): xor128 = w
End Function

Sub Test()
Dim i As Long
x = 123456789#: y = 362436069#: z = 521288629#: w = 88675123#
For i = 1 To 2000: Cells(i, 1) = xor128: Next
End Sub

' 書き込んだ後、uFix は必要がないことに気づきました。
' こっちの方が高速です。
Option Explicit
Public x, y, z, w As Double

Function uXor(ByVal i As Double, ByVal j As Double) As Double
Const Base = 2# ^ 30
Dim u, v As Long
u = Int(i / Base): v = Int(j / Base): i = i - u * Base: j = j - v * Base
uXor = (u Xor v) * Base + (Int(i) Xor Int(j))
End Function

Function xor128() As Double
Dim t As Double
t = x * 2# ^ 11: t = t - Int(t / 2# ^ 32) * 2# ^ 32
t = uXor(x, t): x = y: y = z: z = w: t = uXor(t, Int(t / 2# ^ 8))
w = uXor(uXor(w, Int(w / 2# ^ 19)), t): xor128 = w
End Function

Sub Test()
Dim i As Long
x = 123456789#: y = 362436069#: z = 521288629#: w = 88675123#
For i = 1 To 2000: Cells(i, 1) = xor128: Next
End Sub

>>116
１１４です、ありがとうございます。32bitのXorShiftですね。

で、周期の途中から乱数を取り出して使いたいのですが、
x,y,z,wの初期値を乱数で設定するのに、デフォルトのrnd()を使ったら無意味ですよね。

>>75あたりか

'種を使って初期化できます。116よりさらに２倍程度高速になりました
Private Const p32 = 2# ^ 32, p31 = 2# ^ 31, p21 = 2# ^ 21, p11 = 2# ^ 11
Private Const m53 = 2# ^ -53, m32 = 2# ^ -32, m30 = 2# ^ -30, m19 = 2# ^ -19, m11 = 2# ^ -11, m8 = 2# ^ -8
Private x, y, z, w As Double
Private f As Boolean
Private Function uXor(ByVal x As Double, ByVal y As Double) As Double
Dim u, v As Long
If x >= p31 Then u = x - p32 Else u = x
If y >= p31 Then v = y - p32 Else v = y
u = u Xor v
If u < 0 Then uXor = u + p32 Else uXor = u
End Function
Private Function XSub(ByVal x As Double, ByVal i As Long) As Double
Dim s As Variant
s = CDec(1812433253) * CDec(uXor(x, Int(x * m30))) + CDec(i): s = s - CDec(Int(s * m32)) * CDec(p32): XSub = s
End Function
Public Sub InitXor(ByVal s As Long) ' s を種にして乱数を初期化する
f = True: x = XSub(s, 1): y = XSub(x, 2): z = XSub(y, 3): w = XSub(z, 4)
End Sub
Private Function NextXor() As Double
Dim t As Double
If f = 0 Then InitXor (1)
t = x * p11: t = t - Int(t * m32) * p32: t = uXor(x, t): x = y: y = z: z = w: t = uXor(t, Int(t * m8)): w = uXor(uXor(w, Int(w * m19)), t): NextXor = w
End Function
Public Function NextUnif() As Double ' 0 以上 1 未満の乱数を返す
Dim x, y As Double
x = NextXor * m11: y = NextXor: NextUnif = (y * p21 + Int(x)) * m53
End Function

xorshiftって周期とか分布の保証ってあるの？
もしないならM系列の方がましだと思うんだけど。
ググれば長周期の多項式も見つかるし。

劣化Ｍ系列と理解してるが

早くて軽くてrandよりマシ

>>119
excelVBAじゃ初期化するための種が結局16bitしかないんだから
Xorshiftの種も16bit種類しかなくならね？

種 s は Long なので32bit種類あるが、負の場合は試してないので実質31bit種類。

VBAのRandomizeが16bit種類
それを使って初期化後rnd()で取得できる乱数も16bit種類
XorShiftの種にそれらを使うのなら結局系列は16bit種類

本当の最初の最初に32bitの乱数をセットするときにどうすればいいのか。
32bitのランダムな位置からXorShiftを開始するのに、そのうちの16bit分しか設定できない。

よく分からんが服を買いにいく服がない状態か

>>125

確かにそうだ。困ったもんだ。

>>125
GetTickCountとかCryptGenRandomとかWin32APIに頼ればいいじゃない。

>>128
とりあえず
Private Declare Function GetTickCount Lib "kernel32" () As Long
後に
　　GetTickCountを使って取得するようにしたよ。

暇だったからSFMTのC++ template実装やってみた
http://tripper.kousaku.in/20080914.html

GJ！
前スレからずっと待ってました

あ、なんだ
TR1対応じゃなくて純粋にテンプレート版なのか

そのうちBoost風に作り替える予定

乱数って巻き戻しできないの？

>>134
乱数の巻き戻しって何?

予想すると
あるシードでのn番めの乱数を出したあとに、n-1番目の乱数を
定数時でだせないか？
ってことでは

>>136
そのとおりでございやす

n-1番めからn番めを求める計算がたいてい非可逆だから無理

巻き戻す必要がある数分だけ乱数の結果を保存するしかないだろうなぁ

XorShift ならちょっと考えればわかる。
線形合同法なら 2^{31}-1 だけ進めた x=Ax+C の A と C を求めれば可能。
メルセンヌツイスタやWELLなら
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf
の方法で周期よりも一つ少ないところへジャンプすれば不可能ではないはず。

これって読み捨てるのと比べてどのぐらい高速？
MTの先頭の何百万個か読み捨てる処理に使えそう？

何百万よりは速いだろうが、100程度なら大差ない。

と、コード見ないで言ってみる

flashのActionScriptの乱数Math.randomって何bit？

25くらい

MTならFORTRANだけど
ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/FORTRAN/fortran.html
この中に
revrand(): it generates prn in reverse order
って書いてあるけど

MTの巻き戻しのフォートランをCに移植してみた。

#define main dummy
#include "mt19937ar.c"
#undef main

unsigned long revgrnd(void) {
static unsigned long mag01[2]={0x0UL,MATRIX_A}; unsigned long y=mt[--mti],z,p,q,mt0L,mt0; int x,kk;
if (mti==0) {
z=mt[N-1]^mt[M-1]; x=(int)(z>>31); y=z^mag01[x]; p=(y<<1)|x; mt0L=LOWER_MASK&p; mt[0]=(mt[0]&UPPER_MASK)^mt0L; mt0=mt[0];
for (kk=N-1;kk>N-M;kk--) { z=mt[kk-1]^mt[kk-1+M-N]; x=(int)(z>>31); y=z^mag01[x]; q=(y<<1)|x; mt[kk]=(UPPER_MASK&p)|(LOWER_MASK&q); p=q; }
for (;kk;kk--) { z=mt[kk-1]^mt[kk-1+M]; x=(int)(z>>31); y=z^mag01[x]; q=(y<<1)|x; mt[kk]=(UPPER_MASK&p)|(LOWER_MASK&q); p=q; }
mt[0]=(UPPER_MASK&p)|mt0L; y=mt0; mti=N;
}
y^=(y>>11); y^=(y<<7)&0x9d2c5680UL; y^=(y<<15)&0xefc60000UL; y^=(y>>18); return y;
}

int main(void) {
int i; static unsigned long x[5000],y[5000];
for (i=0;i<5000;i++) x[i]=genrand_int32();
for (i=4999;i>=0;i--) y[i]=revgrnd();
for (i=0;i<5000;i++) if (x[i]!=y[i]) { printf("ERROR\n"); break; }
for (i=0;i<10;i++) printf("%08lx %08lx\n",x[i],y[i]);
return 0;
}

とつげき東北とかいう人の乱数生成法を見て思いついたけど
メモリを確保して、読み書きする速度を計測すれば真の乱数できそう。
もともとはハードディスクの読み書きだが。これだと生成に時間食う。

これね。

ハードウェア乱数生成ルーチンhdrand.c　　by　とつげき東北　
http://www.interq.or.jp/snake/totugeki/hdrand.htm

でもメモリが余ってるときに均一に分布したとしても一杯になったら悪くなるかも試練ね

>>147
時には極端に偏ってくれないと真の乱数とはいえないな。

Unix の /dev/random は、デバイスドライバからそういう真の乱数を
生成するようなタイミングの情報をもらってデータを生成しているのだが...

実行時まで偏ってるかどうかすら分からんから実用的には疑問だけどな。
違うハードの組み合わせで似たようなシードが繰り返し出てしまう可能性も否定出来ん。
特性が誰にも分からんから乱数としてもいいだろうって発想は学問的ではないな。

元手にするだけで、そのまま使うはず無いだろ。
たとえば、メモリ確保と読み書きした間隔が
1ナノ秒から100ナノ秒に分布しても偏りはでる。
そこは適切に処理して良い具合にする

メモリの読み書きレイテンシがどういう条件で決まるかわかって言ってるか？

srand(0)とsrand(1)はその処理系でも同じ系列を生成するのですか？

その処理系て？

なんだろね？

ところでシードに関して系列という単語がよく出るけど違和感が…
乱数アルゴリズムの多くはシードは開始位置を決めるだけで
同じ乱数列を参照してるんだよね。
イメージ的には馬鹿でかい時計のようなものがあって、
秒針よりももっともっと小さい針が数字を拾ってる感じ。
系列という言葉だとそれぞれが全く違う乱数列のように聞こえる。
まあ現実的には2^128くらいあれば被ることはないと思うけどさ。
なんか気になる。

まちがえました。
「その処理系でも」→「他の処理系でも」
でした。

srandはアルゴリズムからしてライブラリの実装次第だから
処理系以前に互換性はないと思え。
そもそもrand自体0からRAND_MAXまでの整数を出力するとかそういう定義しかないはず。
確かMTはその辺しっかりしていて、どこでも同じ結果が得られたはず。

>>157
rand() を実装するために使用する手法がいろいろあり、たとえば線形合同法・Ｍ系列・メルセンヌツイスタなどと呼ばれるものでしょうね。
手法とパラメータさえ同一であれば、当然同じ乱数列が生成されますが、rand()/srand() がどのように実装されているか、明確に
定義されているわけではないので、なんともいいようがないですね。

>>148
>MTのような、周期の長い良質な擬似乱数の種としてこれを使えば、暗号ツールなどに実用的に応用できる。

MTのような暗号的に安全ではない擬似乱数の種に、暗号的に安全な乱数
を使っても出力は暗号的に安全ではないよな？
この記述はおかしいよな？

いや。

暗号的に安全ではない乱数生成系を、暗号関係の目的で使用するには、
出力ストリームに一方向ハッシュ関数を噛ませる方法がある。

その時に、シードは予測不可能なものである必要がある。

NIST test 2.0bってどうなの?

なんかDFTで必ず落とされるんだけど。
とりあえずMT19937, G using SHA-1, Micali-Schnorr試したけど駄目だった。

そりゃすげぇ
真の乱数で試してみたら？　スレ違いだけど...

真の乱数も試したけど駄目だった。
なんかp valueの分布が高いほうに偏ってる。

ffmpegで有名なMichael Niedermayerさんの記事
Pseudo random number generators
http://guru.multimedia.cx/pseudo-random-number-generators/
Pseudo random number generators 2
http://guru.multimedia.cx/pseudo-random-number-generators-2/

再現可能な擬似乱数じゃないけど、こんなんみつけた

ハードウェア乱数生成ルーチンhdrand.c
http://www.interq.or.jp/snake/totugeki/hdrand.htm

概要をコピペ
> テンポラリファイルフォルダにファイルを作成・削除し、その処理にかかった時間
> を高分解能パフォーマンスカウンタで計測して、処理時間を得る。
> 処理時間のビット列のうち、偏らないビットを乱数ビットとして利用する。
> ハードディスクのシーク時間や物理的な書き込み速度は、キャッシュや温度や湿度や
> Windowsの処理順などによってばらつきがあるので、良質なランダムビットがとれる。
> 測定されるビットの変化を最初にテストしておくことで（100回のビット発生で、
> 充分に変化が見られたビットだけを乱数に使用する）、処理速度の違いや、パフォーマンスカウンタの質の悪さ（例えば最下位ビットが必ず偶数や奇数になる可能性）も吸収できる。

WindowsってOSにこのてのメカニズム持ってないのか？

ん、こういうの俺も昔遊びで作った事がある。

SFMTをExcelで使うなら、シード値ってどうやりゃいい？
sgenrand Timer * 1000
なんてのがどっかにあったが、なんかいまいちだよな。

>>169
ハードウェア使った処理が含まれているかどうかは分からないけど、
暗号論的に安全なのが欲しければ、CryptGenRandom使えということになっている。

>>166の続き。ffmpegではMT (Mersene twister)の質が悪く遅いということで非推奨(deprecated)にされました。質が良いのを使いたいならMLFGやKISS99を使えとのこと。
http://lists.mplayerhq.hu/pipermail/ffmpeg-cvslog/2009-March/021108.html

何が問題なんだろ。
松本さんの実装は、内部状態が1周した時に一斉に計算するようになってるので、
負荷が一定しないよなぁとは思うんだが、そういうとこじゃなくて、原理的に問題が
ある、っつってんだよね。
遅いというのは、はあそうですか、というだけなんだけど、blogのほう見ると、
XOR だけで構成されている、ってことをdisってるように見えるんだが...

KISS99もシンプルだし悪くはないんだが

>>174
ブログで参照しているこのペーパーにあるMT19937のテスト結果がCrash 2回、BigCrash 2回になっているからだからだと思う。
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf
誰か解説キボン

どんなアルゴリズムであっても一周期において均等分布を達成するとなると
全てのビットパターンを発生させるという点で結局M系列と同じ事になるんだよな。
するとマクロではみんな十分にランダムということになるから、
あとはミクロでのランダムさとその実装方法からくる計算量が問題なわけだな。
そのあたりに何かあるんじゃなかろか。

なんかその論文で提案してるテストでは、暗号学的な強度のあるジェネレータ以外は
のきなみパーフェクトでない結果を出してるみたいだ。
MTの成績が際立って悪いとかそういう結果ではないけど、ffmpegの作者的には
気になる結果なのかな？

元々そちらの専門家みたい

ダメ

http://en.wikipedia.org/wiki/Mersenne_twister#Alternatives
>The Mersenne Twister algorithm has received some criticism in the computer science field, notably by George Marsaglia.
>These critics claim that while it is good at generating random numbers, it is not very elegant and is overly complex to implement.
>Marsaglia has provided several examples of random number generators that are less complex yet which he claims provide significantly larger periods.
>For example, a simple complementary multiply-with-carry generator can have a period 10^33000 times as long, be significantly faster, and maintain better or equal randomness.[5][6]

*5 http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a4424068/
*6 http://groups.google.com/group/sci.crypt/browse_thread/thread/305c507efbe85be4

スワヒリ語でおｋ

なんか見覚えある名前だなーと思ったらXorshiftの人だったか

あげ

次は185が出てくる

お初ですが質問させてください。

現在sfmtについて作成者のHPにあるプログラムを見て勉強しています。

そこで64bitでシフトしてる部分があって、unsigned long long等が対応していないコンパイラでやる場合(32bitまでしかない)、何かいい方法はありますか？
自力で32bitでシフトしてもいいのですが…

初心者なので意味不明な説明かもしれませんが、参考になる方法やHP等ありましたら教えてください。

そこだけ__asm { } でインラインアセンブラで書くとか

int64が無いコンパイラだとasmも無さそうな

>>186
具体的なロジックを出さないと、曖昧なレスしかつかないよ。

186です。

さっそくの返信ありがとうございます。

一応必要な部分だけアセンブラで書くことも可能だったと思いました。ただ現在携帯からの書き込みでキツいので、あとでまた書きます。

>>186
ないから自力でやれ

どなたかご教示願います。
lehmerの線型合同法で作成される乱数値は、
初期値が同じでも計算機環境の違いにより変わることはありますか？

うん

同じ数式を計算したのに計算機環境の違いで結果が変わることがあると思う？

浮動小数ならよくある

>>> (2 / 3) * 6
0
>>> 6 * 2 / 3
4

>>193>>195>>196

ありがとうございました。

>>196
それらは「同じ数式」といえるのか?

>>194
有効桁数をちゃんと制御して、その動作が保証されている言語を使うなら、
バグでない限り有効桁数の範囲で変わることはない。

ただ同じ数式の同一の変数に別の値を与えたのなら変わってもおかしくないよ。
つかそれ以前に疑似乱数に関係あるのかｗ

高次元均等分布性ってどういうこと？
p[i]=(x[Ni+0],x[Ni+1],…,x[Ni+N-1])
として作ったＮ次元乱数のＮ次元空間上散布図が
Ｎ次元空間内に平面作ったり偏ったりせずにぼんやり分布することと考えていいのかな？

誤解を恐れずに大雑把かつ簡単に言うと、
nビットの状態空間があるとして、
一周期の間に00...00から11...11までnビット(n桁)の数字が
過不足なく1回ずつ出現すること。
それが満たされると周期全体で直前のn-1ビットの状態に関わらず
次の1ビットの出現確立が必ず50:50になる。
つまりn-1次元で0と1が均等に分布したことになる。
状態空間を越えた次元では分布については全く保証出来ない。
だからMT含めて最近の擬似乱数はみんな状態空間をかなり大きめにとってる。

ただしこれはあくまで一周期のことであって、
一周期の一部を切り出した場合(通常の使用状況)では全然話が別ね。
マクロとミクロの違いというか両方同時に成り立たせるのは難しい。
よく0過多状態からの回復の速さが注目されるけど、
状態空間が大きいのに三項式とかだと(MTのことね)
0の多い区間はその前後でも0が多くなる。
逆に1の多い区間はその前後で1が多くなってトータルで均等になるわけさ。

一月あげ

unko

Blum-Blum-Shub のC/C++ の実装コードが掲示されているサイトを知ってる人いませんか？
java での実装例はここにあるんですが
http://code.google.com/p/javarng/

1+1=2

>>204
BlumBlumShub.java を C/C++ に書き換えるだけじゃだめなん？

C/C++ に BigInteger の標準的な代替物でもあれば楽勝だろうけど

blumblum.c とfreelip いうファイルを見つけ
http://www.mindspring.com/~pate/crypto/chap05/blumblum.c
http://math.arizona.edu/~aprl/math/comp/bigint/
blumblum.c をgcc (GCC) 4.2.4 でコンパイルするのですが
zcopy とか、zfree とか、zなんとかという命令がコンパイルできなくて詰まっています。
何なんだこのz何とかというコマンドは？cの命令セットにはないぞ、posix かなんかの命令セットなのか？

>>204、>>208です皆さんサンクスです。
>>207
その通りです、java からの移植はBigInteger を見て、ライブラリから作る羽目になりそうだったので
速攻あきらめました。boost にBlumBlumShubがあればいいのにな・・・・

>208
C/C++ ではコマンドとか命令とか命令セットとは言わないだろう、普通。
命令セットって言われたら CPU の instruction set を思い浮かべるわ。

で、freelip ってのの中に z* 入ってるじゃん。
C/C++ の分割コンパイルに詰まってるんだろうけど、とりあえず
gcc -o blumblum blumblum.c lip.c
とかで実行ファイルできない？

あと、boost vault には bigint が有ったような。使いものになるかしらんけど。

>210
gcc -o blumblum blumblum.c lip.c
このオペレーションも上手くいかない・・・orz

今度はオペレーションて

>>209 gmp じゃだめ？

どういうエラーが出てるのか書かなきゃ対処しようもないぞ

xorshiftをunsigned longではなく32bit intの範囲内でやる方法はありませんか？

complementary multiply-with-carry ってのが
周期長くて計算軽いってのは分かったけど
高次元での均等性はどうなの？
MTだと623個の組で使っても大丈夫ということだけど

RC4が最強だろ

>>215
符号無しの整数型が存在しない言語で実装しようとしているのか？
例えば、Javaとかだと符号付き整数型でも気にせずビット演算して大丈夫のはずなんだけど。

もう1つ、そのunsigned longはおそらく32ビットだと思う。コードを注意してみて。
違ったとしてもググれば32ビット符号無し整数(unsigned intだかunsigned longだか)での実装はすぐ見つかると思う。

最近できた疑似乱数をまとめたサイトとかない？

起動戦士ランダム♪ランダム♪

俺がランダムだ

シェーダ/GPGPU向けでよい疑似乱数ってどんなのがあるでしょうか。
数列系の疑似乱数を直に使うことが出来ないのでいろいろ考えています。

もっと具体的に書かないと分からん
メモリアクセスが厳しいとかそういう話か？

もう一つ
>数列系の疑似乱数
擬似乱数はみんな数列だぞ

ワーキングセットが小さい、って意味か？
確かにMTは比較的大きいが。

アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。
その際、2次元画面*時間の3次元で相関などがなく一様分布するノイズにしたいのです。
画素ごとに並列に計算できれば高速に計算できることは分かっているのですが、
数列を使う以上は基本的に一つずつ取り出すしかなく並列化できません。
そのため、並列計算で生成できる疑似乱数生成法がないかと探しているところです。

一応全画素に32バイト割り当てればそれぞれXorShiftの系列が張り付けられるかなとは考えましたが、
やはりちょっとワーキングセットが大きくなるのと、
XorShiftの系列間相関の有無がよくわからず、躊躇しています。

自分で実装しなければならないなら、各画素の計算では、画素の座標（各座標に固有だが相関たっぷり）と、
フレームごとに全部画素一律に参照できるベクトルを与えることができるので、
それをうまく使って乱数列の系列の途中の値をうまく与えられないかなあ、などと考えています。

プールして切り出し

xyz全部に相関なしか…そいつぁ難しいぜ
とりあえず画素毎に独立した個別の乱数を充てるのはダメだな
少なくとも画素以上の状態空間を持った乱数を用意しないと相関なしには出来ないんだぜ
適当に作っても任意の画素間で相関がないことを保証できないだろ？
そもそも同じ生成式を使えば初期値が違うだけで結局同じ乱数列しか得られないからな

とまあ大げさに書いたけど、本気で3次元完全無相関を目指してるわけじゃないよね？
落としどころとしてはMTとか周期の長い乱数を使って
一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
各画素はM系列とかXorShift?(いまいち信用できない)を使えばよろし。

遅れまして申し訳ありません。

>>228
勉強になります。
一瞬、隣の画素の状態を見ながらメルセンヌツイスタのように「捻れ」ないかと思いましたが、
結局そこでデータコヒーレンシーの問題で並列化できなそうなのでそれも無理そうですね

結構本気で3次元無相関を目指しているというか無相関であることが優先される用途なので、
現在は時間を仕切って有限の大きさにしてプールして切り出し、というのが現実的な解となっています。
ただ長時間やるにはメモリがいくらあっても不足するような感じなので、
なんとか生成できないかなあと思う次第です。
副産物として、落としどころとしてそれっぽいものを作ることは吝かでもないですが。

>>229
当然ながら精度と速度は両立しないんで、
どこまで必要なのか見極めて妥協することになるけど、
仮に1画素あたり32bitとして640*480なら、
最低でも1228800バイト以上の状態空間が必要だね。
これで1フレーム分だから残り何フレームまで必要なのか考えてみればいいよ。

>一瞬、隣の画素の状態を見ながらメルセンヌツイスタのように「捻れ」ないかと思いましたが、
MTの「捻り」はGFSRの短かった周期を理論値まで伸ばしてるだけ。
無闇に隣を参照したらダメだよ。

>>230
ありがとうございます。
まずはM系列からということでググったり本棚をあさったりしていたのですが、
疑似乱数を作るということは、どういう遍歴をたどる数列を設計するかという話だ、ということが改めて身にしみました。
また、正しく「捻る」にはビットの遍歴が最長となるよう正しくビット間の周回コースを繋がなければならない、という理解でいいのでしょうか。

＞ 落としどころとしてはMTとか周期の長い乱数を使って
＞ 一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
という話は、最初見たとき手抜き実装かなと思ってしまったりしたのですが、
冷静に考えるとCPU側とGPU側の状態は両方とも完全に決定可能なのだから、
周期や分布もちゃんと計算できるのですね。
この方法が自分の目的にとっては王道のような気がしてきました。

まったく不勉強で疑似乱数の世界の入場門がどこにあるかがやっとわかった状態ですが、
道筋がなんとなく見えてきたので、次に質問する前に、もっと自分で勉強してみたいと思います。
素人の思いつきに懇切丁寧にご回答いただきありがとうございました。

>>228
こういう用途なら、単純に１次元化して、正規乱数を利用すればいいんじゃないの？

それじゃ速度が出ないだろ
というかそれでいいなら質問してこないだろ

その前にその正規乱数はどこから持ってくるのかと小一時間(ry

>アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。

あれ、ほんとに相関なしなん？＞詳しい人
なんか、いいセルオートマトンとかありそうじゃない？

砂嵐状態っていっても度合いがあるからね。
元の信号が強く混ざってれば文字通り目に見えて分かるし。
砂嵐(スノーノイズ)の原因は熱雑音らしいから
S/Nが十分に悪ければ(笑)ほぼ相関なしといえると思う。

熱雑音はランダムか？という問題は話が別ね。
そっちは量子論の問題だから。
何か法則があるかも知れないしないかも知れないけど
とりあえず理論的に確認できる方法がないので(観測問題)
そこのところは考えないでおこうってのが今の主流。
どちらであっても今のところ結果は統計的な予測と一致している。
ので今のところ統計的に熱雑音はランダムと言えるっぽい。

そもそもランダム・不規則ってなんだ？ってのも哲学っぽくて難しい問題だ。
熱雑音も本当は原子の状態(擬似乱数でいう状態空間)を完全に知ることが出来れば
その後の振る舞いを予測することが出来るはずなんだけど(決定論)
前の状態と次の状態を同時に知ることが出来ない(観測問題)。
観測者の有無に関係なく次の状態は決まっていると考えたのはアインシュタインで
(神はサイコロを振らない)この説は今は少数派。
果たして観測者が次の状態に影響を与えた結果は如何に？

ところで仮に完全に熱雑音の振る舞いを表現することが出来たとして
それをもし理論的に解析できたとしたらその結果はランダムだろうか？
周期も分布も分かってる既存の擬似乱数の方が良かったらどうだろう？
今までに我々がランダムと呼んでいたものの正体は…？

仕組みが分かったところで、解を出すためには初期条件が必要
シードを与えて一意な結果を出すのは一般的な乱数と同じものだろ

>>237
何の話？

物理量を離散的に捉えるのは根本的に違ってるぞ

サンプリングすればおk

DOOM をソフトウェアラスタライズしていた頃と比べれば、リアルタイム程度なら CPU で mt やって充分間に合いそうな気がする。
こういう大量生成が対象なら、前に Cell スレで盛り上がってたコンテストの最適化がフィットすると思う。
そんで別の種でマルチスレッドでクアッドコアで、って感じでどうだろう。

プリレンダした砂嵐テクスチャ並べて適当に描画すれば？

>>242
それは正しい処理だが、スレタイを翌嫁。

>>242,243
それだとテクスチャが沢山必要になるからi/oで引っかかって
擬似乱数より遅くなるよ

二次写像などのカオスの数値の下ビットを使うというのはどうだろう

でも実際に相関がないことを証明する必要があると面倒ですね。
plot(rand mod 640,rand mod 400,rand mod 16)
とかでとびとび直線が出てびっくりですよ

>>245
数理的な意味でのカオスってのは、テント写像に代表されるように
小数点以下を無限に汲みだす漸化式になっているから予測が難しいのであって、
種が有限桁数であっては成立しない。

むしろ、いかなる相関性のある入力に対しても、
周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。

こんなことを言い出すやつがいるとは…
それは線形合(ry
このスレは分かってる人とそうでない人のレベル差が妙に大きいな

>むしろ、いかなる相関性のある入力に対しても、
>周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。
いいわけない、というかそれはただのハッシュ
等確率性・分布・周期を保証できないし
入力がずっと同じだったらどうにもならん

>>248
アンカが抜けてた

>228の
＞ 落としどころとしてはMTとか周期の長い乱数を使って
＞ 一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
に対して、それなら各画素で回す周期は短くていいんじゃないかなと。
等確率性と分布は証明or検証する必要性があるとして。

>>246
頭悪そうな意見だな。周期が短い時点で相関性アリまくりだろうが。
↓こういう馬鹿(道化師)がいたことを思い出す。
【危険】とんでもプログラム告発スレッド【悪質】
http://pc11.2ch.net/test/read.cgi/tech/1191860116/
1 名前：デフォルトの名無しさん[] 投稿日：2007/10/09(火) 01:15:16
劣悪なプログラムやアルゴリズムを、恰も優れたものだと言い張り、
他人を騙しているサイトを告発、検証、監視することを目的としたスレッドです。
単純に技量不足だったり、稚拙であるもの、下らないものは対象としません。
第一弾として、
道化師氏のサイト(http://www.trickpalace.net/)の
疑似乱数アルゴリズム「無相関性擬似乱数アルゴリズム-prime spiral-」
http://www.trickpalace.net/column/random.htm
を紹介します。このアルゴリズムおよび作者の言動の問題点は以下のとおり。
・MT(Mersenne Twister)がダメだと主張しながら、具体的な問題点は指摘できていない。
・MTより劣悪な乱数を生成しながら、MTより優れていると主張する。
・周期がたったの2^32のしかない(線形合同法と同レベル)
・無駄にテーブル参照するため遅い(線形合同法より劣悪)
・優れていると主張しながら、言葉の定義と評価基準を示すことはしない。
・indexと最低限の出力系列(各素数の和)が得られると、初期ベクトルが逆算ができてしまう。
・最低限の出力系列で、全パターンに出現する値の分布が確定する。
indexが確定すれば出現順まで確定するほど相関性が非常に高く劣悪。
・出ない値が確定するという点で乱数とはもはや呼べない。
・作者は暗号用途にも使えるつもりでいる。MTより「良い」乱数だと宣伝しているが、
実際は周期、分布などの点で低品質。信じて使うとろくなことにならない。

アルゴリズムの問題点や作者の人間性が明らかになる過程はこちらのスレで読めます。
擬似乱数
http://pc11.2ch.net/test/read.cgi/tech/1146071975/

これは過去ログ見てみたかったな
まあ乱数弄ってりゃそのうち巡り会うこともあろう

>>426が言いたいのはハッシュ関数かと思われ

>>251
過去ログ（1146071975.dat）うｐしたね
http://www.dotup.org/uploda/www.dotup.org553146.dat.html
よかたら見るね

>>226
ホワイトノイズ(一様分布)じゃなくてブルーノイズでも良いなら方法はある。
ブルーノイズはホワイトノイズの低周波成分を除いたもの。

ホワイトノイズではモアレのような模様が見えるがブルーノイズでは模様は見えない。

乱数をjpegなどのデコーダーに食べさせるって言うのはどうだろうか

>>253
頂きました！
どうもありがとう～
俺，週末になったらこれ読むんだ…

試してみたが、VC++2008EE の /O2 でコンパイルした MEXP=216091 の sfmt の gen_rand32() で
1920x1200 を 30 枚埋めるのに、2003年の CPU P4 2.6C で 600ms 弱くらい。
今なら余裕じゃない？

DIEHARDテストはp-valueが一つでも p < .025 or p> .975が
あると失格なのでしょうか？

>>148のは13個あるのに合格って書いてありますけど。
359行 - 0.97978
391行 - 0.01013
533行 - 0.9948
541行 - 0.9988
543行 - 0.9825
569行 - 0.0003
602行 - 0.0243
610行 - 0.9907
612行 - 0.0049
672行 - 0.985720
687行 - 0.007759
692行 - 0.987352
857行 - 0.009586
13個

擬似乱数についてまとめた本とかってあります？

http://sky.geocities.jp/tcshacina/grs.c
作ってみました。

g・r・s！

>>259 ちょっと内容が古いけど「乱数」という本がある。
あと定番としてはTAOCP2巻。

grsって何？

ggrks

乱数生成generalized reed solomon(GRS)
コンパイルしてみてください。あらさがしもOK。

>>265
$ gcc grs.c -o ggg
grs.c: In function `main':
grs.c:614: error: `__m128i' undeclared (first use in this function)
grs.c:614: error: (Each undeclared identifier is reported only once
grs.c:614: error: for each function it appears in.)
grs.c:614: error: syntax error before ')' token
grs.c:615: error: syntax error before ')' token

インデントぐちゃぐちゃだわ、場所によってコーディングスタイル違うわで気持ち悪いソースだな

C:\cygwin>gcc -O2 -ftree-vectorize -ftree-vectorizer-verbose=5 -msse2 -o hash ha
sh.c

C:\cygwin>gcc -O2 -ftree-vectorize -ftree-vectorizer-verbose=5 -msse2 -o grs grs.c

gcc tmp.c -I/usr/local/include -L/usr/local/lib -lgmp -o tmp -O2

著作権の表記無しで使える優秀な疑似乱数生成アルゴリズムある？

アルゴリズムに著作権はないから

つまり、「著作権表記なしで使える実装」のある、「優秀な擬似乱数生成アルゴリズム」を所望しているのかな。
んなもん、自分で実装すれば選び放題だ。

例えばメルセンヌツイスタはBSDライセンスだけど
コードを参考にして自分で実装すればBSDライセンスに従う必要は無いってこと？

パクリ度による

メルセンヌ・ツイスターの性能に勝るとも劣らない優れたもの？?らしい。
ttp://ayusya.hp.infoseek.co.jp/AlgorithmRandom.html

XORSHIFTにちょっと似てる？

いずれにしろ、高次元での相関や周期について、なんの数理的保証もないので
（MTはどちらも数理的に保証している）比較対象になんないよ。
当人は2次元の分布の見た目で評価して同等とか言ってるけど。

ISAAC
ttp://burtleburtle.net/bob/rand/isaacafa.html

WELL
ttp://www.iro.umontreal.ca/~panneton/WELLRNG.html

KISS
ttp://www.math.niu.edu/~rusin/known-math/99/RNG

こんなとこかな。

>>276

最初の
0x65AC9365UL >> ( r & 3 )
とか、シフトの回数の方が動的なのがちょっと新鮮だった。

ちょっと乱数が欲しいというときの物としてなら受け入れられるだろうに、
MTと比較してと書かれるとイタいだけだな。

このアルゴリズムで同一値が2回連続して出現する事なんてあるのか？

0 が出ないんじゃないか

周期が55898とか出てるんだけど、なんか間違ってる？
0x65AC9360ULにしたら長くなったけど…

周期が明示されていない、または、作者もわからないような擬似乱数はゴミだろ。
あと、同じ値が連続して出ないようなものは、いくら一次分布が均一に見えても乱数として使えない。

線形合同法なんか、まさしくその「同じ値が連続して出ない」乱数なんだが。
誕生日検定に通らないわけだけどね。

同じ値が連続して出たらその瞬間から値の変化しない乱数に

ていうか、周期性があるものは、連続して内部的に同じ値(状態)をとるわけがない。
単に、特定の部分(bit)を取り出しているから、その部分では同じ値に見えるというだけ。

線形合同法を使っていても、例えば32bit中14bitを用いるのであれば
同じ値の連続は起こる。

所詮は有限個の整数の集合を同じサイズの整数集合に写像する関数だから、
内部的に2度続けて同じ状態をとるとしたら、その後は永久にその値になるからな。
物理乱数でもなければ窓を使うことで、その精度での乱数性を確保しているというだけだし。

MTはM系列系統だから有限個の整数を一つずつ漏れなくたどり、
一周した場合に一様分布であることはほぼ自明だが、
相関性についてはどうだったろう？
統計的に検定はしてるけど、なにがしかの証明はされてたっけ？

検索してみたら、乱数の誕生日検定について、情報がネットには全く存在してないでやんのw
「誕生日のパラドックス」が乱数列として期待される通りに成り立つかどうかの検定ね。
確かKnuthの本には書いてあった。

別スレで聞いたのですがこちらに誘導されたので質問します。
メルセンヌツイスタを使って0～(n-1)までの乱数を作りたいのですが、
これだとダメって言われたんですがどこを直せばいいのでしょうか。
INT value;
do {value=genrand_int31()%n;}
while(value>=0x0fffffff-value%n);

いろいろひどいからエスパーしていい？

要件：
１．genrand_int31()の剰余をとる
２．分布を完全に均等化するために剰余をとる前の値がNの倍数通りになるように再実行する

んで、

#define INT31_MAX 0x7FFFFFFF // ←ここ重要

int value;
do { value = genrand_int31();
} while (value >= INT31_MAX - (INT31_MAX % n));
value %= n;


MTは下位ビットをとっても安全な疑似乱数だからどっちでもいい

>>291
ありがとうございます。
31ビットは0x0fffffffだと勘違いしてました。

勘違いの問題点はそこじゃないと思うw

もう終わったのかもしれんが
>>291
value = genrand_int31();
これはマイナスの値が返って来る可能性があるから
value = genrand_int31() & 0x7FFFFFFF;
にするべきじゃなかろか

int31なのに負の値が帰ってくるの？

名前で判断してはいけない

MTのソースってこんな感じじゃなかったか？最近読んでないけど。

int genrand_int31() { return genrand_int32() & 0x7FFFFFFF; }

自己解決

/* generates a random number on [0,0x7fffffff]-interval */
long genrand_int31(void)
{
return (long)(genrand_int32()>>1);
}

ほうほう

より厳密に言えば右シフトが論理になるか算術になるかはCの規格上は未定義だったりするのね
unsignedなら論理シフトになるってのはある程度のCPUでは共通してるだけの話

なんてこった

逆だろ。

Cの規格では、
unsignedの右シフト
及び、
signed型であっても保持している値が正である時の右シフト
これはいずれも論理シフトになることが決まってるんじゃなかったか。

規格書落としてきた。
失礼、unsignedの場合は論理シフトで保証されるんだね。

この辺かな
ttp://flash-gordon.me.uk/ansi.c.txt

   The result of E1 >> E2 is E1 right-shifted E2 bit positions.  If E1
has an unsigned type or if E1 has a signed type and a nonnegative
value, the value of the result is the integral part of the quotient of
E1 divided by the quantity, 2 raised to the power E2 .  If E1 has a
signed type and a negative value, the resulting value is
implementation-defined.

よかった、ほっとした

そりゃunsignedなのに上から1が降ってきたら誰だってビビるわ

算術シフトしかないCPUで、シフト演算はのんきに全部その命令を生成しちゃう
コンパイラだってあるかもしれんし、Cの仕様はそれすらimplementation-definedと
言っていそうな雰囲気がある。この場合は違ったわけだが。

たまにはキャリーさんのことも思い出してあげて

キャリーをさがせ

NIST検査について質問です。乱数の統計的性質を調べるソフトなのですが、
このテストをすべて合格しないと乱数とは言えないのでしょうか？
特にFFT検査の場合に不合格になります。周期はないと思うのですが、なぜか
うまくいきません。それとも、これだけは絶対に通らなくてはいけないという
検査があるのでしょうか。どなたかご教示願います。

テストに合格しようがしまいが乱数は乱数じゃね？

二回（以上）続けて同じ数字が出ないものは乱数と呼びたくないな

>>312
>>284-288

疑似乱数に詳しくない俺が言うべきじゃないのかもしれないけど
乱数と疑似乱数を分けて考えてない人が居るような気がするんだ。
乱数、たとえばサイコロとかで作った乱数なら2回以上続けて6が出ることもあるでしょ。
でも線形合同法とかの疑似乱数は、同じ数が2回続けて出ることはないし、
循環しちゃうし乱数とは別物じゃない。だから、疑似と真の区別をはっきりさせないと
話がかみ合わなくなる気がするんだ。

本当にわかってないな

一気に糞スレ化したね。

>>315
何処がどう分かってないのかハッキリさせないと、その発言に意味はないと思いますよ。
意味のない発言の塊が２ｃｈなわけですけど

314は巨大な状態空間の一部だけ切り出してる擬似乱数が想像できないんだろ

>>317
>>313

>>318
そういうのは自分で考えさせないと

>>318、320
よく分からないんですが、疑似と真乱数を分けて考える必要はないということですか？

何故区別する必要があると思ったの？
問題の出てくる例を挙げて欲しい。

えさを与えないでください

>>322
そもそもこの2つは別物なのにその2つを同じ言葉で表すのが気持ち悪いと感じるんですよ。
>>310は疑似乱数のテストについて質問していて、>>311、312は真乱数を前提に
話してるみたいだし、>>313は疑似乱数を前提に発言してる。どうも疑似と真を分けてないから
話が噛合ってないように見えるんですよ

スルーしてください

スレタイも読めないヤツに何かが分かるなんて期待するヤツはいない。

わざと答えをはぐらかしてるみたい

324は正しい

乙です

George Marsaglia (1924 - 2011)
ttp://www.legacy.com/obituaries/tallahassee/obituary.aspx?n=george-marsaglia&pid=148777353

age

乱数で数値nの約数の合計って使えないの？
結構バラバラなんだけど

とりあえず検定の結果を示してもらわんとなんとも。

それで線形合同法の推奨されてるパラメータを越える成績ならともかく。

数値nをどこから持ってくるのか詳しく聞かせてもらおうじゃないか

ぶっちゃけそこはn=n+(秒針)みたいなでいいと思う
あとn/2/(nの約数の合計)なら多分1～0しかでない

RDRANDで疑似乱数ｵﾜﾀ?

>>336
http://software.intel.com/file/36945
>8.6
>RDRAND returns random numbers that are supplied by a cryptographically secure,
>deterministic random bit generator (DRBG). The DRBG is designed to meet the NIST
>SP 800-90 standard. The DRBG is re-seeded frequently from a on-chip non-deterministic
>entropy source to guarantee data returned by RDRAND is statistically
>uniform, non-periodic and non-deterministic.
超訳：
RDRAND 命令は、暗号論的に安全である**決定的な**ランダムビット生成器（DRBG)により供給される乱数を返す。
DRBG は NIST SP 800-90 http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf　に適合するように設計されている。
DRBG はチップに内蔵されている非決定的なエントロピー源により、定期的に初期値を再与されているため、
その結果、RDRAND命令は統計的に均一かつ非周期的、非決定的なデータを生成することが保証されている。

オンチップ-エントロピー源の出来如何に関わるという印象を受けますが、さて、どうでしょうか？

なんで擬似乱数が終わるんだよ？
分からない奴は黙っとけ

容易に再現できる乱数列が必要な応用があるとか全く知らないんだろ

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NUM_THREAD 8
void *th_main(void *arg){
unsigned i, sum = 0;
for(i = 0; i < 1000; i++) sum += rand();
printf("Thread#%d: sum = %u\n", pthread_self(), sum);
}
int main(){
int i;
pthread_t th[NUM_THREAD];
srand(time(NULL));
for(i = 0; i < NUM_THREAD; i++) pthread_create(&th[i], NULL, th_main, NULL);
for(i = 0; i < NUM_THREAD; i++) pthread_join(th[i], NULL);
return 0;
}

rand()ってスレッドごとに独立した系列の乱数列返すの？
既出だったらすいません。
環境はcygwin+gccです。

そもそもrandがスレッドセーフである保証がない。
スレッドセーフでない関数の読み出しにはロックをかけろ。

疑似乱数の実装がスレッドローカルならスレッドIDとタイムスタンプを組み合わせてseedに使うかな

>>340
rand_r()は実装されてないの？
シミュレーションとかに使うなら、当然もっとまともな乱数使うべきなんだけど

randってアルゴリズムからして処理系依存だから
ドキュメント読むしかないと思うが

２０１１年、Ruby,Perl,PHP,Pythonって並べたときにさ
ここで、Ruby以外を選ぶ奴ってマジでなんなんだろうな


ゴミは何いってもゴミ

おや知らないうちに、MTの周期の短い奴が

内部ベクトルぽ周期がxorshift128に似てるね
テストしてみるか

初カキコというか質問があるんですが

うーん…
XorShiftでいいや。

パワフルプロ野球ｽﾚでcupsを256にすれば天才選手(低確率で出る初期能力が強い選手)が出ると聞きました
乱数のことはよくわからないんですがそのcupsという項目があって
それを256に合わせればいいという認識でよろしいんでしょうか

それがあってるとして、
乱数は数値化しないとそれにあわせることはできないのでしょうか
もしくは数字だけが分かっていればなんとかなるものですか？

すいません…ageてしましました…

ゲームの話は板違い

>>351
しゅません、ここしか見つからなくて…

>>348
ttp://raluck.exblog.jp/7153886/

乱数の「精度」って記述初めて見たぞ？言いたいことは判らなくも無いが。

普通、品質って言うわな。

シードとサンプルの長さと、どのような検定で、どういう風に結果が悪いのか、
定量的なことが書いてあれば一読に値すると思うが、これではわけわからん。

ゲームに使うとかいろいろな種を試したとか
乱数の事なんか何にも分かってないんだろう
悪いけどそんな個人ブログなんか読む価値ないよ

つーかウィキペディアのXorShiftの記事にも「精度」って言葉が使ってある。

誰だよほんとにもう。

http://ja.wikipedia.org/w/index.php?title=Xorshift&action=history
> 2011年7月25日 (月) 22:05 MetaNest (会話 | 投稿記録) (1,890バイト)
> (疑似乱数列の評価として「精度」なんて形容を使うのは聞いたことがない)

自分が聞いたことがないから間違っている、
という理由で編集する前に他の記事を確認してください。

http://www.google.co.jp/search?q=%E4%B9%B1%E6%95%B0+%E7%B2%BE%E5%BA%A6+site%3Aja.wikipedia.org
「精度」はどのくらいのビット数で示される範囲で乱数になっているかという意味で使われているようです。
つまり品質の一部分ですね。

それはwikipediaのノート内で議論すべきでは

漏れは精度っていうのは誤差の大小だと思っていた。

一体何の誤差なのか

理想的な分散から外れる誤差というのはあるんじゃね

カ　オ　ス　ラ　ウ　ン　ジ　ゆ　る　せ　な　ぁ　い　ー

the art of computer programinngの２巻の証明の行間が開きすぎだったから
細部まで証明しましたが何か？

頭いいね！

擬似乱数の偏りってビットごとの偏りとか周期性もちゃんと見たほうがいいと思うんだけどねえ。
乱雑性検定の一覧とか出したほうがいいんじゃないの

まさにそれをやってるのがdiehard testsじゃないの

その、「ビットごとの」は「周期性」にもかかってる？

ていうか現代的な生成法で特定のビット位置のみ変な特性があるとかまず考えられないように思うけど。
線形合同法ぐらいだと下の桁はダメダメだが。

>「精度」はどのくらいのビット数で示される範囲で乱数になっているかという意味で使われているようです。
これ、初期値によっちゃ10個ぐらい0が続いてもどうする？

>>367
そうなんだけど>353の人にお勧めしたい。
ちゃんとした統計を取る気があるが知らないだけのようなので。

>>368
両方。ビットの周期性も、全体としての周期性も。
線形合同法を意識して書いたからその通りですね。

> どのくらいのビット数で示される範囲で乱数になっているかという意味

数式で書いてくれ、で終わりだろこんな文

それより問題は>>348がTinyMTを試した結果なぜXorshiftを選択したかだな

内部ベクトルって見て楽しいのかね

見て楽しいかどうかは人それぞれ　4ビットでシフトレジスタ
ttp://upload.wikimedia.org/wikipedia/commons/7/7f/LFSR-F4.GIF

楽しくなければ乱数じゃない！

グレイコードってやつだな。

グレイコードは1度にハミング距離が1しか変化しないコードだろ

なんだ・・・ただ１づつ足していくだけかクダラネ。

ハミング距離も知らんのか

すごいすごいすごい
ハミング距離を知っているなんて凄いねーー
エライネー
天才だね～

いやあそれほどでも(ｸｨｯ!

復帰

擬似乱数ではないのでスレ違いかもしれないが
ちょっとコンセプトを思いついたので実装してみた。
http://netrand-test.appspot.com/

何に使うんだそれは

/dev/random のような用途？

なんか加減算だけでそれっぽいのができたぜ

http://www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=mon13.html

>>386
SFMTに対して、どこがアドバンテージあるの？
周期2^216091-1とかだぞ。

出力範囲が1000（10ビット未満）というのもな
32ビット精度必要なら4個を組にして使うわけだが，その上での一様性も相当疑わしい

出現回数をカウントできるようにしたぜ

お知識拝借
次のような擬似乱数生成方法を探しております
シード（頻繁には変化しない入力値）のほかにいくつかの入力値（頻繁に変化、1,2,3など近い値が入力される）
があって、それら入力値を入れると必ず決まった擬似乱数を生成する、というような乱数生成方法
当初XorShiftをアレンジすれば出来ると思ったのですが、シード以外の入力値が近いと
結果返ってくる値も近いようなものしか出来ず使えませんでした。
こういったタイプの擬似乱数関数として良好なものはありますでしょうか
もしくはどういった風にXorShiftを改造すればこういったものが実現できそうでしょうか
乱文失礼、お力添えお願い申し上げます

要するにハッシュ関数的な要素が欲しいんでしょ
入力値のハミング距離が近くても出力値のハミング距離が遠くなるように
ハッシュ関数通せばいいよ

ハッシュ関数、初耳ですがちょっと調べてみます

毎回srandしてるようにも読めるな
そうでないなら適当に読み捨てれば？

>>390
どれぐらい「近いようなもの」でなければよいのか、
はっきりしてもらわないと何ともならんのじゃないか？

ハッシュ関数知らないレベルだから改善の余地は大いにありそうだが

>>393
お恥ずかしながらおそらくそれをしていました

>>394
32bitですねfloat精度程度

入力値もfloat3つ程度、シェーダーでノイズを作るような目的です
だから欲しいのは
ulong32 Noise(ulong32 x,ulong32 y,ulong32 z,ulong32 seed)
で当初XorShiftの４つにこれを当てはめて数回振っていましたが
どうも模様が見えてしまう結果になります

ハミング距離が遠くなるようなハッシュ関数考えてみます

典型的にはZobrist Hashingが使える

他の人たちは 390 が何をしたいか分かったの？
もっとちゃんと問題を定義したらズバリの答えが出る気がするけど。

>>396
余計なお世話かもしれないが、単精度浮動小数点数の乱数を作るのは
(rand() & 0x7fffff) | 0x3f800000
として [1.0 .. 2.0) を作り、必要に応じて線形変換するのが常道。
バイアス部分にも乱数のビットを埋めるのは好ましくない。
で、もし本当に 32bits 必要なら、単精度じゃなくて倍精度を選ぶべきかもしれない。

> どうも模様が見えてしまう結果になります
これが周期の問題なのだとしたら、余計なことしないで単にメルセンヌツイスターを使うだけの方が乱数性も処理速度も好ましいものになるだろう。

>>396
低周波成分(いわゆる模様)の無いノイズが欲しいなら
それは乱数ではなく、乱数から低周波成分を除く加工をして作る数列
ブルーノイズとか

>>398
>(rand() & 0x7fffff) | 0x3f800000
>として [1.0 .. 2.0) を作り、必要に応じて線形変換するのが常道。
これは知らなかった。
rand() / (RAND_MAX_1)とばかり。

fmul一回分だけお得と
まあ大抵は再度後から掛けるだろうけど

9bit損するからじゃね？

音のノイズなら線形合同のほうがいいよ
偏りや周期を聞き分ける人がいたら神だよ

上位ビット使うんだぞ

気をつけます。

>>403
ダイナミックレンジ広いと偏りはわからんが、周期は聞こえるぞ

線形合同法でノイズ作ったぜ

http://www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=oto2.html

もうJKISS32でいいんじゃないか。周期も2^121くらいあるみたいだし。
http://www.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf

/* Implementation of a 32-bit KISS generator which uses no multiply instructions */
static unsigned int x=123456789,y=234567891,z=345678912,w=456789123,c=0;
unsigned int JKISS32()
{
int t;
y ^= (y<<5); y ^= (y>>7); y ^= (y<<22);
t = z+w+c; z = w; c = t < 0; w = t&2147483647;
x += 1411392427;
return x + y + w;
}

129ビットぶんの状態があるように見えるけど周期は2^121なのか
加算の使い方がまたなんとも

L・C・G！L・C・G！

wikipediaにある
'特定の範囲で乱数を求めたいときにはa = rand() % 10とする方法も広く知られているが、線形合同法などの下位ビットの乱数としての品質が低い生成法に備えるため上記のコード例のような上位にあるビットを利用するコードが推奨されている'
ってどいういうこと?
(int)((rand() / ((double)RAND_MAX+1.0)) * 2);
と
rand()%2
で1000000回、乱数を生成して比較してみたけど、平均値と0.5の差はどちらもオーダー的にほとんど変わらないのだけど、

面倒だから
乱数 下位ビット
でググってもらっていいかな。

>>411
品質が悪いと、奇数偶数が交互にしか出なかったりする。

>>412

よく分からなかったけど、メルセンヌツイスターとかでも%で余りを求めるやり方はいけないの?
それとも線形合同法に限った問題なん?

MTはかまわないよ
だめなのは質の悪い乱数に限った話
線形合同法はその代表格

%は法の数が大きいと分布の偏りが大きくなる。

>>411
酷い実験してるなw
頼むからブログとかでどっちも変わりませんでしたとか書かないでくれよww

>>416
それって RAND_MAX が 16 だとして、rnd % 10 とかで計算したら、って話？
そりゃ普通は、はみ出る部分の値が出たら捨てるだろ。

>>418
普通の知能の持ち主が剰余を使うならそうだが、剰余を使うほとんどの連中はそんなことはしないだろう

法（のり）

>>414
今は線形合同法といっても、計算で仕様するビット全部ではなく、上位の一部を表に返す、とかするものもあるようだ。
http://en.wikipedia.org/wiki/Linear_congruential_generator

線形合同法は比較的単純な弱点が多いから、使う側が完全に把握して使うべきであって、
ライブラリ側でそういう配慮をするのはよくない（そういう配慮をして、ブラックボックス的に
使わせるなら他の生成法にすべき）。

久々に見たらスレが進んでいるなと思ったら

>>411
＞ 1000000回、乱数を生成して比較してみたけど、平均値と0.5の差はどちらもオーダー的にほとんど変わらないのだけど
これは本当にひどい
高校生でさえ鋭い奴は問題に気が付くレベル

>>413
それを定量的に調べる方法はありますか?

>>424
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

メルセンヌ・ツイスタでseedはどうやって与えれば良いの?

初期化関数の引数にシードを与えればいいよ。

それやってみたのですが、最初の方は似たような数字になってしまいます。

内部状態が2kバイト強あるから、先頭から4kバイト弱ぶんぐらい読み飛ばす。

あと、十分な量のseedを与えることができるインタフェースが用意されてないか、確認する。

>>428
それ、小さいシードで初期化するときの実装が古いやつなんじゃないか？

何万個か読み捨てればいいよ。

Perlでメルセンヌツイスタをつかえますか？

うん

rand(0)とrand(1)どちらも同じ乱数列を生成するのですが、
そのように決まっているのですか?
それともたまたま使っている処理系が、0と1で同じ乱数列を吐き出すのですか?

rand()って引数いらんのでは？
説明めんどいからsrandも調べてみ
色々わかるから

ちなみにrand()は精度低い乱数

>>434
お使いの処理系のマニュアルをご覧ください。

つーか、言語も何も判らんのに答えられるわけないとは思わないもんなのだろうか。

回答もランダムです

MATLABやRならrandはメルセンヌツイスタになってるよw

>>429だな。
少なくともオフィシャルの実装には配列でシードを与える関数がある。

static uint64_t x = seed;
x ^= x << 21;
x ^= x >> 35;
x ^= x << 4;
return (uint32_t)x; // doesnt pass

そのまま返しちゃだめです

Kiss99ってのがあるのをここで見て調べたら、L'Ecuyerがそう呼んだだけだった。
つまり、Marsagliaが1999年にユースネットへ投稿した有名な「挑戦状」、
　'Random numbers for C: End, at last?'
で紹介されていた'KISS(Keep It Simple Stupid)'のことだった(笑)。

monoが

fortranでのSFMTの最速実装っていまどんなのあるの?

A simple demonstration of twenty Pseudo Random Number Generators
www.dotup.org/uploda/www.dotup.org4761462.zip.html
Have fun with it !

擬似乱数が真の乱数に近づく条件は周期を無限大にすること、
周期が長いとどういうことが起きるか？
数値の分布が極所で揺らぎ（歪む）出すってこと

質の良い擬似乱数は使う範囲において一様性の分布が求められる
例えば１から６までのサイコロを演出したとき１万回振って
どの目もほぼ同じ確率になること。

これが1京の1京乗回となる場合に1万回部分の区切りの中が同じ一様性
であるかは別の話しとなる。1京の1京乗回行えば1万回分サイコロを振った
分布より確実にどの目も同じになるわけで、どの側面で優秀かは別の話しである。

暗号のソースである良い擬似乱数とは予測困難性の高いことである、
それは一様性が確実であれば1万回振ったとき最後の1回は高い確率で
予測できてしまう。それはその周期でどの目も一様に分布するから
その性質を維持する為に1万回目は過去のデータから特定できる
ってことである。

計算で求められる擬似乱数に秩序などないと考えるバカがいるが
擬似乱数を求める式でその擬似乱数を割り切れるという秩序がある。
同じ計算が同じ結果を出すのは当たり前すぎる。
方法が統一されているそれは次の値がでるパターンが前の目で確定している
性質があるってことだ。その連続性が膨大であるから困難だと説明している
のにすぎない。
だが桁数が小さいその擬似乱数が困難だというのは過去の話しである。
いつまで困難だと思っているか、バカには理解できない領域である。

どうしたんだ？

誰と戦ってるんだ。ところでフリーの乱数の性能評価ツールない？

diehard

>>446 447 はただのバカ。「疑似乱数列」「暗号学的に安全」「真の乱数」といった言葉を、
まるっきり俺様定義で使ってるから、全くの意味不明なナンセンス文になっている。

>>450
thx!

>>449
おまえ馬鹿だろ、そんなの自分で作れずどうするの？
目的によって違うんだから(ry

過去数十年にわたって、数多くの研究者が乱数列の様々な評価法を考えてきたというのに、
それら全てを無視して、俺の能力ならすばらしい評価関数が作れる、ってか？　すごい自信だな。

（普通、そういうのを「バカ」と言う）

>>451
人格障害じゃね？貴方

>>454

数学を知らずに数学を知ったかのように語るやつっているけど、
たんなる感情論だよね、観念の類を定義して方程式で証明する構図は
まったく具体性のない幻想とまで皮肉をいったり悪口を言う輩がいるが
それは間違いない、幻想でいいんだよ。
方程式そのものは美しさとその完璧なる秩序の明確性を説明するもので
現実を表す物理のような実証ではない、証明と実証の区別ができないのが
実証（具体性）ばかりこのみ難しい数学の領域の記号だけの記述になると
３行しか読めないコピーペーの能力ではどうにもならない。
暗記してできるものでもない。

方程式や論理式に現実性がない、だと？

じゃあ、方程式や論理式を駆使して設計されている飛行機やコンピュータはいったいどうなるんだ。
飛行機やコンピュータは幻想なのか？

あんな重い鉄の塊が飛ぶわけないだろ

飛行機は鉄の塊ってほど密じゃないけどね。
そもそも軽金属か樹脂がメインだし。

鉄の塊は、レシプロ機のエンジンぐらいだな。高機能樹脂ができる前は軽合金、その前は木と布だったw
「機」（本来は、織機のように木などで出来た、軽いものを指す語）を使うのは伊達じゃない。

最近は炭素素材も使われるようになったねぇ

7年も前のスレを読み返すと時代の変遷を実感できる。
>>226や>>390の質問は最近の並列化乱数の流れに繋がる。
ここ2、3年の展開では、
Parallel random numbers: as easy as 1, 2, 3
//www.thesalmons.org/john/random123/papers/random123sc11.pdf
Deterministic parallel random-number generation for dynamic-multithreading platforms
//supertech.csail.mit.edu/papers/dprng.pdf
今、メニーコアのCPUで動的負荷分散したいと皆考えてる。
近々MT以来のブレークスルーがあるような気がするな、、

ラン　スー　とくれば最後はもちろん　ミキ

電線に

一様な分布である乱数（「一様分布に従う乱数」）どうしの和は、一様な分布にならない。


一様乱数の和の確率分布は、個数 n が増えるにつれて急速に正規分布に近づく（「正規分布に従う」）

2個の和
12個の和

図 5-1　Monte-Carlo実験による[0,1)一様乱数の和の分布
2個の和（左）12個の和（右）
http://econom01.cc.sophia.ac.jp/sda/normal.htm

中心極限定理ですねえ

不思議だよね

不思議なの？
結果の数値を表す組み合わせの存在ってだけだと思うんだけど

一様乱数ですら足して足してでガウス分布に近づいていく、というのだからねえ‥‥手元の教科書は証明抜きだ‥‥凡人には理解できない世界なのか？

ごく単純に 2D6 とか 3D6 を....6面のサイコロを2個とか3個とか振って、出た目の合計とか、
考えてみればいいじゃないか。

>>471
それは「二項分布はガウス分布に近づく」ってやつだね，でもその証明も手元にないな‥

メルセンヌツイスタが最強