疑似乱数２

1 名前：デフォルトの名無しさん [2007/10/17(水) 22:34:59 ] 擬似乱数発生器について語ろうか。その２ 前スレ 擬似乱数 pc11.2ch.net/test/read.cgi/tech/1146071975/ 関連スレ 【危険】とんでもプログラム告発スレッド【悪質】 pc11.2ch.net/test/read.cgi/tech/1191860116/ SIMD-oriented Fast Mersenne Twister (SFMT): www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html 63 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 04:04:29 ] web.comlab.ox.ac.uk/oucl/work/richard.brent/random.html 64 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 17:24:18 ] >>63 thx 65 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 22:04:20 ] 32 行書けるんだからもうちょっと綺麗におながいします 67 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 23:52:54 ] 上のほうでrand()をダイハードに食わせるとかいってた人がいたのでオチを教えておきます。 p=1.0頻発します。テストの種類によっては部分がすべてp=1.0　あわせてp=1.0みたいな。 xor128（）って、例の論文に載ってるコードを組み込む場合、ライセンスはPD扱いですか？ 68 名前：デフォルトの名無しさん mailto:sage [2008/01/15(火) 00:53:58 ] >>65 こりゃ無茶だろ．こういう使い方は．．． 別の種の乱数を４個同時に生成するのが正解 69 名前：デフォルトの名無しさん mailto:sage [2008/01/15(火) 16:03:59 ] >>62 xor128内部で使われてる変数x,y,z,wの中のxに、デフォルトの数値(123456789)の変わりに 与えられたseed値を代入するようにしてみた。 一応ちゃんと動作してるっぽいが統計的に良いのか悪いのかはよく分からん 70 名前：デフォルトの名無しさん mailto:sage [2008/01/15(火) 18:39:47 ] >>69 初期値ってあの値じゃなくても良かったのね。 乱数の質がどの程度変わるのかが気になるが 71 名前：デフォルトの名無しさん mailto:sage [2008/01/15(火) 19:28:29 ] やっつけでtimeの値入れたり 72 名前：デフォルトの名無しさん mailto:sage [2008/01/15(火) 19:41:19 ] SEED値を入れるならxよりwの方がいい気がする 73 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/01/15(火) 21:20:55 ] >>73 その種の使い方、MTと全く同じだな 75 名前：デフォルトの名無しさん mailto:sage [2008/01/17(木) 22:51:40 ] XorShiftの正しいシードの設定方法を教えてくれ！ 76 名前：デフォルトの名無しさん mailto:sage [2008/01/26(土) 18:55:32 ] 論文の６ページ目に 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; } 77 名前：デフォルトの名無しさん mailto:sage [2008/01/29(火) 19:35:39 ] なるほど、どんな初期値であっても、2^128-1のどこかの部分列になってるのか 78 名前：デフォルトの名無しさん mailto:sage [2008/01/29(火) 23:17:42 ] >>61について誰か詳しく頼む 79 名前：デフォルトの名無しさん mailto:sage [2008/01/31(木) 21:25:58 ] ん？　何が分からなかった？ 80 名前：デフォルトの名無しさん mailto:sage [2008/01/31(木) 21:44:19 ] 遅いんだよ もういい 81 名前：デフォルトの名無しさん mailto:sage [2008/01/31(木) 23:24:35 ] はやっ 82 名前：デフォルトの名無しさん mailto:sage [2008/01/31(木) 23:53:55 ] こんな過疎スレで遅い言われても 83 名前：デフォルトの名無しさん mailto:sage [2008/01/31(木) 23:59:56 ] 自分がいくら張り付いてるからって、ね。 84 名前：78 mailto:sage [2008/02/02(土) 06:55:22 ] >>61のソースの所在教えてくれ パクる 85 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/02/02(土) 07:20:15 ] dSFMTだったごめん。 nct.brain.riken.jp/~takekawa/softwares.xhtml あとこんなのもあった。 charles.karney.info/random/ 86 名前：デフォルトの名無しさん mailto:sage [2008/02/03(日) 13:34:07 ] thx 87 名前：デフォルトの名無しさん mailto:sage [2008/02/03(日) 13:46:53 ] ダンゴさんはSSEネタには造詣が深いな。 88 名前：デフォルトの名無しさん [2008/02/03(日) 16:46:36 ] じゃあ上げとこ 89 名前：デフォルトの名無しさん [2008/02/22(金) 20:01:38 ] シミュ板、数学板に乱数スレ発見。 乱数 science6.2ch.net/test/read.cgi/sim/1100375806/ 乱数の生成方法を必死になって考えるスレ　 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 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/03/28(金) 03:02:22 ] >>95 そのWEBページのURL教えてくれ 97 名前：95 mailto:sage [2008/03/28(金) 23:26:21 ] >>96 個人のブログですが、確かここだったと思います。 ttp://d.hatena.ne.jp/Isoparametric/20070830/1188462129 今、改めて読んでみると、よく意味分からん・・・ 98 名前：デフォルトの名無しさん mailto:sage [2008/03/28(金) 23:55:04 ] たった100回回しただけなら偏りも出るだろう 99 名前：デフォルトの名無しさん mailto:sage [2008/04/15(火) 04:27:31 ] はぐれめたるは捕まえられますか？ 100 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 03:21:30 ] >>99 むり 101 名前：デフォルトの名無しさん mailto:sage [2008/04/20(日) 18:00:50 ] 単純に何の補正も無い相手に対して「捕まえられる」確率はどのくらいか。 そしてはぐれメタルが逃げない確率はどのくらいか。 その両方のデータをくれ。 102 名前：デフォルトの名無しさん mailto:sage [2008/04/20(日) 19:05:05 ] 乱数とどういう関係があるんだ 103 名前：デフォルトの名無しさん mailto:sage [2008/04/20(日) 23:27:07 ] え？はぐれメタルの行動を決めている乱数テーブルの解析の話じゃないの！？ 104 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 00:54:50 ] ここは「擬似乱数生成アルゴリズム」に関する議論のスレッドだ 105 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/04/21(月) 13:20:43 ] PS2のドラクエ５では壁の衝突回数をカウントして乱数列の初期化してるようだ。 オラクルベリーの教会から一度も壁に衝突せずにカジノのスロットに直行すると 全く同じパターンが出てくるとか。 おそらくはぐれメタル捕獲にも何らかのパターンがあるかと 106 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 08:14:14 ] 全然ちげーよ、ばかが 107 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 12:16:04 ] 「ヽ・´∀｀・,,）っ━━━━━━┓」は放置推奨クソコテ 108 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/05/03(土) 21:01:47 ] >>105 www.astr.tohoku.ac.jp/~ajiki/cheap_restaurant/GAME/SAGA2/saga2rand.html サガ2の乱数発生器 DQ5もソース見れば多分判ると思うよ 110 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/05/19(月) 09:17:00 ] まとめ乙 112 名前：デフォルトの名無しさん [2008/08/06(水) 01:14:02 ] 保守 113 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 20:00:17 ] M系列という単語を見かけたので、理解してないまま保守リンク pc11.2ch.net/test/read.cgi/tech/1158367586/751- 114 名前：デフォルトの名無しさん mailto:sage [2008/08/11(月) 14:05:33 ] VBAで、dll使わずに高機能な乱数を実装する方法はないですか？ XorShiftを使うには、長桁計算しかないですか？ 115 名前：デフォルトの名無しさん mailto:sage [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 mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/08/18(月) 18:18:26 ] >>116 １１４です、ありがとうございます。32bitのXorShiftですね。 で、周期の途中から乱数を取り出して使いたいのですが、 x,y,z,wの初期値を乱数で設定するのに、デフォルトのrnd()を使ったら無意味ですよね。 118 名前：デフォルトの名無しさん mailto:sage [2008/08/19(火) 00:23:17 ] >>75あたりか 119 名前：115 mailto:sage [2008/08/22(金) 21:40:15 ] '種を使って初期化できます。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 120 名前：デフォルトの名無しさん mailto:sage [2008/08/22(金) 23:22:43 ] xorshiftって周期とか分布の保証ってあるの？ もしないならM系列の方がましだと思うんだけど。 ググれば長周期の多項式も見つかるし。 121 名前：デフォルトの名無しさん mailto:sage [2008/08/23(土) 01:50:28 ] 劣化Ｍ系列と理解してるが 122 名前：デフォルトの名無しさん mailto:sage [2008/08/23(土) 02:50:13 ] 早くて軽くてrandよりマシ 123 名前：デフォルトの名無しさん mailto:sage [2008/08/25(月) 16:31:11 ] >>119 excelVBAじゃ初期化するための種が結局16bitしかないんだから Xorshiftの種も16bit種類しかなくならね？ 124 名前：119 mailto:sage [2008/08/27(水) 03:32:41 ] 種 s は Long なので32bit種類あるが、負の場合は試してないので実質31bit種類。 125 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 10:43:09 ] VBAのRandomizeが16bit種類 それを使って初期化後rnd()で取得できる乱数も16bit種類 XorShiftの種にそれらを使うのなら結局系列は16bit種類 本当の最初の最初に32bitの乱数をセットするときにどうすればいいのか。 32bitのランダムな位置からXorShiftを開始するのに、そのうちの16bit分しか設定できない。 126 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 10:56:10 ] よく分からんが服を買いにいく服がない状態か 127 名前：119 mailto:sage [2008/08/27(水) 14:14:51 ] >>125 確かにそうだ。困ったもんだ。 128 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 14:18:21 ] >>125 GetTickCountとかCryptGenRandomとかWin32APIに頼ればいいじゃない。 129 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 12:44:39 ] >>128 とりあえず Private Declare Function GetTickCount Lib "kernel32" () As Long 後に 　　GetTickCountを使って取得するようにしたよ。 130 名前：,,・´∀`・,,）っ-○●◎ mailto:sage [2008/09/15(月) 02:50:11 ] 暇だったからSFMTのC++ template実装やってみた tripper.kousaku.in/20080914.html 131 名前：デフォルトの名無しさん mailto:sage [2008/09/15(月) 11:02:02 ] GJ！ 前スレからずっと待ってました 132 名前：デフォルトの名無しさん mailto:sage [2008/09/15(月) 11:05:17 ] あ、なんだ TR1対応じゃなくて純粋にテンプレート版なのか 133 名前：,,・´∀｀・,,）っ mailto:sage [2008/09/15(月) 14:24:14 ] そのうちBoost風に作り替える予定 134 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 23:55:19 ] 乱数って巻き戻しできないの？ 135 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 10:24:14 ] >>134 乱数の巻き戻しって何? 136 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:00:52 ] 予想すると あるシードでのn番めの乱数を出したあとに、n-1番目の乱数を 定数時でだせないか？ ってことでは 137 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:01:59 ] >>136 そのとおりでございやす 138 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:09:45 ] n-1番めからn番めを求める計算がたいてい非可逆だから無理 139 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:59:05 ] 巻き戻す必要がある数分だけ乱数の結果を保存するしかないだろうなぁ 140 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 19:03:50 ] XorShift ならちょっと考えればわかる。 線形合同法なら 2^{31}-1 だけ進めた x=Ax+C の A と C を求めれば可能。 メルセンヌツイスタやWELLなら www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf の方法で周期よりも一つ少ないところへジャンプすれば不可能ではないはず。 141 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 21:13:31 ] これって読み捨てるのと比べてどのぐらい高速？ MTの先頭の何百万個か読み捨てる処理に使えそう？ 142 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 21:22:53 ] 何百万よりは速いだろうが、100程度なら大差ない。 と、コード見ないで言ってみる 143 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 17:39:27 ] flashのActionScriptの乱数Math.randomって何bit？ 144 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 22:19:58 ] 25くらい 145 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [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　とつげき東北　 www.interq.or.jp/snake/totugeki/hdrand.htm 149 名前：デフォルトの名無しさん [2008/10/22(水) 21:24:52 ] でもメモリが余ってるときに均一に分布したとしても一杯になったら悪くなるかも試練ね 150 名前：デフォルトの名無しさん mailto:age [2008/10/22(水) 21:30:57 ] >>147 時には極端に偏ってくれないと真の乱数とはいえないな。 151 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:39:34 ] Unix の /dev/random は、デバイスドライバからそういう真の乱数を 生成するようなタイミングの情報をもらってデータを生成しているのだが... 152 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:41:38 ] 実行時まで偏ってるかどうかすら分からんから実用的には疑問だけどな。 違うハードの組み合わせで似たようなシードが繰り返し出てしまう可能性も否定出来ん。 特性が誰にも分からんから乱数としてもいいだろうって発想は学問的ではないな。 153 名前：デフォルトの名無しさん [2008/10/22(水) 21:45:17 ] 元手にするだけで、そのまま使うはず無いだろ。 たとえば、メモリ確保と読み書きした間隔が 1ナノ秒から100ナノ秒に分布しても偏りはでる。 そこは適切に処理して良い具合にする 154 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:39:08 ] メモリの読み書きレイテンシがどういう条件で決まるかわかって言ってるか？ 155 名前：デフォルトの名無しさん [2008/11/03(月) 16:36:49 ] srand(0)とsrand(1)はその処理系でも同じ系列を生成するのですか？ 156 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 17:29:47 ] その処理系て？ 157 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 17:45:50 ] なんだろね？ ところでシードに関して系列という単語がよく出るけど違和感が… 乱数アルゴリズムの多くはシードは開始位置を決めるだけで 同じ乱数列を参照してるんだよね。 イメージ的には馬鹿でかい時計のようなものがあって、 秒針よりももっともっと小さい針が数字を拾ってる感じ。 系列という言葉だとそれぞれが全く違う乱数列のように聞こえる。 まあ現実的には2^128くらいあれば被ることはないと思うけどさ。 なんか気になる。 158 名前：155 mailto:sage [2008/11/03(月) 17:52:33 ] まちがえました。 「その処理系でも」→「他の処理系でも」 でした。 159 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 17:59:04 ] srandはアルゴリズムからしてライブラリの実装次第だから 処理系以前に互換性はないと思え。 そもそもrand自体0からRAND_MAXまでの整数を出力するとかそういう定義しかないはず。 確かMTはその辺しっかりしていて、どこでも同じ結果が得られたはず。 160 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 19:41:28 ] >>157 rand() を実装するために使用する手法がいろいろあり、たとえば線形合同法・Ｍ系列・メルセンヌツイスタなどと呼ばれるものでしょうね。 手法とパラメータさえ同一であれば、当然同じ乱数列が生成されますが、rand()/srand() がどのように実装されているか、明確に 定義されているわけではないので、なんともいいようがないですね。 161 名前：デフォルトの名無しさん [2008/11/05(水) 19:25:05 ] >>148 >MTのような、周期の長い良質な擬似乱数の種としてこれを使えば、暗号ツールなどに実用的に応用できる。 MTのような暗号的に安全ではない擬似乱数の種に、暗号的に安全な乱数 を使っても出力は暗号的に安全ではないよな？ この記述はおかしいよな？ 162 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2008/11/28(金) 09:42:11 ] そりゃすげぇ 真の乱数で試してみたら？　スレ違いだけど... 165 名前：デフォルトの名無しさん mailto:sage [2008/11/28(金) 11:42:49 ] 真の乱数も試したけど駄目だった。 なんかp valueの分布が高いほうに偏ってる。 166 名前：デフォルトの名無しさん mailto:sage [2008/11/30(日) 14:12:53 ] ffmpegで有名なMichael Niedermayerさんの記事 Pseudo random number generators guru.multimedia.cx/pseudo-random-number-generators/ Pseudo random number generators 2 guru.multimedia.cx/pseudo-random-number-generators-2/ 167 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 13:48:27 ] 再現可能な擬似乱数じゃないけど、こんなんみつけた ハードウェア乱数生成ルーチンhdrand.c www.interq.or.jp/snake/totugeki/hdrand.htm 168 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 13:49:11 ] 概要をコピペ > テンポラリファイルフォルダにファイルを作成・削除し、その処理にかかった時間 > を高分解能パフォーマンスカウンタで計測して、処理時間を得る。 > 処理時間のビット列のうち、偏らないビットを乱数ビットとして利用する。 > ハードディスクのシーク時間や物理的な書き込み速度は、キャッシュや温度や湿度や > Windowsの処理順などによってばらつきがあるので、良質なランダムビットがとれる。 > 測定されるビットの変化を最初にテストしておくことで（100回のビット発生で、 > 充分に変化が見られたビットだけを乱数に使用する）、処理速度の違いや、パフォーマンスカウンタの質の悪さ（例えば最下位ビットが必ず偶数や奇数になる可能性）も吸収できる。 169 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 15:42:33 ] WindowsってOSにこのてのメカニズム持ってないのか？ 170 名前：デフォルトの名無しさん [2009/01/05(月) 17:21:26 ] ん、こういうの俺も昔遊びで作った事がある。 171 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 23:24:02 ] SFMTをExcelで使うなら、シード値ってどうやりゃいい？ sgenrand Timer * 1000 なんてのがどっかにあったが、なんかいまいちだよな。 172 名前：デフォルトの名無しさん mailto:sage [2009/01/06(火) 00:12:34 ] >>169 ハードウェア使った処理が含まれているかどうかは分からないけど、 暗号論的に安全なのが欲しければ、CryptGenRandom使えということになっている。 173 名前：デフォルトの名無しさん mailto:sage [2009/03/09(月) 06:06:19 ] >>166の続き。ffmpegではMT (Mersene twister)の質が悪く遅いということで非推奨(deprecated)にされました。質が良いのを使いたいならMLFGやKISS99を使えとのこと。 lists.mplayerhq.hu/pipermail/ffmpeg-cvslog/2009-March/021108.html 174 名前：デフォルトの名無しさん mailto:sage [2009/03/09(月) 20:38:50 ] 何が問題なんだろ。 松本さんの実装は、内部状態が1周した時に一斉に計算するようになってるので、 負荷が一定しないよなぁとは思うんだが、そういうとこじゃなくて、原理的に問題が ある、っつってんだよね。 遅いというのは、はあそうですか、というだけなんだけど、blogのほう見ると、 XOR だけで構成されている、ってことをdisってるように見えるんだが... 175 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/09(月) 20:41:31 ] KISS99もシンプルだし悪くはないんだが 176 名前：デフォルトの名無しさん mailto:sage [2009/03/10(火) 00:23:48 ] >>174 ブログで参照しているこのペーパーにあるMT19937のテスト結果がCrash 2回、BigCrash 2回になっているからだからだと思う。 www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf 誰か解説キボン 177 名前：デフォルトの名無しさん mailto:sage [2009/03/10(火) 00:55:31 ] どんなアルゴリズムであっても一周期において均等分布を達成するとなると 全てのビットパターンを発生させるという点で結局M系列と同じ事になるんだよな。 するとマクロではみんな十分にランダムということになるから、 あとはミクロでのランダムさとその実装方法からくる計算量が問題なわけだな。 そのあたりに何かあるんじゃなかろか。 178 名前：デフォルトの名無しさん mailto:sage [2009/03/10(火) 11:49:47 ] なんかその論文で提案してるテストでは、暗号学的な強度のあるジェネレータ以外は のきなみパーフェクトでない結果を出してるみたいだ。 MTの成績が際立って悪いとかそういう結果ではないけど、ffmpegの作者的には 気になる結果なのかな？ 179 名前：デフォルトの名無しさん mailto:sage [2009/03/12(木) 22:15:08 ] 元々そちらの専門家みたい

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef