疑似乱数２ - 暇つぶし2ch

疑似乱数２ ..

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

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

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

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

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

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

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

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

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

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

145:デフォルトの名無しさん
08/09/29 11:00:47
MTならFORTRANだけど
URLﾘﾝｸ(www.math.sci.hiroshima-u.ac.jp)
この中に
revrand(): it generates prn in reverse order
って書いてあるけど

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

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

ハードウェア乱数生成ルーチンhdrand.c　　by　とつげき東北　
URLﾘﾝｸ(www.interq.or.jp)

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

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

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

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

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

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

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

156:デフォルトの名無しさん
08/11/03 17:29:47
その処理系て？

157:デフォルトの名無しさん
08/11/03 17:45:50
なんだろね？

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

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

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

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

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

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

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

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

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

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

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

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

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

166:デフォルトの名無しさん
08/11/30 14:12:53
ffmpegで有名なMichael Niedermayerさんの記事
Pseudo random number generators
URLﾘﾝｸ(guru.multimedia.cx)
Pseudo random number generators 2
URLﾘﾝｸ(guru.multimedia.cx)

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

ハードウェア乱数生成ルーチンhdrand.c
URLﾘﾝｸ(www.interq.or.jp)

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

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

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

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

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

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

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

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

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

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

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

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