疑似乱数２

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