疑似乱数２

1 名前：デフォルトの名無しさん [2007/10/17(水) 22:34:59 .net] 擬似乱数発生器について語ろうか。その２ 前スレ 擬似乱数 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 136 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 23:55:19 .net] 乱数って巻き戻しできないの？ 137 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 10:24:14 .net] >>134 乱数の巻き戻しって何? 138 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:00:52 .net] 予想すると あるシードでのn番めの乱数を出したあとに、n-1番目の乱数を 定数時でだせないか？ ってことでは 139 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:01:59 .net] >>136 そのとおりでございやす 140 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:09:45 .net] n-1番めからn番めを求める計算がたいてい非可逆だから無理 141 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 12:59:05 .net] 巻き戻す必要がある数分だけ乱数の結果を保存するしかないだろうなぁ 142 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 19:03:50 .net] XorShift ならちょっと考えればわかる。 線形合同法なら 2^{31}-1 だけ進めた x=Ax+C の A と C を求めれば可能。 メルセンヌツイスタやWELLなら www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf の方法で周期よりも一つ少ないところへジャンプすれば不可能ではないはず。 143 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 21:13:31 .net] これって読み捨てるのと比べてどのぐらい高速？ MTの先頭の何百万個か読み捨てる処理に使えそう？ 144 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 21:22:53 .net] 何百万よりは速いだろうが、100程度なら大差ない。 と、コード見ないで言ってみる 145 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 17:39:27 .net] flashのActionScriptの乱数Math.randomって何bit？ 146 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 22:19:58 .net] 25くらい 147 名前：デフォルトの名無しさん mailto:sage [2008/09/29(月) 11:00:47 .net] MTならFORTRANだけど ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/FORTRAN/fortran.html この中に revrand(): it generates prn in reverse order って書いてあるけど 148 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 13:52:49 .net] 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; } 149 名前：デフォルトの名無しさん [2008/10/22(水) 21:18:38 .net] とつげき東北とかいう人の乱数生成法を見て思いついたけど メモリを確保して、読み書きする速度を計測すれば真の乱数できそう。 もともとはハードディスクの読み書きだが。これだと生成に時間食う。 150 名前：デフォルトの名無しさん [2008/10/22(水) 21:20:08 .net] これね。 ハードウェア乱数生成ルーチンhdrand.c　　by　とつげき東北　 www.interq.or.jp/snake/totugeki/hdrand.htm 151 名前：デフォルトの名無しさん [2008/10/22(水) 21:24:52 .net] でもメモリが余ってるときに均一に分布したとしても一杯になったら悪くなるかも試練ね 152 名前：デフォルトの名無しさん mailto:age [2008/10/22(水) 21:30:57 .net] >>147 時には極端に偏ってくれないと真の乱数とはいえないな。 153 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:39:34 .net] Unix の /dev/random は、デバイスドライバからそういう真の乱数を 生成するようなタイミングの情報をもらってデータを生成しているのだが... 154 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:41:38 .net] 実行時まで偏ってるかどうかすら分からんから実用的には疑問だけどな。 違うハードの組み合わせで似たようなシードが繰り返し出てしまう可能性も否定出来ん。 特性が誰にも分からんから乱数としてもいいだろうって発想は学問的ではないな。 155 名前：デフォルトの名無しさん [2008/10/22(水) 21:45:17 .net] 元手にするだけで、そのまま使うはず無いだろ。 たとえば、メモリ確保と読み書きした間隔が 1ナノ秒から100ナノ秒に分布しても偏りはでる。 そこは適切に処理して良い具合にする 156 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:39:08 .net] メモリの読み書きレイテンシがどういう条件で決まるかわかって言ってるか？ 157 名前：デフォルトの名無しさん [2008/11/03(月) 16:36:49 .net] srand(0)とsrand(1)はその処理系でも同じ系列を生成するのですか？ 158 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 17:29:47 .net] その処理系て？ 159 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 17:45:50 .net] なんだろね？ ところでシードに関して系列という単語がよく出るけど違和感 160 名前：が… 乱数アルゴリズムの多くはシードは開始位置を決めるだけで 同じ乱数列を参照してるんだよね。 イメージ的には馬鹿でかい時計のようなものがあって、 秒針よりももっともっと小さい針が数字を拾ってる感じ。 系列という言葉だとそれぞれが全く違う乱数列のように聞こえる。 まあ現実的には2^128くらいあれば被ることはないと思うけどさ。 なんか気になる。 [] [ここ壊れてます] 161 名前：155 mailto:sage [2008/11/03(月) 17:52:33 .net] まちがえました。 「その処理系でも」→「他の処理系でも」 でした。 162 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 17:59:04 .net] srandはアルゴリズムからしてライブラリの実装次第だから 処理系以前に互換性はないと思え。 そもそもrand自体0からRAND_MAXまでの整数を出力するとかそういう定義しかないはず。 確かMTはその辺しっかりしていて、どこでも同じ結果が得られたはず。 163 名前：デフォルトの名無しさん mailto:sage [2008/11/03(月) 19:41:28 .net] >>157 rand() を実装するために使用する手法がいろいろあり、たとえば線形合同法・Ｍ系列・メルセンヌツイスタなどと呼ばれるものでしょうね。 手法とパラメータさえ同一であれば、当然同じ乱数列が生成されますが、rand()/srand() がどのように実装されているか、明確に 定義されているわけではないので、なんともいいようがないですね。 164 名前：デフォルトの名無しさん [2008/11/05(水) 19:25:05 .net] >>148 >MTのような、周期の長い良質な擬似乱数の種としてこれを使えば、暗号ツールなどに実用的に応用できる。 MTのような暗号的に安全ではない擬似乱数の種に、暗号的に安全な乱数 を使っても出力は暗号的に安全ではないよな？ この記述はおかしいよな？ 165 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 19:38:22 .net] いや。 暗号的に安全ではない乱数生成系を、暗号関係の目的で使用するには、 出力ストリームに一方向ハッシュ関数を噛ませる方法がある。 その時に、シードは予測不可能なものである必要がある。 166 名前：デフォルトの名無しさん [2008/11/27(木) 22:25:54 .net] NIST test 2.0bってどうなの? なんかDFTで必ず落とされるんだけど。 とりあえずMT19937, G using SHA-1, Micali-Schnorr試したけど駄目だった。 167 名前：デフォルトの名無しさん mailto:sage [2008/11/28(金) 09:42:11 .net] そりゃすげぇ 真の乱数で試してみたら？　スレ違いだけど... 168 名前：デフォルトの名無しさん mailto:sage [2008/11/28(金) 11:42:49 .net] 真の乱数も試したけど駄目だった。 なんかp valueの分布が高いほうに偏ってる。 169 名前：デフォルトの名無しさん mailto:sage [2008/11/30(日) 14:12:53 .net] 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/ 170 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 13:48:27 .net] 再現可能な擬似乱数じゃないけど、こんなんみつけた ハードウェア乱数生成ルーチンhdrand.c www.interq.or.jp/snake/totugeki/hdrand.htm 171 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 13:49:11 .net] 概要をコピペ > テンポラリファイルフォルダにファイルを作成・削除し、その処理にかかった時間 > を高分解能パフォーマンスカウンタで計測して、処理時間を得る。 > 処理時間のビット列のうち、偏らないビットを乱数ビットとして利用する。 > ハードディスクのシーク時間や物理的な書き込み速度は、キャッシュや温度や湿度や > Windowsの処理順などによってばらつきがあるので、良質なランダムビットがとれる。 > 測定されるビットの変化を最初にテストしておくことで（100回のビット発生で、 > 充分に変化が見られたビットだけを乱数に使用する）、処理速度の違いや、パフォーマンスカウンタの質の悪さ（例えば最下位ビットが必ず偶数や奇数になる可能性）も吸収できる。 172 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 15:42:33 .net] WindowsってOSにこのてのメカニズム持ってないのか？ 173 名前：デフォルトの名無しさん [2009/01/05(月) 17:21:26 .net] ん、こういうの俺も昔遊びで作った事がある。 174 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 23:24:02 .net] SFMTをExcelで使うなら、シード値ってどうやりゃいい？ sgenrand Timer * 1000 なんてのがどっかにあったが、なんかいまいちだよな。 175 名前：デフォルトの名無しさん mailto:sage [2009/01/06(火) 00:12:34 .net] >>169 ハードウェア使った処理が含まれているかどうかは分からないけど、 暗号論的に安全なのが欲しければ、CryptGenRandom使えということになっている。 176 名前：デフォルトの名無しさん mailto:sage [2009/03/09(月) 06:06:19 .net] >>166の続き。ffmpegではMT (Mersene twister)の質が悪く遅いということで非推奨(deprecated)にされました。質が良いのを使いたいならMLFGやKISS99を使えとのこと。 lists.mplayerhq.hu/pipermail/ffmpeg-cvslog/2009-March/021108.html 177 名前：デフォルトの名無しさん mailto:sage [2009/03/09(月) 20:38:50 .net] 何が問題なんだろ。 松本さんの実装は、内部状態が1周した時に一斉に計算するようになってるので、 負荷が一定しないよなぁとは思うんだが、そういうとこじゃなくて、原理的に問題が ある、っつってんだよね。 遅いというのは、はあそうですか、というだけなんだけど、blogのほう見ると、 XOR だけで構成されている、ってことをdisってるように見えるんだが... 178 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/09(月) 20:41:31 .net] KISS99もシンプルだし悪くはないんだが 179 名前：デフォルトの名無しさん mailto:sage [2009/03/10(火) 00:23:48 .net] >>174 ブログで参照しているこのペーパーにあるMT19937のテスト結果がCrash 2回、BigCrash 2回になっているからだからだと思う。 www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf 誰か解説キボン 180 名前：デフォルトの名無しさん mailto:sage [2009/03/10(火) 00:55:31 .net] どんなアルゴリズムであっても一周期において均等分布を達成するとなると 全てのビットパターンを発生させるという点で結局M系列と同じ事になるんだよな。 するとマクロではみんな十分にランダムということになるから、 あとはミクロでのランダムさとその実装方法からくる計算量が問題なわけだな。 そのあたりに何かあるんじゃなかろか。 181 名前：デフォルトの名無しさん mailto:sage [2009/03/10(火) 11:49:47 .net] なんかその論文で提案してるテストでは、暗号学的な強度のあるジェネレータ以外は のきなみパーフェクトでない結果を出してるみたいだ。 MTの成績が際立って悪いとかそういう結果ではないけど、ffmpegの作者的には 気になる結果なのかな？ 182 名前：デフォルトの名無しさん mailto:sage [2009/03/12(木) 22:15:08 .net] 元々そちらの専門家みたい 183 名前：デフォルトの名無しさん mailto:sage [2009/04/17(金) 14:38:32 .net] ダメ 184 名前：デフォルトの名無しさん mailto:sage [2009/06/20(土) 20:18:13 .net] 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 groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a4424068/ *6 groups.google.com/group/sci.crypt/browse_thread/thread/305c507efbe85be4 185 名前：デフォルトの名無しさん mailto:sage [2009/06/20(土) 20:20:22 .net] スワヒリ語でおｋ 186 名前：デフォルトの名無しさん mailto:sage [2009/06/20(土) 20:54:53 ] [ここ壊れてます] 187 名前： .net mailto: なんか見覚えある名前だなーと思ったらXorshiftの人だったか [] [ここ壊れてます] 188 名前：デフォルトの名無しさん [2009/08/11(火) 03:30:02 .net] あげ 189 名前：デフォルトの名無しさん mailto:sage [2009/08/11(火) 13:07:46 .net] 次は185が出てくる 190 名前：デフォルトの名無しさん [2009/08/14(金) 01:57:19 .net] お初ですが質問させてください。 現在sfmtについて作成者のHPにあるプログラムを見て勉強しています。 そこで64bitでシフトしてる部分があって、unsigned long long等が対応していないコンパイラでやる場合(32bitまでしかない)、何かいい方法はありますか？ 自力で32bitでシフトしてもいいのですが… 初心者なので意味不明な説明かもしれませんが、参考になる方法やHP等ありましたら教えてください。 191 名前：デフォルトの名無しさん mailto:sage [2009/08/14(金) 02:06:20 .net] そこだけ__asm { } でインラインアセンブラで書くとか 192 名前：デフォルトの名無しさん mailto:sage [2009/08/14(金) 08:53:55 .net] int64が無いコンパイラだとasmも無さそうな 193 名前：デフォルトの名無しさん mailto:sage [2009/08/14(金) 09:37:58 .net] >>186 具体的なロジックを出さないと、曖昧なレスしかつかないよ。 194 名前：デフォルトの名無しさん [2009/08/14(金) 13:23:06 .net] 186です。 さっそくの返信ありがとうございます。 一応必要な部分だけアセンブラで書くことも可能だったと思いました。ただ現在携帯からの書き込みでキツいので、あとでまた書きます。 195 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/08/15(土) 09:25:55 .net] >>186 ないから自力でやれ 196 名前：デフォルトの名無しさん [2009/08/15(土) 20:24:26 .net] どなたかご教示願います。 lehmerの線型合同法で作成される乱数値は、 初期値が同じでも計算機環境の違いにより変わることはありますか？ 197 名前：デフォルトの名無しさん [2009/08/16(日) 02:20:18 .net] うん 198 名前：デフォルトの名無しさん mailto:sage [2009/08/16(日) 08:03:39 .net] 同じ数式を計算したのに計算機環境の違いで結果が変わることがあると思う？ 199 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/08/16(日) 08:23:56 .net] 浮動小数ならよくある 200 名前：デフォルトの名無しさん mailto:sage [2009/08/16(日) 08:28:53 .net] >>> (2 / 3) * 6 0 >>> 6 * 2 / 3 4 201 名前：192 [2009/08/16(日) 11:13:06 .net] >>193>>195>>196 ありがとうございました。 202 名前：デフォルトの名無しさん mailto:sage [2009/08/17(月) 10:39:10 .net] >>196 それらは「同じ数式」といえるのか? 203 名前：デフォルトの名無しさん mailto:sage [2009/08/17(月) 13:04:38 .net] >>194 有効桁数をちゃんと制御して、その動作が保証されている言語を使うなら、 バグでない限り有効桁数の範囲で変わることはない。 ただ同じ数式の同一の変数に別の値を与えたのなら変わってもおかしくないよ。 つかそれ以前に疑似乱数に関係あるのかｗ 204 名前：デフォルトの名無しさん [2009/09/03(木) 21:52:50 .net] 高次元均等分布性ってどういうこと？ p[i]=(x[Ni+0],x[Ni+1],…,x[Ni+N-1]) として作ったＮ次元乱数のＮ次元空間上散布図が Ｎ次元空間内に平面作ったり偏ったりせずにぼんやり分布することと考えていいのかな？ 205 名前：デフォルトの名無しさん mailto:sage [2009/09/04(金) 07:05:22 .net] 誤解を恐れずに大雑把かつ簡単に言うと、 nビットの状態空間があるとして、 一周期の間に00...00から11...11までnビット(n桁)の数字が 過不足なく1回ずつ出現すること。 それが満たされると周期全体で直前のn-1ビットの状態に関わらず 次の1ビットの出現確立が必ず50:50になる。 つまりn-1次元で0と1が均等に分布したことになる。 状態空間を越えた次元では分布については全く保証出来ない。 だからMT含めて最近の擬似乱数はみんな状態空間をかなり大きめにとってる。 ただしこれはあくまで一周期のことであって、 一周期の一部を切り出した場合(通常の使用状況)では全然話が別ね。 マクロとミクロの違いというか両方同時に成り立たせるのは難しい。 よく0過多状態からの回復の速さが注目されるけど、 状態空間が大きいのに三項式とかだと(MTのことね) 0の多い区間はその前後でも0が多くなる。 逆に1の多い区間はその前後で1が多くなってトータルで均等になるわけさ。 206 名前：デフォルトの名無しさん [2009/10/04(日) 07:32:06 .net] 一月あげ 207 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 10:51:02 .net] unko 208 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 15:32:33 .net] Blum-Blum-Shub のC/C++ の実装コードが掲示されているサイトを知ってる人いませんか？ java での実装例はここにあるんですが code.google.com/p/javarng/ 209 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 18:00:56 .net] 1+1=2 210 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 18:22:02 .net] >>204 BlumBlumShub.java を C/C++ に書き換えるだけじゃだめなん？ 211 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 18:34:10 .net] C/C++ に BigInteger の標準的な代替物でもあれば楽勝だろうけど 212 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 18:55:46 .net] blumblum.c とfreelip いうファイルを見つけ www.mindspring.com/~pate/crypto/chap05/blumblum.c math.arizona.edu/~aprl/math/comp/bigint/ blumblum.c をgcc (GCC) 4.2.4 でコンパイルするのですが zcopy とか、zfree とか、zなんとかという命令がコンパイルできなくて詰まっています。 何なんだこのz何とかというコマンドは？cの命令セットにはないぞ、posix かなんかの命令セットなのか？ 213 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 19:01:35 .net] >>204、>>208です皆さんサンクスです。 >>207 その通りです、java からの移植はBigInteger を見て、ライブラリから作る羽目になりそうだったので 速攻あきらめました。boost にBlumBlumShubがあればいいのにな・・・・ 214 名前：デフォルトの名無しさん mailto:sage [2009/10/06(火) 00:46:53 .net] >208 C/C++ ではコマンドとか命令とか命令セットとは言わないだろう、普通。 命令セットって言われたら CPU の instruction set を思い浮かべるわ。 で、freelip ってのの中に z* 入ってるじゃん。 C/C++ の分割コンパイルに詰まってるんだろうけど、とりあえず gcc -o blumblum blumblum.c lip.c とかで実行ファイルできない？ あと、boost vault には bigint が有ったような。使いものになるかしらんけど。 215 名前：デフォルトの名無しさん mailto:sage [2009/10/06(火) 22:41:31 .net] >210 gcc -o blumblum blumblum.c lip.c このオペレーションも上手くいかない・・・orz 216 名前：デフォルトの名無しさん mailto:sage [2009/10/06(火) 23:27:47 .net] 今度はオペレーションて 217 名前：デフォルトの名無しさん mailto:sage [2009/10/07(水) 06:28:55 .net] >>209 gmp じゃだめ？ 218 名前：デフォルトの名無しさん mailto:sage [2009/10/07(水) 08:53:51 .net] どういうエラーが出てるのか書かなきゃ対処しようもないぞ 219 名前：デフォルトの名無しさん [2009/11/14(土) 09:37:55 .net] xorshiftをunsigned longではなく32bit intの範囲内でやる方法はありませんか？ 220 名前：デフォルトの名無しさん mailto:sage [2009/11/14(土) 16:45:06 .net] complementary multiply-with-carry ってのが 周期長くて計算軽いってのは分かったけど 高次元での均等性はどうなの？ MTだと623個の組で使っても大丈夫ということだけど 221 名前：デフォルトの名無しさん [2009/11/14(土) 19:33:47 .net] RC4が最強だろ 222 名前：デフォルトの名無しさん mailto:sage [2009/11/15(日) 00:29:33 .net] >>215 符号無しの整数型が存在しない言語で実装しようとしているのか？ 例えば、Javaとかだと符号付き整数型でも気にせずビット演算して大丈夫のはずなんだけど。 もう1つ、そのunsigned longはおそらく32ビットだと思う。コードを注意してみて。 違ったとしてもググれば32ビット符号無し整数(unsigned intだかunsigned longだか)での実装はすぐ見つかると思う。 223 名前：デフォルトの名無しさん mailto:sage [2009/11/18(水) 19:08:23 .net] 最近できた疑似乱数をまとめたサイトとかない？ 224 名前：デフォルトの名無しさん mailto:sage [2009/12/05(土) 08:22:52 .net] 起動戦士ランダム♪ランダム♪ 225 名前：デフォルトの名無しさん mailto:sage [2009/12/05(土) 11:36:41 .net] 俺がランダムだ 226 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 13:19:31 .net] シェーダ/GPGPU向けでよい疑似乱数ってどんなのがあるでしょうか。 数列系の疑似乱数を直に使うことが出来ないのでいろいろ考えています。 227 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 14:30:20 .net] もっと具体的に書かないと分からん メモリアクセスが厳しいとかそういう話か？ 228 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 14:35:46 .net] もう一つ >数列系の疑似乱数 擬似乱数はみんな数列だぞ 229 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 14:42:46 .net] ワーキングセットが小さい、って意味か？ 確かにMTは比較的大きいが。 230 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 15:01:10 .net] アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。 その際、2次元画面*時間の3次元で相関などがなく一様分布するノイズにしたいのです。 画素ごとに並列に計算できれば高速に計算できることは分かっているのですが、 数列を使う以上は基本的に一つずつ取り出すしかなく並列化できません。 そのため、並列計算で生成できる疑似乱数生成法がないかと探しているところです。 一応全画素に32バイト割り当てればそれぞれXorShiftの系列が張り付けられるかなとは考えましたが、 やはりちょっとワーキングセットが大きくなるのと、 XorShiftの系列間相関の有無がよくわからず、躊躇しています。 自分で実装しなければならないなら、各画素の計算では、画素の座標（各座標に固有だが相関たっぷり）と、 フレームごとに全部画素一律に参照できるベクトルを与えることができるので、 それをうまく使って乱数列の系列の途中の値をうまく与えられないかなあ、などと考えています。 231 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 15:22:14 .net] プールして切り出し 232 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 15:33:08 .net] xyz全部に相関なしか…そいつぁ難しいぜ とりあえず画素毎に独立した個別の乱数を充てるのはダメだな 少なくとも画素以上の状態空間を持った乱数を用意しないと相関なしには出来ないんだぜ 適当に作っても任意の画素間で相関がないことを保証できないだろ？ そもそも同じ生成式を使えば初期値が違うだけで結局同じ乱数列しか得られないからな とまあ大げさに書いたけど、本気で3次元完全無相関を目指してるわけじゃないよね？ 落としどころとしてはMTとか周期の長い乱数を使って 一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。 各画素はM系列とかXorShift?(いまいち信用できない)を使えばよろし。 233 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 20:32:23 .net] 遅れまして申し訳ありません。 >>228 勉強になります。 一瞬、隣の画素の状態を見ながらメルセンヌツイスタのように「捻れ」ないかと思いましたが、 結局そこでデータコヒーレンシーの問題で並列化できなそうなのでそれも無理そうですね 結構本気で3次元無相関を目指しているというか無相関であることが優先される用途なので、 現在は時間を仕切って有限の大きさにしてプールして切り出し、というのが現実的な解となっています。 ただ長時間やるにはメモリがいくらあっても不足するような感じなので、 なんとか生成できないかなあと思う次第です。 副産物として、落としどころとしてそれっぽいものを作ることは吝かでもないですが。 234 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 21:37:19 .net] >>229 当然ながら精度と速度は両立しないんで、 どこまで必要なのか見極めて妥協することになるけど、 仮に1画素あたり32bitとして640*480なら、 最低でも1228800バイト以上の状態空間が必要だね。 これで1フレーム分だから残り何フレームまで必要なのか考えてみればいいよ。 >一瞬、隣の画素の状態を見ながらメルセンヌツイスタのように「捻れ」ないかと思いましたが、 MTの「捻り」はGFSRの短かった周期を理論値まで伸ばしてるだけ。 無闇に隣を参照したらダメだよ。 235 名前：デフォルトの名無しさん mailto:sage [2010/01/08(金) 23:07:46 .net] >>230 ありがとうございます。 まずはM系列からということでググったり本棚をあさったりしていたのですが、 疑似乱数を作るということは、どういう遍歴をたどる数列を設計するかという話だ、ということが改めて身にしみました。 また、正しく「捻る」にはビットの遍歴が最長となるよう正しくビット間の周回コースを繋がなければならない、という理解でいいのでしょうか。 ＞ 落としどころとしてはMTとか周期の長い乱数を使って ＞ 一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。 という話は、最初見たとき手抜き実装かなと思ってしまったりしたのですが、 冷静に考えるとCPU側とGPU側の状態は両方とも完全に決定可能なのだから、 周期や分布もちゃんと計算できるのですね。 この方法が自分の目的にとっては王道のような気がしてきました。 まったく不勉強で疑似乱数の世界の入場門がどこにあるかがやっとわかった状態ですが、 道筋がなんとなく見えてきたので、次に質問する前に、もっと自分で勉強してみたいと思います。 素人の思いつきに懇切丁寧にご回答いただきありがとうございました。 236 名前：デフォルトの名無しさん mailto:sage [2010/01/09(土) 12:02:20 .net] >>228 こういう用途なら、単純に１次元化して、正規乱数を利用すればいいんじゃないの？

---

---

[ 続きを読む ] / [ 携帯版 ]

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