- 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
- 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 ]
- 元々そちらの専門家みたい
|
 |
