2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

疑似乱数2

1 :デフォルトの名無しさん:2007/10/17(水) 22:34:59
擬似乱数発生器について語ろうか。その2

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


2 :デフォルトの名無しさん:2007/10/17(水) 22:53:56
で、いつになったらSFMTはboostに組み込まれるの?

3 :デフォルトの名無しさん: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)) );
}


4 :デフォルトの名無しさん:2007/10/17(水) 23:35:36
>>3
せっかくだからURLも貼っとこう
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub218.html

5 :デフォルトの名無しさん:2007/10/17(水) 23:38:04
この手の乱数マジックナンバーでよくでてくる
123456789
なにふざけてるのかと思ってたら、
0.1234567891011121314… って超越数なんだな。
つまり123456789は、その超越数を10億倍して9桁の精度で切り落とした、
そこそこ質のよい数なのであった。
目からウロコ

6 :ヽ・´∀`・,,)っ━━━━━━┓:2007/10/18(木) 00:42:09
マジックナンバーに0xDEADBEEFってよく見る

7 :デフォルトの名無しさん:2007/10/18(木) 01:51:23
SFMTはCPUの機能に最適化させてるメルセンヌツイスタですよね?
boostはテンプレートライブラリだからそれはいつまでたっても組み込まれないと自分は思います…。



8 :デフォルトの名無しさん:2007/10/18(木) 08:32:57
>>7意味不明

9 :7:2007/10/18(木) 10:16:21
C++のテンプレートライブラリとして実装するものなのかなと思っただけです。


10 :デフォルトの名無しさん:2007/10/18(木) 12:38:11
独自の乱数発生器を組み込めるのがboost::randomのよいところ。
手直しは必要だが。

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

11 :7=9:2007/10/18(木) 14:19:16
実際違いました…すみません。
boostの一部がSTLに移植されるとか書いてあったの見てたから勘違いかな…。
regexとかはテンプレートライブラリではなかったです。

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


12 :デフォルトの名無しさん:2007/10/18(木) 19:08:52
RandomはTR1に入った、つまり標準ライブラリ入り内定ではある。

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

13 :ヽ・´∀`・,,)っ━━━━━━┓:2007/10/19(金) 00:54:05
regexがプリコンパイル方式なのは型が最初から決まってるからじゃん。

14 :デフォルトの名無しさん: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

15 :デフォルトの名無しさん:2007/10/19(金) 12:51:57
Boost はほとんどテンプレートだけど、
たまにテンプレートじゃないのがあるからな。

16 :デフォルトの名無しさん:2007/10/23(火) 01:38:55
http://www.nicovideo.jp/watch/sm1331242
歌詞を乱数で生成した歌

17 :デフォルトの名無しさん:2007/10/23(火) 04:40:30
(ax+b) mod M でいいよ…

18 :デフォルトの名無しさん:2007/10/23(火) 05:09:13
MT使え。
いじょ。
終了。

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

20 :デフォルトの名無しさん:2007/10/25(木) 23:12:25
初心者ですみません。

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

21 :デフォルトの名無しさん:2007/10/25(木) 23:15:18
COBOLで頑張ってもいいとはおもうけど(どっかに実装があるかもしれないけど)、
処理系の、Cの関数を呼び出す機能の利用を検討するのもありと思う

22 :デフォルトの名無しさん:2007/10/25(木) 23:27:05
>>21
ああ、おっしゃる通りですね。Cならすでにソースあるんだし。
その方向で検討します。ありがとうございました。

23 :デフォルトの名無しさん:2007/10/27(土) 11:24:36
COBOLで乱数が必要なのか?

24 :デフォルトの名無しさん:2007/10/27(土) 12:14:41
使えないとちょっとCOBOL

25 :デフォルトの名無しさん:2007/10/27(土) 19:27:33
コボルと困るを掛けた駄洒落か。なるほど。次の宴会で使おう。

26 :デフォルトの名無しさん:2007/10/28(日) 09:43:23
昔COBOLでなんちゃって正規分布乱数を作ったな

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

27 :デフォルトの名無しさん:2007/10/28(日) 19:36:32
>>25
きっと誰かのビールがCOBOLる

28 :デフォルトの名無しさん:2007/10/28(日) 19:49:41
それは、すCOBOL、きついな。

29 :デフォルトの名無しさん:2007/10/29(月) 00:13:57
XorShiftのk=128では無いバージョン(32,64,96,160,192)について
誰か擬似コードor参考になるURL希望。

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

30 :デフォルトの名無しさん:2007/11/01(木) 01:20:36
>>29
ttp://www.jstatsoft.org/v08/i14/
ttp://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf

31 :デフォルトの名無しさん: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列の長さ定義



32 :デフォルトの名無しさん: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/

33 :デフォルトの名無しさん:2007/11/03(土) 03:37:01
>>31
rand()は乱数としての性質があまりよろしくないという
当たり前のことを文句言われてもどうかと。

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

> rand()%0xffff

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

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

35 :デフォルトの名無しさん:2007/11/03(土) 17:26:32
そんなのどうでもいいじゃん
だからまあ普通はラッパーかけて開発中はrand使って
あとで精度ほしくなったら差し替えるように作るわけだが

36 :31:2007/11/03(土) 23:00:03
>>33-35
早速の返答ありがとうございます。
色々とマヌケな勘違いをしていましたorz

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

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

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

37 :デフォルトの名無しさん:2007/11/04(日) 05:32:17
>>36
実行はできてるんだね。
オレの環境だと>>31-32のコードは動かないんだけど。
# 原因はスタックに置くには配列サイズがでかすぎることみたいだけど。

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

38 :デフォルトの名無しさん:2007/11/05(月) 02:14:18
RAND__MAXと0xffffってどっちが大きいか知ってる?

39 :デフォルトの名無しさん:2007/11/10(土) 21:14:12
RAND_MAXの値は実装にもよるかと。

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

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

41 :デフォルトの名無しさん:2007/11/10(土) 21:39:02
そんなことよりxorshiftの話しよーぜ

42 :デフォルトの名無しさん: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;}
こんな具合か

43 :42:2007/11/11(日) 19:16:33
コピペ丸張りで色々とおかしくなってることに気付く。
後悔はしていない。

44 :デフォルトの名無しさん:2007/11/11(日) 20:03:25
>>40
意味とランダム度が全然違うだろ。

45 :デフォルトの名無しさん:2007/11/11(日) 20:05:36
>>42
これってsrand()に相当する関数は自作しなきゃいかんよね?

46 :デフォルトの名無しさん:2007/11/13(火) 04:38:48
>>45
srand_xor(int hoge)
{
extern static int x;
x=hoge;
}
これでいいんとちゃう?ん?staticはexternできなかったっけ?

47 :デフォルトの名無しさん:2007/11/13(火) 08:50:49
>>46
アホかい。

48 :デフォルトの名無しさん:2007/11/13(火) 17:51:10
分からなかったらとりあえずクラス化→private属性のクラス内変数で(ry

49 :デフォルトの名無しさん:2007/11/16(金) 23:27:42
あるシードを使うと、得られる乱数を繋げたバイナリが
偶然たまたま 迷走Mind.mp3 として読めるような
乱数ジェネレータを作ったら どうだろうか。

50 :デフォルトの名無しさん:2007/11/16(金) 23:44:09
確率的にありえない

51 :デフォルトの名無しさん:2007/11/17(土) 00:09:54
意図的に作るんなら偶然じゃないな

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

53 :デフォルトの名無しさん:2007/11/17(土) 05:19:51
>>42 には間違いがあるので注意

54 :デフォルトの名無しさん:2007/11/17(土) 05:24:13
訂正したコードを示した方が有用なレスになると思うよ。

55 :デフォルトの名無しさん: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) とすべき


56 :デフォルトの名無しさん:2008/01/06(日) 13:04:45
XORってライブラリ化してないの?

57 :ヽ・´∀`・,,)っ━━━━━━┓:2008/01/07(月) 00:17:55
めぼしいのはBoost.Randomにある

58 :デフォルトの名無しさん:2008/01/07(月) 12:16:11
団子あげ

59 :デフォルトの名無しさん: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


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


61 :ヽ・´∀`・,,)っ━━━━━━┓:2008/01/14(月) 01:28:22
SFMTのスレッドセーフ実装なら京大の人のページにあったぞ。SSE2だけだけど。

62 :デフォルトの名無しさん:2008/01/14(月) 01:48:05
XorShiftをseed使えるようにする場合、どうすればいいかな?<何度もブン回す以外で

63 :デフォルトの名無しさん:2008/01/14(月) 04:04:29
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/random.html

64 :デフォルトの名無しさん:2008/01/14(月) 17:24:18
>>63
thx

65 :デフォルトの名無しさん:2008/01/14(月) 21:52:52
/* 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);}


66 :デフォルトの名無しさん:2008/01/14(月) 22:04:20
32 行書けるんだからもうちょっと綺麗におながいします

67 :デフォルトの名無しさん:2008/01/14(月) 23:52:54
上のほうでrand()をダイハードに食わせるとかいってた人がいたのでオチを教えておきます。
p=1.0頻発します。テストの種類によっては部分がすべてp=1.0 あわせてp=1.0みたいな。

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


68 :デフォルトの名無しさん:2008/01/15(火) 00:53:58
>>65
こりゃ無茶だろ.こういう使い方は...
別の種の乱数を4個同時に生成するのが正解

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

70 :デフォルトの名無しさん:2008/01/15(火) 18:39:47
>>69
初期値ってあの値じゃなくても良かったのね。
乱数の質がどの程度変わるのかが気になるが

71 :デフォルトの名無しさん:2008/01/15(火) 19:28:29
やっつけでtimeの値入れたり

72 :デフォルトの名無しさん:2008/01/15(火) 19:41:19
SEED値を入れるならxよりwの方がいい気がする

73 :デフォルトの名無しさん:2008/01/15(火) 20:24:10
/* >>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 ); }


74 :デフォルトの名無しさん:2008/01/15(火) 21:20:55
>>73
その種の使い方、MTと全く同じだな

75 :デフォルトの名無しさん:2008/01/17(木) 22:51:40
XorShiftの正しいシードの設定方法を教えてくれ!

76 :デフォルトの名無しさん:2008/01/26(土) 18:55:32
論文の6ページ目に xor128 の seed set は全て0の場合を除いて、どの
ように設定してもよいと書いてある。しかし、極端な設定をすると不自然
な部分列が出力される。そこで初期化の方法はMTを参考にした。iを0
からではなく1から始めた理由は0を種にしたときに最初の2つの出力が
似た値にならないようにするためである。配列を使っているが、スピード
はオリジナルとほとんど変わらない。コンパイラによっては、こちらの方
が速くなる場合もある。デフォルトの初期ベクトルは rand,srand になら
って種を1としたときと同じである。

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


77 :デフォルトの名無しさん:2008/01/29(火) 19:35:39
なるほど、どんな初期値であっても、2^128-1のどこかの部分列になってるのか

78 :デフォルトの名無しさん:2008/01/29(火) 23:17:42
>>61について誰か詳しく頼む

79 :デフォルトの名無しさん:2008/01/31(木) 21:25:58
ん? 何が分からなかった?

80 :デフォルトの名無しさん:2008/01/31(木) 21:44:19
遅いんだよ
もういい

81 :デフォルトの名無しさん:2008/01/31(木) 23:24:35
はやっ

82 :デフォルトの名無しさん:2008/01/31(木) 23:53:55
こんな過疎スレで遅い言われても

83 :デフォルトの名無しさん:2008/01/31(木) 23:59:56
自分がいくら張り付いてるからって、ね。

84 :78:2008/02/02(土) 06:55:22
>>61のソースの所在教えてくれ
パクる

85 :ヽ・´∀`・,,)っ━━━━━━┓:2008/02/02(土) 07:20:15
dSFMTだったごめん。
http://nct.brain.riken.jp/~takekawa/softwares.xhtml


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



86 :デフォルトの名無しさん:2008/02/03(日) 13:34:07
thx

87 :デフォルトの名無しさん:2008/02/03(日) 13:46:53
ダンゴさんはSSEネタには造詣が深いな。

88 :デフォルトの名無しさん:2008/02/03(日) 16:46:36
じゃあ上げとこ

89 :デフォルトの名無しさん:2008/02/22(金) 20:01:38
シミュ板、数学板に乱数スレ発見。
乱数
http://science6.2ch.net/test/read.cgi/sim/1100375806/
乱数の生成方法を必死になって考えるスレ 
http://science6.2ch.net/test/read.cgi/math/1203153071/

90 :デフォルトの名無しさん:2008/03/23(日) 01:46:24
あげ

91 :デフォルトの名無しさん:2008/03/27(木) 23:56:06
XORSHIFTって、その出力の剰余を取った場合も
良質なランダム性があるって言われているのでしょうか?

92 :デフォルトの名無しさん:2008/03/28(金) 00:05:34
XORSHIFTは良質ではないと思います

93 :デフォルトの名無しさん:2008/03/28(金) 00:06:25

工工エエエエエ(´Д`)エエエエエ工工

94 :デフォルトの名無しさん:2008/03/28(金) 00:11:48
MTが一番良質と思います XORは速度は速いです 用途によっては十分です

95 :デフォルトの名無しさん:2008/03/28(金) 00:20:58
>>91です。
XORSHIFTで剰余を取った時の結果を載せてる
WEBページを見た気がするのですが、結果が
今一だったような記憶が・・・

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

96 :デフォルトの名無しさん:2008/03/28(金) 03:02:22
>>95
そのWEBページのURL教えてくれ

97 :95:2008/03/28(金) 23:26:21
>>96
個人のブログですが、確かここだったと思います。
ttp://d.hatena.ne.jp/Isoparametric/20070830/1188462129

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

98 :デフォルトの名無しさん:2008/03/28(金) 23:55:04
たった100回回しただけなら偏りも出るだろう

99 :デフォルトの名無しさん:2008/04/15(火) 04:27:31
はぐれめたるは捕まえられますか?

100 :デフォルトの名無しさん:2008/04/17(木) 03:21:30
>>99
むり

101 :デフォルトの名無しさん:2008/04/20(日) 18:00:50
単純に何の補正も無い相手に対して「捕まえられる」確率はどのくらいか。
そしてはぐれメタルが逃げない確率はどのくらいか。
その両方のデータをくれ。

102 :デフォルトの名無しさん:2008/04/20(日) 19:05:05
乱数とどういう関係があるんだ

103 :デフォルトの名無しさん:2008/04/20(日) 23:27:07
え?はぐれメタルの行動を決めている乱数テーブルの解析の話じゃないの!?

104 :デフォルトの名無しさん:2008/04/21(月) 00:54:50
ここは「擬似乱数生成アルゴリズム」に関する議論のスレッドだ

105 :ヽ・´∀`・,,)っ━━━━━━┓:2008/04/21(月) 13:20:43
PS2のドラクエ5では壁の衝突回数をカウントして乱数列の初期化してるようだ。
オラクルベリーの教会から一度も壁に衝突せずにカジノのスロットに直行すると
全く同じパターンが出てくるとか。

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

106 :デフォルトの名無しさん:2008/04/23(水) 08:14:14
全然ちげーよ、ばかが

107 :デフォルトの名無しさん:2008/04/23(水) 12:16:04
「ヽ・´∀`・,,)っ━━━━━━┓」は放置推奨クソコテ

108 :デフォルトの名無しさん:2008/05/01(木) 23:36:04
英語版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;
}

109 :デフォルトの名無しさん:2008/05/03(土) 21:01:47
>>105
http://www.astr.tohoku.ac.jp/~ajiki/cheap_restaurant/GAME/SAGA2/saga2rand.html
サガ2の乱数発生器

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

110 :デフォルトの名無しさん:2008/05/18(日) 22:07:45
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

111 :デフォルトの名無しさん:2008/05/19(月) 09:17:00
まとめ乙

112 :デフォルトの名無しさん:2008/08/06(水) 01:14:02
保守

113 :デフォルトの名無しさん:2008/08/09(土) 20:00:17
M系列という単語を見かけたので、理解してないまま保守リンク
http://pc11.2ch.net/test/read.cgi/tech/1158367586/751-

114 :デフォルトの名無しさん:2008/08/11(月) 14:05:33
VBAで、dll使わずに高機能な乱数を実装する方法はないですか?
XorShiftを使うには、長桁計算しかないですか?

115 :デフォルトの名無しさん:2008/08/13(水) 17:47:46
' 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


116 :115:2008/08/13(水) 18:47:55
' 書き込んだ後、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


117 :デフォルトの名無しさん:2008/08/18(月) 18:18:26
>>116
114です、ありがとうございます。32bitのXorShiftですね。

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


118 :デフォルトの名無しさん:2008/08/19(火) 00:23:17
>>75あたりか

119 :115:2008/08/22(金) 21:40:15
'種を使って初期化できます。116よりさらに2倍程度高速になりました
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


120 :デフォルトの名無しさん:2008/08/22(金) 23:22:43
xorshiftって周期とか分布の保証ってあるの?
もしないならM系列の方がましだと思うんだけど。
ググれば長周期の多項式も見つかるし。

121 :デフォルトの名無しさん:2008/08/23(土) 01:50:28
劣化M系列と理解してるが

122 :デフォルトの名無しさん:2008/08/23(土) 02:50:13
早くて軽くてrandよりマシ

123 :デフォルトの名無しさん:2008/08/25(月) 16:31:11
>>119
excelVBAじゃ初期化するための種が結局16bitしかないんだから
Xorshiftの種も16bit種類しかなくならね?

124 :119:2008/08/27(水) 03:32:41
種 s は Long なので32bit種類あるが、負の場合は試してないので実質31bit種類。

125 :デフォルトの名無しさん:2008/08/27(水) 10:43:09
VBAのRandomizeが16bit種類
それを使って初期化後rnd()で取得できる乱数も16bit種類
XorShiftの種にそれらを使うのなら結局系列は16bit種類

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

126 :デフォルトの名無しさん:2008/08/27(水) 10:56:10
よく分からんが服を買いにいく服がない状態か

127 :119:2008/08/27(水) 14:14:51
>>125

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

128 :デフォルトの名無しさん:2008/08/27(水) 14:18:21
>>125
GetTickCountとかCryptGenRandomとかWin32APIに頼ればいいじゃない。

129 :デフォルトの名無しさん:2008/08/29(金) 12:44:39
>>128
とりあえず
Private Declare Function GetTickCount Lib "kernel32" () As Long
後に
  GetTickCountを使って取得するようにしたよ。

130 :,,・´∀`・,,)っ-○●◎:2008/09/15(月) 02:50:11
暇だったからSFMTのC++ template実装やってみた
http://tripper.kousaku.in/20080914.html

131 :デフォルトの名無しさん:2008/09/15(月) 11:02:02
GJ!
前スレからずっと待ってました

132 :デフォルトの名無しさん:2008/09/15(月) 11:05:17
あ、なんだ
TR1対応じゃなくて純粋にテンプレート版なのか

133 :,,・´∀`・,,)っ:2008/09/15(月) 14:24:14
そのうちBoost風に作り替える予定

134 :デフォルトの名無しさん:2008/09/16(火) 23:55:19
乱数って巻き戻しできないの?


135 :デフォルトの名無しさん:2008/09/17(水) 10:24:14
>>134
乱数の巻き戻しって何?

136 :デフォルトの名無しさん:2008/09/17(水) 12:00:52
予想すると
あるシードでのn番めの乱数を出したあとに、n-1番目の乱数を
定数時でだせないか?
ってことでは

137 :デフォルトの名無しさん:2008/09/17(水) 12:01:59
>>136
そのとおりでございやす


138 :デフォルトの名無しさん:2008/09/17(水) 12:09:45
n-1番めからn番めを求める計算がたいてい非可逆だから無理

139 :デフォルトの名無しさん:2008/09/17(水) 12:59:05
巻き戻す必要がある数分だけ乱数の結果を保存するしかないだろうなぁ

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

141 :デフォルトの名無しさん:2008/09/17(水) 21:13:31
これって読み捨てるのと比べてどのぐらい高速?
MTの先頭の何百万個か読み捨てる処理に使えそう?

142 :デフォルトの名無しさん:2008/09/17(水) 21:22:53
何百万よりは速いだろうが、100程度なら大差ない。

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

143 :デフォルトの名無しさん:2008/09/25(木) 17:39:27
flashのActionScriptの乱数Math.randomって何bit?

144 :デフォルトの名無しさん:2008/09/25(木) 22:19:58
25くらい

145 :デフォルトの名無しさん:2008/09/29(月) 11:00:47
MTならFORTRANだけど
ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/FORTRAN/fortran.html
この中に
revrand(): it generates prn in reverse order
って書いてあるけど

146 :デフォルトの名無しさん:2008/10/05(日) 13:52:49
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;
}


147 :デフォルトの名無しさん:2008/10/22(水) 21:18:38
とつげき東北とかいう人の乱数生成法を見て思いついたけど
メモリを確保して、読み書きする速度を計測すれば真の乱数できそう。
もともとはハードディスクの読み書きだが。これだと生成に時間食う。

148 :デフォルトの名無しさん:2008/10/22(水) 21:20:08
これね。

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

149 :デフォルトの名無しさん:2008/10/22(水) 21:24:52
でもメモリが余ってるときに均一に分布したとしても一杯になったら悪くなるかも試練ね

150 :デフォルトの名無しさん:2008/10/22(水) 21:30:57
>>147
時には極端に偏ってくれないと真の乱数とはいえないな。


151 :デフォルトの名無しさん:2008/10/22(水) 21:39:34
Unix の /dev/random は、デバイスドライバからそういう真の乱数を
生成するようなタイミングの情報をもらってデータを生成しているのだが...

152 :デフォルトの名無しさん:2008/10/22(水) 21:41:38
実行時まで偏ってるかどうかすら分からんから実用的には疑問だけどな。
違うハードの組み合わせで似たようなシードが繰り返し出てしまう可能性も否定出来ん。
特性が誰にも分からんから乱数としてもいいだろうって発想は学問的ではないな。


153 :デフォルトの名無しさん:2008/10/22(水) 21:45:17
元手にするだけで、そのまま使うはず無いだろ。
たとえば、メモリ確保と読み書きした間隔が
1ナノ秒から100ナノ秒に分布しても偏りはでる。
そこは適切に処理して良い具合にする

154 :デフォルトの名無しさん:2008/10/23(木) 00:39:08
メモリの読み書きレイテンシがどういう条件で決まるかわかって言ってるか?


155 :デフォルトの名無しさん:2008/11/03(月) 16:36:49
srand(0)とsrand(1)はその処理系でも同じ系列を生成するのですか?

156 :デフォルトの名無しさん:2008/11/03(月) 17:29:47
その処理系て?

157 :デフォルトの名無しさん:2008/11/03(月) 17:45:50
なんだろね?

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

158 :155:2008/11/03(月) 17:52:33
まちがえました。
「その処理系でも」→「他の処理系でも」
でした。


159 :デフォルトの名無しさん:2008/11/03(月) 17:59:04
srandはアルゴリズムからしてライブラリの実装次第だから
処理系以前に互換性はないと思え。
そもそもrand自体0からRAND_MAXまでの整数を出力するとかそういう定義しかないはず。
確かMTはその辺しっかりしていて、どこでも同じ結果が得られたはず。

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

161 :デフォルトの名無しさん:2008/11/05(水) 19:25:05
>>148
>MTのような、周期の長い良質な擬似乱数の種としてこれを使えば、暗号ツールなどに実用的に応用できる。

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

162 :デフォルトの名無しさん:2008/11/05(水) 19:38:22
いや。

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

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

163 :デフォルトの名無しさん:2008/11/27(木) 22:25:54
NIST test 2.0bってどうなの?

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

164 :デフォルトの名無しさん:2008/11/28(金) 09:42:11
そりゃすげぇ
真の乱数で試してみたら? スレ違いだけど...

165 :デフォルトの名無しさん:2008/11/28(金) 11:42:49
真の乱数も試したけど駄目だった。
なんかp valueの分布が高いほうに偏ってる。

166 :デフォルトの名無しさん:2008/11/30(日) 14:12:53
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/

167 :デフォルトの名無しさん:2009/01/05(月) 13:48:27
再現可能な擬似乱数じゃないけど、こんなんみつけた

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


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


169 :デフォルトの名無しさん:2009/01/05(月) 15:42:33
WindowsってOSにこのてのメカニズム持ってないのか?

170 :デフォルトの名無しさん:2009/01/05(月) 17:21:26
ん、こういうの俺も昔遊びで作った事がある。


171 :デフォルトの名無しさん:2009/01/05(月) 23:24:02
SFMTをExcelで使うなら、シード値ってどうやりゃいい?
sgenrand Timer * 1000
なんてのがどっかにあったが、なんかいまいちだよな。

172 :デフォルトの名無しさん:2009/01/06(火) 00:12:34
>>169
ハードウェア使った処理が含まれているかどうかは分からないけど、
暗号論的に安全なのが欲しければ、CryptGenRandom使えということになっている。

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

174 :デフォルトの名無しさん:2009/03/09(月) 20:38:50
何が問題なんだろ。
松本さんの実装は、内部状態が1周した時に一斉に計算するようになってるので、
負荷が一定しないよなぁとは思うんだが、そういうとこじゃなくて、原理的に問題が
ある、っつってんだよね。
遅いというのは、はあそうですか、というだけなんだけど、blogのほう見ると、
XOR だけで構成されている、ってことをdisってるように見えるんだが...

175 :,,・´∀`・,,)っ-○◎●:2009/03/09(月) 20:41:31
KISS99もシンプルだし悪くはないんだが

176 :デフォルトの名無しさん:2009/03/10(火) 00:23:48
>>174
ブログで参照しているこのペーパーにあるMT19937のテスト結果がCrash 2回、BigCrash 2回になっているからだからだと思う。
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf
誰か解説キボン

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

178 :デフォルトの名無しさん:2009/03/10(火) 11:49:47
なんかその論文で提案してるテストでは、暗号学的な強度のあるジェネレータ以外は
のきなみパーフェクトでない結果を出してるみたいだ。
MTの成績が際立って悪いとかそういう結果ではないけど、ffmpegの作者的には
気になる結果なのかな?

179 :デフォルトの名無しさん:2009/03/12(木) 22:15:08
元々そちらの専門家みたい

180 :デフォルトの名無しさん:2009/04/17(金) 14:38:32
ダメ

181 :デフォルトの名無しさん:2009/06/20(土) 20:18:13
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

182 :デフォルトの名無しさん:2009/06/20(土) 20:20:22
スワヒリ語でおk

183 :デフォルトの名無しさん:2009/06/20(土) 20:54:53
なんか見覚えある名前だなーと思ったらXorshiftの人だったか

184 :デフォルトの名無しさん:2009/08/11(火) 03:30:02
あげ

185 :デフォルトの名無しさん:2009/08/11(火) 13:07:46
次は185が出てくる

186 :デフォルトの名無しさん:2009/08/14(金) 01:57:19
お初ですが質問させてください。

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

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

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


187 :デフォルトの名無しさん:2009/08/14(金) 02:06:20
そこだけ__asm { } でインラインアセンブラで書くとか

188 :デフォルトの名無しさん:2009/08/14(金) 08:53:55
int64が無いコンパイラだとasmも無さそうな

189 :デフォルトの名無しさん:2009/08/14(金) 09:37:58
>>186
具体的なロジックを出さないと、曖昧なレスしかつかないよ。

190 :デフォルトの名無しさん:2009/08/14(金) 13:23:06
186です。

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

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


191 :,,・´∀`・,,)っ-○○○:2009/08/15(土) 09:25:55
>>186
ないから自力でやれ

192 :デフォルトの名無しさん:2009/08/15(土) 20:24:26
どなたかご教示願います。
lehmerの線型合同法で作成される乱数値は、
初期値が同じでも計算機環境の違いにより変わることはありますか?

193 :デフォルトの名無しさん:2009/08/16(日) 02:20:18
うん

194 :デフォルトの名無しさん:2009/08/16(日) 08:03:39
同じ数式を計算したのに計算機環境の違いで結果が変わることがあると思う?

195 :,,・´∀`・,,)っ-○○○:2009/08/16(日) 08:23:56
浮動小数ならよくある

196 :デフォルトの名無しさん:2009/08/16(日) 08:28:53
>>> (2 / 3) * 6
0
>>> 6 * 2 / 3
4


197 :192:2009/08/16(日) 11:13:06
>>193>>195>>196

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

198 :デフォルトの名無しさん:2009/08/17(月) 10:39:10
>>196
それらは「同じ数式」といえるのか?

199 :デフォルトの名無しさん:2009/08/17(月) 13:04:38
>>194
有効桁数をちゃんと制御して、その動作が保証されている言語を使うなら、
バグでない限り有効桁数の範囲で変わることはない。

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

200 :デフォルトの名無しさん:2009/09/03(木) 21:52:50
高次元均等分布性ってどういうこと?
p[i]=(x[Ni+0],x[Ni+1],…,x[Ni+N-1])
として作ったN次元乱数のN次元空間上散布図が
N次元空間内に平面作ったり偏ったりせずにぼんやり分布することと考えていいのかな?

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

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

202 :デフォルトの名無しさん:2009/10/04(日) 07:32:06
一月あげ

203 :デフォルトの名無しさん:2009/10/05(月) 10:51:02
unko

204 :デフォルトの名無しさん:2009/10/05(月) 15:32:33
Blum-Blum-Shub のC/C++ の実装コードが掲示されているサイトを知ってる人いませんか?
java での実装例はここにあるんですが
http://code.google.com/p/javarng/

205 :デフォルトの名無しさん:2009/10/05(月) 18:00:56
1+1=2

206 :デフォルトの名無しさん:2009/10/05(月) 18:22:02
>>204
BlumBlumShub.java を C/C++ に書き換えるだけじゃだめなん?


207 :デフォルトの名無しさん:2009/10/05(月) 18:34:10
C/C++ に BigInteger の標準的な代替物でもあれば楽勝だろうけど

208 :デフォルトの名無しさん:2009/10/05(月) 18:55:46
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 かなんかの命令セットなのか?

209 :デフォルトの名無しさん:2009/10/05(月) 19:01:35
>>204>>208です皆さんサンクスです。
>>207
その通りです、java からの移植はBigInteger を見て、ライブラリから作る羽目になりそうだったので
速攻あきらめました。boost にBlumBlumShubがあればいいのにな・・・・

210 :デフォルトの名無しさん:2009/10/06(火) 00:46:53
>208
C/C++ ではコマンドとか命令とか命令セットとは言わないだろう、普通。
命令セットって言われたら CPU の instruction set を思い浮かべるわ。

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

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

211 :デフォルトの名無しさん:2009/10/06(火) 22:41:31
>210
gcc -o blumblum blumblum.c lip.c
このオペレーションも上手くいかない・・・orz



212 :デフォルトの名無しさん:2009/10/06(火) 23:27:47
今度はオペレーションて

213 :デフォルトの名無しさん:2009/10/07(水) 06:28:55
>>209 gmp じゃだめ?


214 :デフォルトの名無しさん:2009/10/07(水) 08:53:51
どういうエラーが出てるのか書かなきゃ対処しようもないぞ

215 :デフォルトの名無しさん:2009/11/14(土) 09:37:55
xorshiftをunsigned longではなく32bit intの範囲内でやる方法はありませんか?


216 :デフォルトの名無しさん:2009/11/14(土) 16:45:06
complementary multiply-with-carry ってのが
周期長くて計算軽いってのは分かったけど
高次元での均等性はどうなの?
MTだと623個の組で使っても大丈夫ということだけど

217 :デフォルトの名無しさん:2009/11/14(土) 19:33:47
RC4が最強だろ

218 :デフォルトの名無しさん:2009/11/15(日) 00:29:33
>>215
符号無しの整数型が存在しない言語で実装しようとしているのか?
例えば、Javaとかだと符号付き整数型でも気にせずビット演算して大丈夫のはずなんだけど。

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

219 :デフォルトの名無しさん:2009/11/18(水) 19:08:23
最近できた疑似乱数をまとめたサイトとかない?

220 :デフォルトの名無しさん:2009/12/05(土) 08:22:52
起動戦士ランダム♪ランダム♪

221 :デフォルトの名無しさん:2009/12/05(土) 11:36:41
俺がランダムだ

222 :デフォルトの名無しさん:2010/01/08(金) 13:19:31
シェーダ/GPGPU向けでよい疑似乱数ってどんなのがあるでしょうか。
数列系の疑似乱数を直に使うことが出来ないのでいろいろ考えています。

223 :デフォルトの名無しさん:2010/01/08(金) 14:30:20
もっと具体的に書かないと分からん
メモリアクセスが厳しいとかそういう話か?

224 :デフォルトの名無しさん:2010/01/08(金) 14:35:46
もう一つ
>数列系の疑似乱数
擬似乱数はみんな数列だぞ

225 :デフォルトの名無しさん:2010/01/08(金) 14:42:46
ワーキングセットが小さい、って意味か?
確かにMTは比較的大きいが。

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

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

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

227 :デフォルトの名無しさん:2010/01/08(金) 15:22:14
プールして切り出し

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

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


229 :デフォルトの名無しさん:2010/01/08(金) 20:32:23
遅れまして申し訳ありません。

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

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

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

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


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

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

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

232 :デフォルトの名無しさん:2010/01/09(土) 12:02:20
>>228
こういう用途なら、単純に1次元化して、正規乱数を利用すればいいんじゃないの?

233 :デフォルトの名無しさん:2010/01/09(土) 12:35:43
それじゃ速度が出ないだろ
というかそれでいいなら質問してこないだろ


234 :デフォルトの名無しさん:2010/01/09(土) 12:38:29
その前にその正規乱数はどこから持ってくるのかと小一時間(ry

235 :デフォルトの名無しさん:2010/01/09(土) 23:20:47
>アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。

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

236 :デフォルトの名無しさん:2010/01/10(日) 00:55:27
砂嵐状態っていっても度合いがあるからね。
元の信号が強く混ざってれば文字通り目に見えて分かるし。
砂嵐(スノーノイズ)の原因は熱雑音らしいから
S/Nが十分に悪ければ(笑)ほぼ相関なしといえると思う。

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

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

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


237 :デフォルトの名無しさん:2010/01/10(日) 03:21:02
仕組みが分かったところで、解を出すためには初期条件が必要
シードを与えて一意な結果を出すのは一般的な乱数と同じものだろ

238 :デフォルトの名無しさん:2010/01/10(日) 03:26:41
>>237
何の話?

239 :デフォルトの名無しさん:2010/01/10(日) 04:32:49
物理量を離散的に捉えるのは根本的に違ってるぞ

240 :デフォルトの名無しさん:2010/01/10(日) 05:36:42
サンプリングすればおk

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

242 :デフォルトの名無しさん:2010/01/11(月) 03:25:51
プリレンダした砂嵐テクスチャ並べて適当に描画すれば?

243 :デフォルトの名無しさん:2010/01/11(月) 09:28:59
>>242
それは正しい処理だが、スレタイを翌嫁。

244 :デフォルトの名無しさん:2010/01/11(月) 16:31:10
>>242,243
それだとテクスチャが沢山必要になるからi/oで引っかかって
擬似乱数より遅くなるよ


245 :デフォルトの名無しさん:2010/01/11(月) 20:19:14
二次写像などのカオスの数値の下ビットを使うというのはどうだろう

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


246 :デフォルトの名無しさん:2010/01/11(月) 20:48:42
>>245
数理的な意味でのカオスってのは、テント写像に代表されるように
小数点以下を無限に汲みだす漸化式になっているから予測が難しいのであって、
種が有限桁数であっては成立しない。

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

247 :デフォルトの名無しさん:2010/01/11(月) 20:48:48
こんなことを言い出すやつがいるとは…
それは線形合(ry
このスレは分かってる人とそうでない人のレベル差が妙に大きいな

248 :デフォルトの名無しさん:2010/01/11(月) 20:57:18
>むしろ、いかなる相関性のある入力に対しても、
>周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。
いいわけない、というかそれはただのハッシュ
等確率性・分布・周期を保証できないし
入力がずっと同じだったらどうにもならん

249 :デフォルトの名無しさん:2010/01/11(月) 21:02:21
>>248
アンカが抜けてた

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

250 :デフォルトの名無しさん:2010/01/11(月) 21:36:24
>>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/

251 :デフォルトの名無しさん:2010/01/12(火) 01:04:22
これは過去ログ見てみたかったな
まあ乱数弄ってりゃそのうち巡り会うこともあろう

252 :デフォルトの名無しさん:2010/01/12(火) 01:25:44
>>426が言いたいのはハッシュ関数かと思われ

253 :デフォルトの名無しさん:2010/01/12(火) 03:31:52
>>251
過去ログ(1146071975.dat)うpしたね
http://www.dotup.org/uploda/www.dotup.org553146.dat.html
よかたら見るね

254 :デフォルトの名無しさん:2010/01/12(火) 11:59:26
>>226
ホワイトノイズ(一様分布)じゃなくてブルーノイズでも良いなら方法はある。
ブルーノイズはホワイトノイズの低周波成分を除いたもの。

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

255 :デフォルトの名無しさん:2010/01/12(火) 16:02:33
乱数をjpegなどのデコーダーに食べさせるって言うのはどうだろうか

256 :デフォルトの名無しさん:2010/01/13(水) 01:01:39
>>253
頂きました!
どうもありがとう〜
俺,週末になったらこれ読むんだ…

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

258 :デフォルトの名無しさん:2010/09/14(火) 17:15:16
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個

259 :デフォルトの名無しさん:2010/09/30(木) 05:03:43
擬似乱数についてまとめた本とかってあります?

260 :デフォルトの名無しさん:2010/09/30(木) 05:07:25
http://sky.geocities.jp/tcshacina/grs.c
作ってみました。

261 :デフォルトの名無しさん:2010/09/30(木) 05:13:08
g・r・s!

262 :デフォルトの名無しさん:2010/09/30(木) 09:22:33
>>259 ちょっと内容が古いけど「乱数」という本がある。
あと定番としてはTAOCP2巻。

263 :デフォルトの名無しさん:2010/10/01(金) 01:32:20
grsって何?

264 :デフォルトの名無しさん:2010/10/01(金) 02:15:37
ggrks

265 :デフォルトの名無しさん:2010/10/01(金) 07:52:17
乱数生成generalized reed solomon(GRS)
コンパイルしてみてください。あらさがしもOK。

266 :デフォルトの名無しさん:2010/10/01(金) 12:22:27
>>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


267 :デフォルトの名無しさん:2010/10/01(金) 12:26:55
インデントぐちゃぐちゃだわ、場所によってコーディングスタイル違うわで気持ち悪いソースだな

268 :デフォルトの名無しさん:2010/10/01(金) 17:22:01
C:\cygwin>gcc -O2 -ftree-vectorize -ftree-vectorizer-verbose=5 -msse2 -o hash ha
sh.c

269 :デフォルトの名無しさん:2010/10/01(金) 17:23:29
C:\cygwin>gcc -O2 -ftree-vectorize -ftree-vectorizer-verbose=5 -msse2 -o grs grs.c

270 :デフォルトの名無しさん:2010/10/01(金) 18:26:44
gcc tmp.c -I/usr/local/include -L/usr/local/lib -lgmp -o tmp -O2

271 :デフォルトの名無しさん:2010/10/21(木) 22:32:31
著作権の表記無しで使える優秀な疑似乱数生成アルゴリズムある?

272 :デフォルトの名無しさん:2010/10/22(金) 09:44:29
アルゴリズムに著作権はないから

273 :デフォルトの名無しさん:2010/10/22(金) 10:15:00
つまり、「著作権表記なしで使える実装」のある、「優秀な擬似乱数生成アルゴリズム」を所望しているのかな。
んなもん、自分で実装すれば選び放題だ。

274 :デフォルトの名無しさん:2010/10/22(金) 23:22:08
例えばメルセンヌツイスタはBSDライセンスだけど
コードを参考にして自分で実装すればBSDライセンスに従う必要は無いってこと?

275 :デフォルトの名無しさん:2010/10/22(金) 23:34:49
パクリ度による


276 :デフォルトの名無しさん:2010/10/23(土) 08:59:29
メルセンヌ・ツイスターの性能に勝るとも劣らない優れたもの??らしい。
ttp://ayusya.hp.infoseek.co.jp/AlgorithmRandom.html


277 :デフォルトの名無しさん:2010/10/23(土) 09:51:07
XORSHIFTにちょっと似てる?

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

278 :デフォルトの名無しさん:2010/10/23(土) 12:52:34
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

こんなとこかな。


279 :デフォルトの名無しさん:2010/10/23(土) 19:50:35
>>276

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


280 :デフォルトの名無しさん:2010/10/23(土) 20:43:04
ちょっと乱数が欲しいというときの物としてなら受け入れられるだろうに、
MTと比較してと書かれるとイタいだけだな。

281 :デフォルトの名無しさん:2010/10/23(土) 21:29:25
このアルゴリズムで同一値が2回連続して出現する事なんてあるのか?

282 :デフォルトの名無しさん:2010/10/23(土) 22:13:45
0 が出ないんじゃないか

283 :デフォルトの名無しさん:2010/10/24(日) 01:27:04
周期が55898とか出てるんだけど、なんか間違ってる?
0x65AC9360ULにしたら長くなったけど…

284 :デフォルトの名無しさん:2010/10/24(日) 02:29:14
周期が明示されていない、または、作者もわからないような擬似乱数はゴミだろ。
あと、同じ値が連続して出ないようなものは、いくら一次分布が均一に見えても乱数として使えない。

285 :デフォルトの名無しさん:2010/10/24(日) 07:41:43
線形合同法なんか、まさしくその「同じ値が連続して出ない」乱数なんだが。
誕生日検定に通らないわけだけどね。

286 :デフォルトの名無しさん:2010/10/24(日) 07:44:47
同じ値が連続して出たらその瞬間から値の変化しない乱数に

287 :デフォルトの名無しさん:2010/10/24(日) 08:28:08
ていうか、周期性があるものは、連続して内部的に同じ値(状態)をとるわけがない。
単に、特定の部分(bit)を取り出しているから、その部分では同じ値に見えるというだけ。

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

288 :デフォルトの名無しさん:2010/10/24(日) 08:58:30
所詮は有限個の整数の集合を同じサイズの整数集合に写像する関数だから、
内部的に2度続けて同じ状態をとるとしたら、その後は永久にその値になるからな。
物理乱数でもなければ窓を使うことで、その精度での乱数性を確保しているというだけだし。

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


289 :デフォルトの名無しさん:2010/10/24(日) 16:41:50
検索してみたら、乱数の誕生日検定について、情報がネットには全く存在してないでやんのw
「誕生日のパラドックス」が乱数列として期待される通りに成り立つかどうかの検定ね。
確かKnuthの本には書いてあった。

290 :デフォルトの名無しさん:2010/11/06(土) 22:40:38
別スレで聞いたのですがこちらに誘導されたので質問します。
メルセンヌツイスタを使って0〜(n-1)までの乱数を作りたいのですが、
これだとダメって言われたんですがどこを直せばいいのでしょうか。
INT value;
do {value=genrand_int31()%n;}
while(value>=0x0fffffff-value%n);

291 :,,・´∀`・,,)っ-○○○:2010/11/06(土) 23:03:00
いろいろひどいからエスパーしていい?

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

んで、

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

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


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

292 :デフォルトの名無しさん:2010/11/06(土) 23:19:31
>>291
ありがとうございます。
31ビットは0x0fffffffだと勘違いしてました。

293 :デフォルトの名無しさん:2010/11/06(土) 23:29:53
勘違いの問題点はそこじゃないと思うw

294 :デフォルトの名無しさん:2010/11/07(日) 12:16:05
もう終わったのかもしれんが
>>291
value = genrand_int31();
これはマイナスの値が返って来る可能性があるから
value = genrand_int31() & 0x7FFFFFFF;
にするべきじゃなかろか

295 :デフォルトの名無しさん:2010/11/07(日) 13:42:16
int31なのに負の値が帰ってくるの?

296 :デフォルトの名無しさん:2010/11/07(日) 13:45:36
名前で判断してはいけない

297 :,,・´∀`・,,)っ-○○○:2010/11/07(日) 15:15:37
MTのソースってこんな感じじゃなかったか?最近読んでないけど。

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


298 :,,・´∀`・,,)っ-○○○:2010/11/07(日) 15:17:20
自己解決

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



299 :デフォルトの名無しさん:2010/11/07(日) 16:30:25
ほうほう

300 :,,・´∀`・,,)っ-○○○:2010/11/07(日) 16:39:17
より厳密に言えば右シフトが論理になるか算術になるかはCの規格上は未定義だったりするのね
unsignedなら論理シフトになるってのはある程度のCPUでは共通してるだけの話

301 :デフォルトの名無しさん:2010/11/07(日) 16:50:17
なんてこった

302 :デフォルトの名無しさん:2010/11/07(日) 19:45:33
逆だろ。

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

303 :,,・´∀`・,,)っ-○○○:2010/11/07(日) 19:58:33
規格書落としてきた。
失礼、unsignedの場合は論理シフトで保証されるんだね。

304 :デフォルトの名無しさん:2010/11/07(日) 20:03:17
この辺かな
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.


305 :デフォルトの名無しさん:2010/11/08(月) 10:40:27
よかった、ほっとした

306 :デフォルトの名無しさん:2010/11/08(月) 12:09:17
そりゃunsignedなのに上から1が降ってきたら誰だってビビるわ

307 :デフォルトの名無しさん:2010/11/08(月) 12:14:17
算術シフトしかないCPUで、シフト演算はのんきに全部その命令を生成しちゃう
コンパイラだってあるかもしれんし、Cの仕様はそれすらimplementation-definedと
言っていそうな雰囲気がある。この場合は違ったわけだが。

308 :デフォルトの名無しさん:2010/11/12(金) 23:22:51
たまにはキャリーさんのことも思い出してあげて

309 :デフォルトの名無しさん:2010/11/13(土) 09:26:39
キャリーをさがせ

310 :デフォルトの名無しさん:2011/01/18(火) 01:52:26
NIST検査について質問です。乱数の統計的性質を調べるソフトなのですが、
このテストをすべて合格しないと乱数とは言えないのでしょうか?
特にFFT検査の場合に不合格になります。周期はないと思うのですが、なぜか
うまくいきません。それとも、これだけは絶対に通らなくてはいけないという
検査があるのでしょうか。どなたかご教示願います。

311 :デフォルトの名無しさん:2011/01/19(水) 01:13:06
テストに合格しようがしまいが乱数は乱数じゃね?

312 :デフォルトの名無しさん:2011/01/19(水) 01:42:36
二回(以上)続けて同じ数字が出ないものは乱数と呼びたくないな


313 :デフォルトの名無しさん:2011/01/19(水) 09:31:42
>>312
>>284-288

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

315 :デフォルトの名無しさん:2011/01/19(水) 17:03:32
本当にわかってないな

316 :デフォルトの名無しさん:2011/01/19(水) 17:14:01
一気に糞スレ化したね。

317 :デフォルトの名無しさん:2011/01/19(水) 17:53:20
>>315
何処がどう分かってないのかハッキリさせないと、その発言に意味はないと思いますよ。
意味のない発言の塊が2chなわけですけど

318 :デフォルトの名無しさん:2011/01/19(水) 17:55:41
314は巨大な状態空間の一部だけ切り出してる擬似乱数が想像できないんだろ

319 :デフォルトの名無しさん:2011/01/19(水) 18:20:58
>>317
>>313

320 :デフォルトの名無しさん:2011/01/19(水) 18:39:02
>>318
そういうのは自分で考えさせないと

321 :314:2011/01/19(水) 19:16:42
>>318、320
よく分からないんですが、疑似と真乱数を分けて考える必要はないということですか?

322 :デフォルトの名無しさん:2011/01/20(木) 00:03:34
何故区別する必要があると思ったの?
問題の出てくる例を挙げて欲しい。

323 :デフォルトの名無しさん:2011/01/20(木) 00:15:30
えさを与えないでください

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

325 :デフォルトの名無しさん:2011/01/20(木) 01:54:43
スルーしてください

326 :デフォルトの名無しさん:2011/01/20(木) 05:00:53
スレタイも読めないヤツに何かが分かるなんて期待するヤツはいない。

327 :デフォルトの名無しさん:2011/01/20(木) 17:55:54
わざと答えをはぐらかしてるみたい

328 :デフォルトの名無しさん:2011/01/20(木) 18:03:55
324は正しい

329 :デフォルトの名無しさん:2011/01/20(木) 18:06:56
乙です

330 :デフォルトの名無しさん:2011/04/16(土) 11:03:07.44
George Marsaglia (1924 - 2011)
ttp://www.legacy.com/obituaries/tallahassee/obituary.aspx?n=george-marsaglia&pid=148777353

331 :デフォルトの名無しさん:2011/04/16(土) 11:16:55.91
age

332 :デフォルトの名無しさん:2011/05/18(水) 23:19:05.17
乱数で数値nの約数の合計って使えないの?
結構バラバラなんだけど

333 :デフォルトの名無しさん:2011/05/18(水) 23:21:48.27
とりあえず検定の結果を示してもらわんとなんとも。

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

334 :デフォルトの名無しさん:2011/05/18(水) 23:58:05.10
数値nをどこから持ってくるのか詳しく聞かせてもらおうじゃないか

335 :デフォルトの名無しさん:2011/05/19(木) 16:36:50.88
ぶっちゃけそこはn=n+(秒針)みたいなでいいと思う
あとn/2/(nの約数の合計)なら多分1〜0しかでない

336 :デフォルトの名無しさん:2011/06/12(日) 19:32:33.48
RDRANDで疑似乱数オワタ?

337 :デフォルトの名無しさん:2011/06/12(日) 21:41:33.09
>>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命令は統計的に均一かつ非周期的、非決定的なデータを生成することが保証されている。

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

338 :デフォルトの名無しさん:2011/06/12(日) 22:06:24.66
なんで擬似乱数が終わるんだよ?
分からない奴は黙っとけ

339 :デフォルトの名無しさん:2011/06/12(日) 22:08:35.00
容易に再現できる乱数列が必要な応用があるとか全く知らないんだろ

340 :デフォルトの名無しさん:2011/06/16(木) 00:25:21.98
#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です。


341 :デフォルトの名無しさん:2011/06/16(木) 13:48:55.52
そもそもrandがスレッドセーフである保証がない。
スレッドセーフでない関数の読み出しにはロックをかけろ。

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

342 :デフォルトの名無しさん:2011/06/16(木) 21:37:26.52
>>340
rand_r()は実装されてないの?
シミュレーションとかに使うなら、当然もっとまともな乱数使うべきなんだけど

343 :デフォルトの名無しさん:2011/06/16(木) 22:04:02.90
randってアルゴリズムからして処理系依存だから
ドキュメント読むしかないと思うが

344 :天使 ◆uL5esZLBSE :2011/07/03(日) 19:51:40.73
2011年、Ruby,Perl,PHP,Pythonって並べたときにさ
ここで、Ruby以外を選ぶ奴ってマジでなんなんだろうな


ゴミは何いってもゴミ

345 :デフォルトの名無しさん:2011/07/03(日) 20:36:04.58
おや知らないうちに、MTの周期の短い奴が

346 :デフォルトの名無しさん:2011/07/03(日) 21:16:56.21
内部ベクトルぽ周期がxorshift128に似てるね
テストしてみるか


347 :デフォルトの名無しさん:2011/07/18(月) 01:12:26.71
初カキコというか質問があるんですが

348 :デフォルトの名無しさん:2011/07/18(月) 01:23:00.97
うーん…
XorShiftでいいや。

349 :デフォルトの名無しさん:2011/07/18(月) 01:27:26.98
パワフルプロ野球スレでcupsを256にすれば天才選手(低確率で出る初期能力が強い選手)が出ると聞きました
乱数のことはよくわからないんですがそのcupsという項目があって
それを256に合わせればいいという認識でよろしいんでしょうか

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

350 :デフォルトの名無しさん:2011/07/18(月) 01:28:07.97
すいません…ageてしましました…

351 :デフォルトの名無しさん:2011/07/18(月) 01:35:15.25
ゲームの話は板違い

352 :デフォルトの名無しさん:2011/07/18(月) 01:37:58.95
>>351
しゅません、ここしか見つからなくて…

353 :デフォルトの名無しさん:2011/07/25(月) 07:45:02.26
>>348
ttp://raluck.exblog.jp/7153886/

354 :デフォルトの名無しさん:2011/07/25(月) 19:27:51.78
乱数の「精度」って記述初めて見たぞ?言いたいことは判らなくも無いが。


355 :デフォルトの名無しさん:2011/07/25(月) 19:32:37.26
普通、品質って言うわな。

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

356 :デフォルトの名無しさん:2011/07/25(月) 19:37:41.28
ゲームに使うとかいろいろな種を試したとか
乱数の事なんか何にも分かってないんだろう
悪いけどそんな個人ブログなんか読む価値ないよ

357 :デフォルトの名無しさん:2011/07/25(月) 19:37:53.89
つーかウィキペディアのXorShiftの記事にも「精度」って言葉が使ってある。

誰だよほんとにもう。

358 :デフォルトの名無しさん:2011/07/26(火) 12:24:34.03
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
「精度」はどのくらいのビット数で示される範囲で乱数になっているかという意味で使われているようです。
つまり品質の一部分ですね。

359 :デフォルトの名無しさん:2011/07/26(火) 12:37:39.46
それはwikipediaのノート内で議論すべきでは

360 :デフォルトの名無しさん:2011/07/26(火) 19:22:02.57
漏れは精度っていうのは誤差の大小だと思っていた。


361 :デフォルトの名無しさん:2011/07/26(火) 19:28:23.63
一体何の誤差なのか

362 :デフォルトの名無しさん:2011/07/26(火) 20:21:03.30
理想的な分散から外れる誤差というのはあるんじゃね

363 :ななし。:2011/07/27(水) 14:04:51.54
カ オ ス ラ ウ ン ジ ゆ る せ な ぁ い ー

364 :デフォルトの名無しさん:2011/07/27(水) 16:02:15.11
the art of computer programinngの2巻の証明の行間が開きすぎだったから
細部まで証明しましたが何か?

365 :デフォルトの名無しさん:2011/07/27(水) 22:37:01.04
頭いいね!

366 :デフォルトの名無しさん:2011/08/02(火) 16:16:05.44
擬似乱数の偏りってビットごとの偏りとか周期性もちゃんと見たほうがいいと思うんだけどねえ。
乱雑性検定の一覧とか出したほうがいいんじゃないの

367 :デフォルトの名無しさん:2011/08/02(火) 16:42:04.28
まさにそれをやってるのがdiehard testsじゃないの

368 :デフォルトの名無しさん:2011/08/02(火) 19:08:01.33
その、「ビットごとの」は「周期性」にもかかってる?

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

369 :デフォルトの名無しさん:2011/08/02(火) 19:15:45.81
>「精度」はどのくらいのビット数で示される範囲で乱数になっているかという意味で使われているようです。
これ、初期値によっちゃ10個ぐらい0が続いてもどうする?

370 :デフォルトの名無しさん:2011/08/02(火) 19:17:27.23
>>367
そうなんだけど>353の人にお勧めしたい。
ちゃんとした統計を取る気があるが知らないだけのようなので。

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

371 :デフォルトの名無しさん:2011/08/02(火) 19:45:25.22
> どのくらいのビット数で示される範囲で乱数になっているかという意味

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

372 :デフォルトの名無しさん:2011/08/03(水) 04:39:55.82
それより問題は>>348がTinyMTを試した結果なぜXorshiftを選択したかだな

373 :デフォルトの名無しさん:2011/08/03(水) 19:21:14.73
内部ベクトルって見て楽しいのかね

374 :デフォルトの名無しさん:2011/08/03(水) 19:57:03.18
見て楽しいかどうかは人それぞれ 4ビットでシフトレジスタ
ttp://upload.wikimedia.org/wikipedia/commons/7/7f/LFSR-F4.GIF

375 :デフォルトの名無しさん:2011/08/04(木) 00:13:01.69
楽しくなければ乱数じゃない!

376 :デフォルトの名無しさん:2011/08/04(木) 09:30:26.00
グレイコードってやつだな。

377 :デフォルトの名無しさん:2011/08/04(木) 10:37:52.94
グレイコードは1度にハミング距離が1しか変化しないコードだろ

378 :デフォルトの名無しさん:2011/08/04(木) 10:48:53.38
なんだ・・・ただ1づつ足していくだけかクダラネ。

379 :デフォルトの名無しさん:2011/08/04(木) 12:02:14.43
ハミング距離も知らんのか

380 :デフォルトの名無しさん:2011/08/04(木) 12:20:06.08
すごいすごいすごい
ハミング距離を知っているなんて凄いねーー
エライネー
天才だね〜

381 :デフォルトの名無しさん:2011/08/04(木) 19:22:19.62
いやあそれほどでも(クィッ!

382 :デフォルトの名無しさん:2011/08/26(金) 11:30:52.08
復帰

383 :デフォルトの名無しさん:2011/11/07(月) 00:15:56.56
擬似乱数ではないのでスレ違いかもしれないが
ちょっとコンセプトを思いついたので実装してみた。
http://netrand-test.appspot.com/

384 :デフォルトの名無しさん:2011/11/07(月) 00:34:50.29
何に使うんだそれは

385 :デフォルトの名無しさん:2011/11/07(月) 07:01:49.82
/dev/random のような用途?

386 :デフォルトの名無しさん:2011/11/23(水) 11:19:10.85
なんか加減算だけでそれっぽいのができたぜ

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

387 :デフォルトの名無しさん:2011/11/23(水) 22:49:37.46
>>386
SFMTに対して、どこがアドバンテージあるの?
周期2^216091-1とかだぞ。

388 :デフォルトの名無しさん:2011/11/23(水) 22:57:01.60
出力範囲が1000(10ビット未満)というのもな
32ビット精度必要なら4個を組にして使うわけだが,その上での一様性も相当疑わしい

389 :デフォルトの名無しさん:2011/11/24(木) 08:38:35.87
出現回数をカウントできるようにしたぜ

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

391 :デフォルトの名無しさん:2011/12/10(土) 01:02:45.31
要するにハッシュ関数的な要素が欲しいんでしょ
入力値のハミング距離が近くても出力値のハミング距離が遠くなるように
ハッシュ関数通せばいいよ


392 :デフォルトの名無しさん:2011/12/10(土) 01:04:32.98
ハッシュ関数、初耳ですがちょっと調べてみます

393 :デフォルトの名無しさん:2011/12/10(土) 01:13:57.92
毎回srandしてるようにも読めるな
そうでないなら適当に読み捨てれば?

394 :デフォルトの名無しさん:2011/12/10(土) 01:37:08.54
>>390
どれぐらい「近いようなもの」でなければよいのか、
はっきりしてもらわないと何ともならんのじゃないか?

395 :デフォルトの名無しさん:2011/12/10(土) 01:39:31.04
ハッシュ関数知らないレベルだから改善の余地は大いにありそうだが


396 :デフォルトの名無しさん:2011/12/10(土) 02:29:28.25
>>393
お恥ずかしながらおそらくそれをしていました

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

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

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

397 :デフォルトの名無しさん:2011/12/10(土) 02:45:34.85
典型的にはZobrist Hashingが使える


398 :デフォルトの名無しさん:2011/12/11(日) 08:35:49.22
他の人たちは 390 が何をしたいか分かったの?
もっとちゃんと問題を定義したらズバリの答えが出る気がするけど。

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

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


399 :デフォルトの名無しさん:2011/12/11(日) 08:58:54.46
>>396
低周波成分(いわゆる模様)の無いノイズが欲しいなら
それは乱数ではなく、乱数から低周波成分を除く加工をして作る数列
ブルーノイズとか

400 :デフォルトの名無しさん:2011/12/12(月) 19:02:48.17
>>398
>(rand() & 0x7fffff) | 0x3f800000
>として [1.0 .. 2.0) を作り、必要に応じて線形変換するのが常道。
これは知らなかった。
rand() / (RAND_MAX_1)とばかり。


401 :デフォルトの名無しさん:2011/12/12(月) 19:13:08.54
fmul一回分だけお得と
まあ大抵は再度後から掛けるだろうけど

402 :デフォルトの名無しさん:2011/12/14(水) 20:11:28.68
9bit損するからじゃね?

403 :デフォルトの名無しさん:2011/12/21(水) 14:23:42.69
音のノイズなら線形合同のほうがいいよ
偏りや周期を聞き分ける人がいたら神だよ

404 :デフォルトの名無しさん:2011/12/24(土) 15:01:03.98
上位ビット使うんだぞ

405 :デフォルトの名無しさん:2011/12/24(土) 18:33:56.26
気をつけます。

406 :デフォルトの名無しさん:2011/12/25(日) 00:38:03.89
>>403
ダイナミックレンジ広いと偏りはわからんが、周期は聞こえるぞ


407 :デフォルトの名無しさん:2011/12/25(日) 10:38:56.24
線形合同法でノイズ作ったぜ

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

408 :デフォルトの名無しさん:2011/12/30(金) 00:08:06.52
もう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;
}


409 :デフォルトの名無しさん:2011/12/30(金) 16:57:53.03
129ビットぶんの状態があるように見えるけど周期は2^121なのか
加算の使い方がまたなんとも

410 :デフォルトの名無しさん:2012/01/02(月) 18:16:00.13
L・C・G!L・C・G!

411 :デフォルトの名無しさん:2012/07/24(火) 08:00:03.47
wikipediaにある
'特定の範囲で乱数を求めたいときにはa = rand() % 10とする方法も広く知られているが、線形合同法などの下位ビットの乱数としての品質が低い生成法に備えるため上記のコード例のような上位にあるビットを利用するコードが推奨されている'
ってどいういうこと?
(int)((rand() / ((double)RAND_MAX+1.0)) * 2);

rand()%2
で1000000回、乱数を生成して比較してみたけど、平均値と0.5の差はどちらもオーダー的にほとんど変わらないのだけど、

412 :デフォルトの名無しさん:2012/07/24(火) 08:24:36.56
面倒だから
乱数 下位ビット
でググってもらっていいかな。

413 :デフォルトの名無しさん:2012/07/24(火) 08:26:01.03
>>411
品質が悪いと、奇数偶数が交互にしか出なかったりする。

414 :デフォルトの名無しさん:2012/07/24(火) 09:00:13.60
>>412

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

415 :デフォルトの名無しさん:2012/07/24(火) 09:04:24.07
MTはかまわないよ
だめなのは質の悪い乱数に限った話
線形合同法はその代表格


416 :デフォルトの名無しさん:2012/07/24(火) 15:07:40.15
%は法の数が大きいと分布の偏りが大きくなる。

417 :デフォルトの名無しさん:2012/07/24(火) 16:50:20.82
>>411
酷い実験してるなw
頼むからブログとかでどっちも変わりませんでしたとか書かないでくれよww

418 :デフォルトの名無しさん:2012/07/24(火) 17:06:19.28
>>416
それって RAND_MAX が 16 だとして、rnd % 10 とかで計算したら、って話?
そりゃ普通は、はみ出る部分の値が出たら捨てるだろ。

419 :デフォルトの名無しさん:2012/07/24(火) 17:57:44.60
>>418
普通の知能の持ち主が剰余を使うならそうだが、剰余を使うほとんどの連中はそんなことはしないだろう


420 :デフォルトの名無しさん:2012/07/24(火) 19:19:37.18
法(のり)

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

422 :デフォルトの名無しさん:2012/07/25(水) 06:50:57.92
線形合同法は比較的単純な弱点が多いから、使う側が完全に把握して使うべきであって、
ライブラリ側でそういう配慮をするのはよくない(そういう配慮をして、ブラックボックス的に
使わせるなら他の生成法にすべき)。

423 :デフォルトの名無しさん:2012/07/30(月) 22:53:54.77
久々に見たらスレが進んでいるなと思ったら

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

424 :デフォルトの名無しさん:2012/08/01(水) 07:50:35.33
>>413
それを定量的に調べる方法はありますか?

425 :デフォルトの名無しさん:2012/08/01(水) 08:14:03.90
>>424
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

426 :デフォルトの名無しさん:2012/08/03(金) 08:40:44.06
メルセンヌ・ツイスタでseedはどうやって与えれば良いの?


427 :デフォルトの名無しさん:2012/08/03(金) 08:47:28.71
初期化関数の引数にシードを与えればいいよ。

428 :デフォルトの名無しさん:2012/08/03(金) 09:07:33.39
それやってみたのですが、最初の方は似たような数字になってしまいます。


429 :デフォルトの名無しさん:2012/08/03(金) 09:17:44.87
内部状態が2kバイト強あるから、先頭から4kバイト弱ぶんぐらい読み飛ばす。

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

430 :デフォルトの名無しさん:2012/08/03(金) 09:22:52.54
>>428
それ、小さいシードで初期化するときの実装が古いやつなんじゃないか?

431 :デフォルトの名無しさん:2012/08/03(金) 09:27:16.85
何万個か読み捨てればいいよ。

432 :デフォルトの名無しさん:2012/10/01(月) 07:40:42.45
Perlでメルセンヌツイスタをつかえますか?

433 :デフォルトの名無しさん:2012/10/01(月) 09:10:34.08
うん

434 :デフォルトの名無しさん:2012/11/20(火) 11:52:42.11
rand(0)とrand(1)どちらも同じ乱数列を生成するのですが、
そのように決まっているのですか?
それともたまたま使っている処理系が、0と1で同じ乱数列を吐き出すのですか?

435 :デフォルトの名無しさん:2012/11/20(火) 12:10:19.47
rand()って引数いらんのでは?
説明めんどいからsrandも調べてみ
色々わかるから

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

436 :デフォルトの名無しさん:2012/11/20(火) 12:36:34.27
>>434
お使いの処理系のマニュアルをご覧ください。

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

437 :デフォルトの名無しさん:2012/11/20(火) 13:27:08.91
回答もランダムです

438 :デフォルトの名無しさん:2012/11/22(木) 12:27:29.80
MATLABやRならrandはメルセンヌツイスタになってるよw

439 :デフォルトの名無しさん:2013/01/07(月) 21:11:37.12
>>429だな。
少なくともオフィシャルの実装には配列でシードを与える関数がある。

440 :デフォルトの名無しさん:2013/02/23(土) 22:05:49.43
static uint64_t x = seed;
x ^= x << 21;
x ^= x >> 35;
x ^= x << 4;
return (uint32_t)x; // doesnt pass

441 :デフォルトの名無しさん:2013/02/24(日) 04:19:20.32
そのまま返しちゃだめです

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

443 :デフォルトの名無しさん:2013/09/27(金) 23:42:09.81
monoが

444 :デフォルトの名無しさん:2013/09/29(日) 16:51:16.72
fortranでのSFMTの最速実装っていまどんなのあるの?

445 :デフォルトの名無しさん:2013/12/25(水) 18:00:46.47
A simple demonstration of twenty Pseudo Random Number Generators
www.dotup.org/uploda/www.dotup.org4761462.zip.html
Have fun with it !

446 :デフォルトの名無しさん:2013/12/25(水) 19:02:50.07
擬似乱数が真の乱数に近づく条件は周期を無限大にすること、
周期が長いとどういうことが起きるか?
数値の分布が極所で揺らぎ(歪む)出すってこと

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

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

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

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

448 :デフォルトの名無しさん:2013/12/25(水) 21:50:51.96
どうしたんだ?

449 :デフォルトの名無しさん:2013/12/26(木) 02:46:31.02
誰と戦ってるんだ。ところでフリーの乱数の性能評価ツールない?

450 :デフォルトの名無しさん:2013/12/26(木) 08:04:12.61
diehard

451 :デフォルトの名無しさん:2013/12/26(木) 10:18:01.99
>>446 447 はただのバカ。「疑似乱数列」「暗号学的に安全」「真の乱数」といった言葉を、
まるっきり俺様定義で使ってるから、全くの意味不明なナンセンス文になっている。

452 :デフォルトの名無しさん:2013/12/26(木) 19:03:55.58
>>450
thx!

453 :デフォルトの名無しさん:2014/01/03(金) 20:42:27.35
>>449
おまえ馬鹿だろ、そんなの自分で作れずどうするの?
目的によって違うんだから(ry

454 :デフォルトの名無しさん:2014/01/03(金) 23:06:25.84
過去数十年にわたって、数多くの研究者が乱数列の様々な評価法を考えてきたというのに、
それら全てを無視して、俺の能力ならすばらしい評価関数が作れる、ってか? すごい自信だな。

(普通、そういうのを「バカ」と言う)

455 :デフォルトの名無しさん:2014/01/04(土) 19:32:09.42
>>451
人格障害じゃね?貴方

456 :デフォルトの名無しさん:2014/01/04(土) 19:47:35.20
>>454

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

458 :デフォルトの名無しさん:2014/01/06(月) 09:52:48.11
方程式や論理式に現実性がない、だと?

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

459 :デフォルトの名無しさん:2014/01/07(火) 11:01:34.65
あんな重い鉄の塊が飛ぶわけないだろ

460 :デフォルトの名無しさん:2014/01/07(火) 11:16:14.23
飛行機は鉄の塊ってほど密じゃないけどね。
そもそも軽金属か樹脂がメインだし。

461 :デフォルトの名無しさん:2014/01/07(火) 11:53:33.12
鉄の塊は、レシプロ機のエンジンぐらいだな。高機能樹脂ができる前は軽合金、その前は木と布だったw
「機」(本来は、織機のように木などで出来た、軽いものを指す語)を使うのは伊達じゃない。

462 :デフォルトの名無しさん:2014/01/07(火) 14:40:58.24
最近は炭素素材も使われるようになったねぇ

463 :デフォルトの名無しさん:2014/03/27(木) 03:02:18.88 ID:2kZbCKHg
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以来のブレークスルーがあるような気がするな、、

464 :デフォルトの名無しさん:2014/04/11(金) 20:08:05.30 ID:vHcSHc13
ラン スー とくれば最後はもちろん ミキ

465 :デフォルトの名無しさん:2014/04/12(土) 13:57:47.36 ID:cTqY1h51
電線に

466 :デフォルトの名無しさん:2014/04/25(金) 13:01:06.17 ID:bY1/N1n7
一様な分布である乱数(「一様分布に従う乱数」)どうしの和は、一様な分布にならない。


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

2個の和
12個の和

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

467 :デフォルトの名無しさん:2014/04/25(金) 20:09:23.50 ID:DUkBiaE/
中心極限定理ですねえ

468 :デフォルトの名無しさん:2014/04/25(金) 22:34:52.61 ID:vRDAArpO
不思議だよね

469 :デフォルトの名無しさん:2014/04/26(土) 04:34:51.11 ID:VGFQwx9o
不思議なの?
結果の数値を表す組み合わせの存在ってだけだと思うんだけど

470 :デフォルトの名無しさん:2014/04/27(日) 21:38:54.17 ID:dRMpu4rZ
一様乱数ですら足して足してでガウス分布に近づいていく、というのだからねえ‥‥手元の教科書は証明抜きだ‥‥凡人には理解できない世界なのか?

471 :デフォルトの名無しさん:2014/04/27(日) 21:57:22.77 ID:J+hFW2BD
ごく単純に 2D6 とか 3D6 を....6面のサイコロを2個とか3個とか振って、出た目の合計とか、
考えてみればいいじゃないか。

472 :デフォルトの名無しさん:2014/05/01(木) 08:02:06.54 ID:txn6O3jo
>>471
それは「二項分布はガウス分布に近づく」ってやつだね,でもその証明も手元にないな‥

473 :デフォルトの名無しさん:2014/11/09(日) 14:21:04.82 ID:iOEsToOb
メルセンヌツイスタが最強

474 :デフォルトの名無しさん:2015/12/18(金) 13:17:24.11 ID:kGnyy2oJ
xorshift128+ってのが今はいいのかな

475 :デフォルトの名無しさん:2016/01/29(金) 15:49:03.52 ID:A091Ig/h
線形合同法の結果を x ^ (x>>n)すると改良できね?

476 :デフォルトの名無しさん:2016/03/19(土) 17:07:51.05 ID:nABaYqd9
xorshift1024*てえのが最高品質なうえに速度もトップクラスだぜとテスト結果を示して自信満々だが
なんだか話がうますぎてほんまかいなという気もする
http://xorshift.di.unimi.it/

32ビット型の扱いが最も効率良い言語の方がまだ多そうだからそっちで返してほしいのもあるな
返し方で調整できるといえばそうなんだけど

477 :デフォルトの名無しさん:2016/03/29(火) 09:31:35.21 ID:/c8bAcK4
サッカーブッシュ日本代表日程ぷあたん(しゅっちょうまいくろ教育長交代)春文執行40代売上差額シュガーチョコ
https://www.youtube.com/watch?v=NDq1QoJY0nY宇ドナルドアナリストパワーストーンコーチングとしまえん
サッカーブッシュ日本代表日程古本屋よしたけしゅっちょうちょこしゅがー
ディーラー税務署天才開発者死亡詰みヨミドクターマイクロサービス不足
サッカーブッシュ日本代表日程ぷあたんシフト光金さかい強制バイト人権侵害問題
春分資源執行ニューヨーク低原価ぼったステーキソルトレイク福岡横浜新橋奴隷課金パチシフト強制バイト問題新潟米センター生残
コスメ24チャリティー隠れ40代生活保護プレイボーイバイトレードいたりあん接待問題
マスコミKARDローンケーオーサービス不足婚活パーティー寄付金執行原発ビジネス
FBIチャイニーズタイホテル売上事務所ガチャ決算ガチャキャンペーン(販売報道陣過激派組織向携帯最新情報提供終了
校長発言細心注意ノートン産廃エラー(著作権クレーム中国反応融資高額教育費)(中国捕鯨団体40代社員サッカーコメント
高額入学金ヤフウ新橋大学ヤフウ新橋理事長FX経費 おじや50代資産ガリバズフィード40代エリート

478 :デフォルトの名無しさん:2016/03/29(火) 19:54:10.75 ID:B5K8vkuQ
>>476
やっていることは既存のxorshiftのアルゴリズムだな
内部で保持するシード列が64ビットになってその保持数が増えたって感じだね
速度は早いかもしれんが、乱数列としての質はどうなんだろうな
マジックナンバーの積算があるのが気になるw

汎用性から見てMTが最強には変わらないと思うよ

479 :デフォルトの名無しさん:2016/03/31(木) 20:16:33.23 ID:cjJ70n7R
とりあえずで利用するならSFMTとは思った
テスト結果どおり,統計的におそろしく性質がいいと分かってきたらまた見方が変わるかもしれん

480 :デフォルトの名無しさん:2016/09/21(水) 12:21:52.98 ID:CD/L3vnF
ゲームに乱数が使われていると思うけど、この計算の占める割合って全計算のどのくらいの割合
なんでしょうか?

481 :デフォルトの名無しさん:2016/09/21(水) 14:00:56.83 ID:ib8am8Zc
全体からみて1/1000000以下くらいじゃね

482 :デフォルトの名無しさん:2016/09/21(水) 14:06:22.50 ID:CD/L3vnF
全然大したことじゃないですか?
ほかのスレで、

ゲームサーバーでも対戦判定に莫大な回数の擬似乱数を回してパワーを食う

って書いてる人がいたんですけど

483 :デフォルトの名無しさん:2016/09/21(水) 14:30:30.69 ID:ib8am8Zc
この板の他のスレ?
それとも他の板のスレ?
この板のひとでそれを真に受ける人はいないと思いたい

484 :デフォルトの名無しさん:2016/09/21(水) 14:43:40.10 ID:CD/L3vnF
ポケモンのような大規模ゲームの場合でも、乱数発生の占める計算パワーは微々たるものですか?

485 :デフォルトの名無しさん:2016/09/21(水) 15:06:12.43 ID:DJrsIBwc
ネットワークの処理に比べればゼロに近い

486 :デフォルトの名無しさん:2016/09/21(水) 17:34:47.65 ID:yT1mont5
高速な物理乱数発生器なんて必要性ないですかね

487 :デフォルトの名無しさん:2016/09/21(水) 20:37:48.08 ID:5qi85AkV
あらかじめ物理乱数発生器で乱数表を作成
乱数表を順に読み込む

488 :デフォルトの名無しさん:2016/09/23(金) 10:57:39.17 ID:fan7eHym
乱数発生が重くて困るとか、真正乱数がぜひほしいっていう話はないですか?

489 :デフォルトの名無しさん:2016/10/05(水) 11:24:40.59 ID:lpG0enk6
http://d.hatena.ne.jp/tsukaban/20130727/p1
xorshiftについて聞きたいのですが、

x<<11
w>>19
t>>8

この 11 と 19 と 8 ってのはなんですか?
なんでもいいんですか?

64ビットで乱数を作りたいのですが、どう直していいか困ってます。

490 :デフォルトの名無しさん:2016/10/05(水) 13:39:42.79 ID:39LeL7K0
xorshift64 で検索したらいいじゃん。

491 :デフォルトの名無しさん:2016/10/05(水) 15:04:31.12 ID:lpG0enk6
簡単に言いますが、でしたら解答もらえんでしょうか

492 :デフォルトの名無しさん:2016/10/05(水) 15:09:17.42 ID:ZsK4JXk7
>>489
(・∀・)つ ホレ!
ttps://www.jstatsoft.org/article/view/v008i14/xorshift.pdf

Marsaglia先生が詳しく解説してくれてる

493 :デフォルトの名無しさん:2016/10/05(水) 15:33:16.58 ID:lpG0enk6
tだけを64ビットにすればいいってことですか?

494 :デフォルトの名無しさん:2016/10/05(水) 15:39:10.45 ID:lpG0enk6
たぶん分かりました。
ありがとうございます

495 :デフォルトの名無しさん:2016/10/06(木) 07:29:45.67 ID:iNNf2EsF
こういう厚かましい無能が現れるのも乱数性のなせるわざか。

496 :デフォルトの名無しさん:2016/10/06(木) 08:30:59.70 ID:2aWpWU4C
三木さんに新しい疑似乱数生成方式を考案してほしい
三木乱数で

ミキさんに考えてもらって乱数ミキでもいい

497 :デフォルトの名無しさん:2016/10/06(木) 12:12:14.44 ID:Yw0Cruyw
線形合同法は、下位ビットが偏る

メルセンヌツイスター、1996の方が、周期が長い

Xorshift、2003は高速

498 :デフォルトの名無しさん:2016/10/08(土) 06:01:51.17 ID:KfBpvv2w
順番性のテストをしたことあるけど、
xorshiftは異常なほど結果が偏ってるよ。
逆に線形合同法は異常なほど分散する。

結局、統計学や確率論などの乱数の順番が重要になる処理では結局どちらも使えない。
例えば、rand(100)で 5回連続で 20以下が出るかどうか。などの処理確率の信憑性が極めて疑わしい。


ちなみにテストはいろいろやったけど、xorshiftのおかしさが一撃でわかるのが x座標y座標と順番に出して印をつけてく方式。
線形合同法に至っては、rand(100) を100個出すだけで十分。確率上あり得ないくらい重複が少なく綺麗に分散する。


線形合同法は、下位ビットのかたよりがすぐ話題になるが、1/max の精度で乱数を必要とすることがあまりないのでけっこうどうでもいい。


ちなみに俺はここ数年、線形合同法で最初のseed設定時に乱数を1024個プールして、
array[rand(max) % 1024];
みたいな感じでランダムで取り出して使う。(そしてそこに次の乱数をセットする)。
って感じの自作汎用dllを使ってる。
トランプだって、2度シャッフルすればもう最初の並び順との因果関係は誰にも発見出来ないってね。


まぁメモリは多少食うし速度も最速じゃないけど、別に最速最小を求めるような研究者じゃないし。俺は。

499 :デフォルトの名無しさん:2016/10/08(土) 07:32:49.80 ID:U+ATce89
>>498
とりあえず、全bit使おうとするのは良くないというのは基本だと思うが

だからこそ、内部で32bitとかで種を持っているにもかかわらず、
標準Cでの要求が14bitとかそういう話になる

単純に割って使う(シフトでの下位bit切り捨てに相当)んじゃなく、上位もマスクして切り捨てて使うのが常識

500 :デフォルトの名無しさん:2016/10/08(土) 07:47:16.98 ID:PgGGpXVn
>>498
>ちなみに俺はここ数年、線形合同法で最初のseed設定時に乱数を1024個プールして、
>array[rand(max) % 1024];
>みたいな感じでランダムで取り出して使う。(そしてそこに次の乱数をセットする)。

それはDonald Knuth先生のリオーダーアルゴリズムBに近いな
内部のバッファリングは256だけどC++のstd::knuth_b(シャッフルオーダーね)がある

501 :デフォルトの名無しさん:2016/10/08(土) 14:10:54.10 ID:PgGGpXVn
>>498
>rand(max) % 1024
この部分は下位ビットの偏りが諸に関連しているよ
因みにstd::knuth_bではstd::minstd_rand0を元にバッファサイズで正規化して
値を取り出しているから、その演算のせいで他のに比べると重い
周期も数学的に不明だったかな

502 :デフォルトの名無しさん:2016/10/08(土) 18:34:54.73 ID:KfBpvv2w
あんま深く考えてなかったけどそうかもね。
ただし検定は通ってるから、まあいいっちゃいいけど。

実用上の実質的な周期はそのまま線形合同法と同じだよ。
まあ300回くらいなら多く回しても実用上にも問題ないけど、そんなのは計算しない。

>rand(max) % 1024
これは素数にすることでノーコストで解決できるから気が向いた時にでもやっとくよ。
ただ、どんなに下位ビットが偏ってた所で、
araay[988]の中身 と araay[986]の中身の因果関係、もしくは共通点は何か、と聞かれても判明させるのは不可能に近いと思うけどね。

>上位もマスクして切り捨てて使うのが常識
ただ線形合同法はそれでいいとしてxorshiftは捨てるべきビットが特定できないような?


まあ俺はシャッフルして何も捨てないのが好きらしい。
全部が若干遅いんだけどね。特にseed植える時。

503 :デフォルトの名無しさん:2016/10/26(水) 12:50:05.40 ID:X3TP1P6r
奥村先生のアルゴリズム事典にある乱数の改良法だぬ

xorshiftは生で使うと俺も気持ち悪さを感じるので線形合同法を足してる

504 :デフォルトの名無しさん:2016/12/10(土) 11:46:44.94 ID:DCOx50tb
統計の知識は中高どまり(平均・中央値・分散程度か)なので
乱数用に内部状態が32ビットしか確保できないソフトに対して単にxorshiftを採用して「検定もいい結果らしいし」と気にしていなかった

思ったより良くないとなると,プールしておいてランダムに取り出す方法も使えないし悩むな

505 :デフォルトの名無しさん:2016/12/14(水) 12:22:06.08 ID:7W6mxi0O
1個使ったら100個捨てるとか
RNGが保証してるのは周期だけだと割りきって頑張って調律するとか

506 :デフォルトの名無しさん:2016/12/14(水) 23:07:36.84 ID:2UzQxrtp
素人の生半可なオレオレ乱数はやらない方が身のため

507 :デフォルトの名無しさん:2016/12/31(土) 21:32:49.60 ID:VVtKGmEj
2017は素数か

508 :デフォルトの名無しさん:2017/01/01(日) 11:37:31.32 ID:DY9bt0tG
あけましておめでとうございます
return x = x * 2017 + 1;

509 :デフォルトの名無しさん:2017/01/05(木) 01:13:53.38 ID:yRe7g27Q
一個使って100個捨てるとか馬鹿の極み
コストを101倍にしてどうする。
コスト2倍も出せば問題のない乱数を作れるのに

510 :デフォルトの名無しさん:2017/01/05(木) 06:28:07.10 ID:42rV0dht
S/N比最低の2ちゃんでドヤっってる場合じゃないよな

511 :デフォルトの名無しさん:2017/01/05(木) 20:10:30.85 ID:atmVS5w4
S/N比最低というのは、乱数としては素晴らしいことだ。

512 :デフォルトの名無しさん:2017/01/06(金) 09:49:58.47 ID:zAIptLYs
つまり2chの書き込みをもとに乱数列を作る生成器を作れば…?

513 :デフォルトの名無しさん:2017/01/06(金) 12:01:18.30 ID:CHjfjTiP
片寄りが多くて一様じゃないからなあ……

514 :デフォルトの名無しさん:2017/01/06(金) 14:32:25.52 ID:eb3De0HO
>>513
ワロタ
一様分布じゃなく、一応分布が2chらしい

515 :デフォルトの名無しさん:2017/02/22(水) 09:39:50.93 ID:BVjvbr4Q
BIG 不正
いまGoogleで検索したら、すごいのがでますね

516 :デフォルトの名無しさん:2017/02/22(水) 09:56:53.06 ID:BVjvbr4Q
「14試合×5口分の予想結果が2回続けて全く同じという極めて不自然な結果が出力され、
システムの不具合や不正ではないかと一騒動となっている(中略)
日本スポーツ振興センターと楽天から調査結果の発表がなされたのだが、
くじは確かに販売されたものである」

スポーツくじ「BIG」でランダムなはずの予測結果が2連続で一致するも「偶然」との回答 - エキサイトニュース
http://www.excite.co.jp/News/it_g/20170221/Slashdot_17_02_20_1619238.html
2017年2月22日 09時50分

517 :デフォルトの名無しさん:2017/02/22(水) 12:02:19.51 ID:Acz49b5N
一人が予想して当たればその確率かもわからんけど、
1000人が予想した場合の期待値は1000倍になるんじゃね

518 :デフォルトの名無しさん:2017/02/23(木) 07:14:10.76 ID:WFbVQHcp
2回とも当たったんならすごいけどな

519 :デフォルトの名無しさん:2017/02/23(木) 07:17:16.12 ID:WFbVQHcp
数枚買ったうちの2枚が連続して同じだったのか
そりゃ金返せってなるな

最初から買わんけど

520 :デフォルトの名無しさん:2017/02/23(木) 07:23:45.91 ID:WFbVQHcp
セキュリティ上の理由から
アルゴリズム公開しないって書いてあるけど
全組み合わせを逐次予想するんじゃなくて
元々予想したくじを用意してあって
そこから適当に買った枚数分選んでくるとかだったら
重複確率は上がりそうだな

たまたま購入者が気付いただけで
気付かずに捨てられた券で
過去の重複してたのもっとあるんじゃないか

521 :デフォルトの名無しさん:2017/02/23(木) 08:54:22.37 ID:907E0Xet
どんな擬似乱数でも、内部的に状態を示す値を保持していて、それを元に次回の乱数を計算で出す
その値を初期化するのがsrand等だけど、その時に限らず常に値は持っているので
偶然内部の値が同じなんてこともよくある

ただし、普通は同じ値であっても、別の用途に乱数を使うので、同一であったことが問題になることはない

けれど、もし、14試合分の予想の直前の段階での内部的な値が、前回と全く同じ値だったとすると
そこから算出される各試合結果を示す乱数も、全く同じ値が出て
予想結果も全く同じものになる


偶然同じ状態値を持っている時に同じ買い方をしたために、全く同じ予想値になった

状態値のbit数が少ない(例えば普通に線形合同法だと32bitか)のを修正するか、
あるいはアルゴリズム的に同じ擬似乱数だけで順番に算出することを見直すか
そういうことをしないと、同じことが再び起こる可能性はある

擬似乱数だと防げないけどね


宇宙が始まるより低い確率云々ってのはナンセンス
擬似乱数の内部値が一致していて、単純に擬似乱数を利用するアルゴリズムだったというだけ
これは珍しいけど起こりうること

522 :デフォルトの名無しさん:2017/02/23(木) 13:04:42.59 ID:UXkH84Wv
宇宙云々はあくまで真の乱数が使われていた場合でしょ

523 :デフォルトの名無しさん:2017/02/23(木) 13:15:51.47 ID:eG9NqkD/
>>521
状態機械で内部の値が一緒だったらその次もその次もずっと同じ値を出し続けるんじゃね

524 :デフォルトの名無しさん:2017/02/23(木) 13:37:51.43 ID:lN59Dhjm
真の乱数なら、種の設定は (少なくとも実用上は) いかなる場合も最初の一度きりで二度と結果がループすることはない

525 :デフォルトの名無しさん:2017/02/23(木) 13:40:24.47 ID:lN59Dhjm
と言っても宇宙の何かの物理法則が真の乱数を作ることはないのだろうと思うけど。
全ては必ず有限らしいし、その中でのチューリング完全なんだろうだし。

526 :デフォルトの名無しさん:2017/02/23(木) 13:59:17.36 ID:7wYQlXII
一つずつ乱数生成してないのかもね

527 :デフォルトの名無しさん:2017/02/23(木) 16:45:07.24 ID:eG9NqkD/
>>524
真じゃない乱数は
ループの長さが長いか短いかだけで
いずれはループするんだよな

528 :デフォルトの名無しさん:2017/02/23(木) 16:46:44.91 ID:WFbVQHcp
>>526
なんらかのバグで内部状態が変化しなくなって
2回連続で同じ値を出してしまったら
再起動がかかるシステムだったりするかもしれない

529 :デフォルトの名無しさん:2017/02/23(木) 21:50:11.33 ID:5geihC2S
>>523
「前回(の乱数取得時)と同じ」という意味ではなく
「前回試合予想をした時と同じ」という意味ね

どちらも、同じ値から同じ試合の予想をして、
結果、前週と全く同じ予想が14試合x5口分で起きた

530 :デフォルトの名無しさん:2017/02/24(金) 14:00:51.79 ID:xRGcfmim
メルセンヌツイスタ使ってなかったんだろ

531 :デフォルトの名無しさん:2017/02/24(金) 19:02:56.20 ID:3z/u0Cfz
用途が用途だから暗号論的擬似乱数の適応だろ
/dev/urandomでもCryptGenRandomでも

532 :デフォルトの名無しさん:2017/02/25(土) 15:09:25.02 ID:u8Ry8YI7
状態変数が同じになったから同じ数列が出たんじゃねーよ。
二セット分繰り返す数列を出力する状態変数だっただけだろ。

http://science3.2ch.net/test/read.cgi/math/1088351567/424-425
円周率の 93299341 桁目から 07214545 という数列が出るそうだ。
まあ大体その辺で出そうな桁数だ。
おそらく無限に調べれば 1/10,0000,000 より少しだけ少ない頻度で出現するだろう。
そしてそのうちの 1/10,0000,000 は二回続く、つまり 1/10+E16 程度で 0721454507214545 という数列が出現するであろう。

目立つ組み合わせだから話題だが、どの二セットを取っても、その組み合わせが発生する確率は同じだ。

533 :デフォルトの名無しさん:2017/02/25(土) 16:57:29.92 ID:usTDxsWv
e なら割と早く出て来る

534 :デフォルトの名無しさん:2017/03/10(金) 21:31:43.44 ID:ARsP6JfD
PCGってどうなん?
ttp://www.pcg-random.org/

説明読んだりビデオ観たりした限りでは優れているみたいなんだけども
アルゴリズム的には線形合同法とXorShiftのハイブリッドの様な感じで
結構単純な構造なんだけど、高速で良質な乱数を生成するとか

因みに2年前に発表されているみたいなんだけど知らんかったわ

535 :デフォルトの名無しさん:2017/04/23(日) 03:06:26.50 ID:H8Cvp+NU
周期性と分布バランスが目的用途に特化できるならそれが最強だろ

536 :デフォルトの名無しさん:2017/05/11(木) 11:22:40.04 ID:yPF7Zec4
最強(笑)

130 KB
新着レスの表示

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50
名前: E-mail (省略可) :


read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)