疑似乱数２

**デフォルトの名無しさん** · 2007/10/17(水) 22:34:59

擬似乱数発生器について語ろうか。その２

前スレ
擬似乱数
http://pc11.2ch.net/test/read.cgi/tech/1146071975/

関連スレ
【危険】とんでもプログラム告発スレッド【悪質】
http://pc11.2ch.net/test/read.cgi/tech/1191860116/

SIMD-oriented Fast Mersenne Twister (SFMT):
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html

**デフォルトの名無しさん** · 2008/09/17(水) 12:01:59

>>136
そのとおりでございやす

**デフォルトの名無しさん** · 2008/09/17(水) 12:09:45

n-1番めからn番めを求める計算がたいてい非可逆だから無理

**デフォルトの名無しさん** · 2008/09/17(水) 12:59:05

巻き戻す必要がある数分だけ乱数の結果を保存するしかないだろうなぁ

**デフォルトの名無しさん** · 2008/09/17(水) 19:03:50

XorShift ならちょっと考えればわかる。
線形合同法なら 2^{31}-1 だけ進めた x=Ax+C の A と C を求めれば可能。
メルセンヌツイスタやWELLなら
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf
の方法で周期よりも一つ少ないところへジャンプすれば不可能ではないはず。

**デフォルトの名無しさん** · 2008/09/17(水) 21:13:31

これって読み捨てるのと比べてどのぐらい高速？
MTの先頭の何百万個か読み捨てる処理に使えそう？

**デフォルトの名無しさん** · 2008/09/17(水) 21:22:53

何百万よりは速いだろうが、100程度なら大差ない。

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

**デフォルトの名無しさん** · 2008/09/25(木) 17:39:27

flashのActionScriptの乱数Math.randomって何bit？

**デフォルトの名無しさん** · 2008/09/25(木) 22:19:58

25くらい

**デフォルトの名無しさん** · 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
って書いてあるけど

**デフォルトの名無しさん** · 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;
}

**デフォルトの名無しさん** · 2008/10/22(水) 21:18:38

とつげき東北とかいう人の乱数生成法を見て思いついたけど
メモリを確保して、読み書きする速度を計測すれば真の乱数できそう。
もともとはハードディスクの読み書きだが。これだと生成に時間食う。

**デフォルトの名無しさん** · 2008/10/22(水) 21:20:08

これね。

ハードウェア乱数生成ルーチンhdrand.c　　by　とつげき東北　
http://www.interq.or.jp/snake/totugeki/hdrand.htm

**デフォルトの名無しさん** · 2008/10/22(水) 21:24:52

でもメモリが余ってるときに均一に分布したとしても一杯になったら悪くなるかも試練ね

**デフォルトの名無しさん** · 2008/10/22(水) 21:30:57

>>147
時には極端に偏ってくれないと真の乱数とはいえないな。

**デフォルトの名無しさん** · 2008/10/22(水) 21:39:34

Unix の /dev/random は、デバイスドライバからそういう真の乱数を
生成するようなタイミングの情報をもらってデータを生成しているのだが...

**デフォルトの名無しさん** · 2008/10/22(水) 21:41:38

実行時まで偏ってるかどうかすら分からんから実用的には疑問だけどな。
違うハードの組み合わせで似たようなシードが繰り返し出てしまう可能性も否定出来ん。
特性が誰にも分からんから乱数としてもいいだろうって発想は学問的ではないな。

**デフォルトの名無しさん** · 2008/10/22(水) 21:45:17

元手にするだけで、そのまま使うはず無いだろ。
たとえば、メモリ確保と読み書きした間隔が
1ナノ秒から100ナノ秒に分布しても偏りはでる。
そこは適切に処理して良い具合にする

**デフォルトの名無しさん** · 2008/10/23(木) 00:39:08

メモリの読み書きレイテンシがどういう条件で決まるかわかって言ってるか？

**デフォルトの名無しさん** · 2008/11/03(月) 16:36:49

srand(0)とsrand(1)はその処理系でも同じ系列を生成するのですか？

**デフォルトの名無しさん** · 2008/11/03(月) 17:29:47

その処理系て？

**デフォルトの名無しさん** · 2008/11/03(月) 17:45:50

なんだろね？

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

**155** · 2008/11/03(月) 17:52:33

まちがえました。
「その処理系でも」→「他の処理系でも」
でした。

**デフォルトの名無しさん** · 2008/11/03(月) 17:59:04

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

**デフォルトの名無しさん** · 2008/11/03(月) 19:41:28

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

**デフォルトの名無しさん** · 2008/11/05(水) 19:25:05

>>148
>MTのような、周期の長い良質な擬似乱数の種としてこれを使えば、暗号ツールなどに実用的に応用できる。

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

**デフォルトの名無しさん** · 2008/11/05(水) 19:38:22

いや。

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

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

**デフォルトの名無しさん** · 2008/11/27(木) 22:25:54

NIST test 2.0bってどうなの?

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

**デフォルトの名無しさん** · 2008/11/28(金) 09:42:11

そりゃすげぇ
真の乱数で試してみたら？　スレ違いだけど...

**デフォルトの名無しさん** · 2008/11/28(金) 11:42:49

真の乱数も試したけど駄目だった。
なんかp valueの分布が高いほうに偏ってる。

**デフォルトの名無しさん** · 2008/11/30(日) 14:12:53

ffmpegで有名なMichael Niedermayerさんの記事
Pseudo random number generators
http://guru.multimedia.cx/pseudo-random-number-generators/
Pseudo random number generators 2
http://guru.multimedia.cx/pseudo-random-number-generators-2/

**デフォルトの名無しさん** · 2009/01/05(月) 13:48:27

再現可能な擬似乱数じゃないけど、こんなんみつけた

ハードウェア乱数生成ルーチンhdrand.c
http://www.interq.or.jp/snake/totugeki/hdrand.htm

**デフォルトの名無しさん** · 2009/01/05(月) 13:49:11

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

**デフォルトの名無しさん** · 2009/01/05(月) 15:42:33

WindowsってOSにこのてのメカニズム持ってないのか？

**デフォルトの名無しさん** · 2009/01/05(月) 17:21:26

ん、こういうの俺も昔遊びで作った事がある。

**デフォルトの名無しさん** · 2009/01/05(月) 23:24:02

SFMTをExcelで使うなら、シード値ってどうやりゃいい？
sgenrand Timer * 1000
なんてのがどっかにあったが、なんかいまいちだよな。

**デフォルトの名無しさん** · 2009/01/06(火) 00:12:34

>>169
ハードウェア使った処理が含まれているかどうかは分からないけど、
暗号論的に安全なのが欲しければ、CryptGenRandom使えということになっている。

**デフォルトの名無しさん** · 2009/03/09(月) 06:06:19

>>166の続き。ffmpegではMT (Mersene twister)の質が悪く遅いということで非推奨(deprecated)にされました。質が良いのを使いたいならMLFGやKISS99を使えとのこと。
http://lists.mplayerhq.hu/pipermail/ffmpeg-cvslog/2009-March/021108.html

**デフォルトの名無しさん** · 2009/03/09(月) 20:38:50

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

**,,・´∀｀・,,）っ-○◎●** · 2009/03/09(月) 20:41:31

KISS99もシンプルだし悪くはないんだが

**デフォルトの名無しさん** · 2009/03/10(火) 00:23:48

>>174
ブログで参照しているこのペーパーにあるMT19937のテスト結果がCrash 2回、BigCrash 2回になっているからだからだと思う。
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf
誰か解説キボン

**デフォルトの名無しさん** · 2009/03/10(火) 00:55:31

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

**デフォルトの名無しさん** · 2009/03/10(火) 11:49:47

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

**デフォルトの名無しさん** · 2009/03/12(木) 22:15:08

元々そちらの専門家みたい

**デフォルトの名無しさん** · 2009/04/17(金) 14:38:32

ダメ

**デフォルトの名無しさん** · 2009/06/20(土) 20:18:13

http://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 http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a4424068/
*6 http://groups.google.com/group/sci.crypt/browse_thread/thread/305c507efbe85be4

**デフォルトの名無しさん** · 2009/06/20(土) 20:20:22

スワヒリ語でおｋ

**デフォルトの名無しさん** · 2009/06/20(土) 20:54:53

なんか見覚えある名前だなーと思ったらXorshiftの人だったか

**デフォルトの名無しさん** · 2009/08/11(火) 03:30:02

あげ

**デフォルトの名無しさん** · 2009/08/11(火) 13:07:46

次は185が出てくる

**デフォルトの名無しさん** · 2009/08/14(金) 01:57:19

お初ですが質問させてください。

現在sfmtについて作成者のHPにあるプログラムを見て勉強しています。

そこで64bitでシフトしてる部分があって、unsigned long long等が対応していないコンパイラでやる場合(32bitまでしかない)、何かいい方法はありますか？
自力で32bitでシフトしてもいいのですが…

初心者なので意味不明な説明かもしれませんが、参考になる方法やHP等ありましたら教えてください。

**デフォルトの名無しさん** · 2009/08/14(金) 02:06:20

そこだけ__asm { } でインラインアセンブラで書くとか

**デフォルトの名無しさん** · 2009/08/14(金) 08:53:55

int64が無いコンパイラだとasmも無さそうな

**デフォルトの名無しさん** · 2009/08/14(金) 09:37:58

>>186
具体的なロジックを出さないと、曖昧なレスしかつかないよ。

**デフォルトの名無しさん** · 2009/08/14(金) 13:23:06

186です。

さっそくの返信ありがとうございます。

一応必要な部分だけアセンブラで書くことも可能だったと思いました。ただ現在携帯からの書き込みでキツいので、あとでまた書きます。

**,,・´∀｀・,,）っ-○○○** · 2009/08/15(土) 09:25:55

>>186
ないから自力でやれ

**デフォルトの名無しさん** · 2009/08/15(土) 20:24:26

どなたかご教示願います。
lehmerの線型合同法で作成される乱数値は、
初期値が同じでも計算機環境の違いにより変わることはありますか？

**デフォルトの名無しさん** · 2009/08/16(日) 02:20:18

うん

**デフォルトの名無しさん** · 2009/08/16(日) 08:03:39

同じ数式を計算したのに計算機環境の違いで結果が変わることがあると思う？

**,,・´∀｀・,,）っ-○○○** · 2009/08/16(日) 08:23:56

浮動小数ならよくある

**デフォルトの名無しさん** · 2009/08/16(日) 08:28:53

>>> (2 / 3) * 6
0
>>> 6 * 2 / 3
4

**192** · 2009/08/16(日) 11:13:06

>>193 >>195 >>196

ありがとうございました。

**デフォルトの名無しさん** · 2009/08/17(月) 10:39:10

>>196
それらは「同じ数式」といえるのか?

**デフォルトの名無しさん** · 2009/08/17(月) 13:04:38

>>194
有効桁数をちゃんと制御して、その動作が保証されている言語を使うなら、
バグでない限り有効桁数の範囲で変わることはない。

ただ同じ数式の同一の変数に別の値を与えたのなら変わってもおかしくないよ。
つかそれ以前に疑似乱数に関係あるのかｗ

**デフォルトの名無しさん** · 2009/09/03(木) 21:52:50

高次元均等分布性ってどういうこと？
p[i]=(x[Ni+0],x[Ni+1],…,x[Ni+N-1])
として作ったＮ次元乱数のＮ次元空間上散布図が
Ｎ次元空間内に平面作ったり偏ったりせずにぼんやり分布することと考えていいのかな？

**デフォルトの名無しさん** · 2009/09/04(金) 07:05:22

誤解を恐れずに大雑把かつ簡単に言うと、
nビットの状態空間があるとして、
一周期の間に00...00から11...11までnビット(n桁)の数字が
過不足なく1回ずつ出現すること。
それが満たされると周期全体で直前のn-1ビットの状態に関わらず
次の1ビットの出現確立が必ず50:50になる。
つまりn-1次元で0と1が均等に分布したことになる。
状態空間を越えた次元では分布については全く保証出来ない。
だからMT含めて最近の擬似乱数はみんな状態空間をかなり大きめにとってる。

ただしこれはあくまで一周期のことであって、
一周期の一部を切り出した場合(通常の使用状況)では全然話が別ね。
マクロとミクロの違いというか両方同時に成り立たせるのは難しい。
よく0過多状態からの回復の速さが注目されるけど、
状態空間が大きいのに三項式とかだと(MTのことね)
0の多い区間はその前後でも0が多くなる。
逆に1の多い区間はその前後で1が多くなってトータルで均等になるわけさ。

**デフォルトの名無しさん** · 2009/10/04(日) 07:32:06

一月あげ

**デフォルトの名無しさん** · 2009/10/05(月) 10:51:02

unko

**デフォルトの名無しさん** · 2009/10/05(月) 15:32:33

Blum-Blum-Shub のC/C++ の実装コードが掲示されているサイトを知ってる人いませんか？
java での実装例はここにあるんですが
http://code.google.com/p/javarng/

**デフォルトの名無しさん** · 2009/10/05(月) 18:00:56

1+1=2

**デフォルトの名無しさん** · 2009/10/05(月) 18:22:02

>>204
BlumBlumShub.java を C/C++ に書き換えるだけじゃだめなん？

**デフォルトの名無しさん** · 2009/10/05(月) 18:34:10

C/C++ に BigInteger の標準的な代替物でもあれば楽勝だろうけど

**デフォルトの名無しさん** · 2009/10/05(月) 18:55:46

blumblum.c とfreelip いうファイルを見つけ
http://www.mindspring.com/~pate/crypto/chap05/blumblum.c
http://math.arizona.edu/~aprl/math/comp/bigint/
blumblum.c をgcc (GCC) 4.2.4 でコンパイルするのですが
zcopy とか、zfree とか、zなんとかという命令がコンパイルできなくて詰まっています。
何なんだこのz何とかというコマンドは？cの命令セットにはないぞ、posix かなんかの命令セットなのか？

**デフォルトの名無しさん** · 2009/10/05(月) 19:01:35

>>204、>>208です皆さんサンクスです。
>>207
その通りです、java からの移植はBigInteger を見て、ライブラリから作る羽目になりそうだったので
速攻あきらめました。boost にBlumBlumShubがあればいいのにな・・・・

**デフォルトの名無しさん** · 2009/10/06(火) 00:46:53

>208
C/C++ ではコマンドとか命令とか命令セットとは言わないだろう、普通。
命令セットって言われたら CPU の instruction set を思い浮かべるわ。

で、freelip ってのの中に z* 入ってるじゃん。
C/C++ の分割コンパイルに詰まってるんだろうけど、とりあえず
gcc -o blumblum blumblum.c lip.c
とかで実行ファイルできない？

あと、boost vault には bigint が有ったような。使いものになるかしらんけど。

**デフォルトの名無しさん** · 2009/10/06(火) 22:41:31

>210
gcc -o blumblum blumblum.c lip.c
このオペレーションも上手くいかない・・・orz

**デフォルトの名無しさん** · 2009/10/06(火) 23:27:47

今度はオペレーションて

**デフォルトの名無しさん** · 2009/10/07(水) 06:28:55

>>209 gmp じゃだめ？

**デフォルトの名無しさん** · 2009/10/07(水) 08:53:51

どういうエラーが出てるのか書かなきゃ対処しようもないぞ

**デフォルトの名無しさん** · 2009/11/14(土) 09:37:55

xorshiftをunsigned longではなく32bit intの範囲内でやる方法はありませんか？

**デフォルトの名無しさん** · 2009/11/14(土) 16:45:06

complementary multiply-with-carry ってのが
周期長くて計算軽いってのは分かったけど
高次元での均等性はどうなの？
MTだと623個の組で使っても大丈夫ということだけど

**デフォルトの名無しさん** · 2009/11/14(土) 19:33:47

RC4が最強だろ

**デフォルトの名無しさん** · 2009/11/15(日) 00:29:33

>>215
符号無しの整数型が存在しない言語で実装しようとしているのか？
例えば、Javaとかだと符号付き整数型でも気にせずビット演算して大丈夫のはずなんだけど。

もう1つ、そのunsigned longはおそらく32ビットだと思う。コードを注意してみて。
違ったとしてもググれば32ビット符号無し整数(unsigned intだかunsigned longだか)での実装はすぐ見つかると思う。

**デフォルトの名無しさん** · 2009/11/18(水) 19:08:23

最近できた疑似乱数をまとめたサイトとかない？

**デフォルトの名無しさん** · 2009/12/05(土) 08:22:52

起動戦士ランダム♪ランダム♪

**デフォルトの名無しさん** · 2009/12/05(土) 11:36:41

俺がランダムだ

**デフォルトの名無しさん** · 2010/01/08(金) 13:19:31

シェーダ/GPGPU向けでよい疑似乱数ってどんなのがあるでしょうか。
数列系の疑似乱数を直に使うことが出来ないのでいろいろ考えています。

**デフォルトの名無しさん** · 2010/01/08(金) 14:30:20

もっと具体的に書かないと分からん
メモリアクセスが厳しいとかそういう話か？

**デフォルトの名無しさん** · 2010/01/08(金) 14:35:46

もう一つ
>数列系の疑似乱数
擬似乱数はみんな数列だぞ

**デフォルトの名無しさん** · 2010/01/08(金) 14:42:46

ワーキングセットが小さい、って意味か？
確かにMTは比較的大きいが。

**デフォルトの名無しさん** · 2010/01/08(金) 15:01:10

アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。
その際、2次元画面*時間の3次元で相関などがなく一様分布するノイズにしたいのです。
画素ごとに並列に計算できれば高速に計算できることは分かっているのですが、
数列を使う以上は基本的に一つずつ取り出すしかなく並列化できません。
そのため、並列計算で生成できる疑似乱数生成法がないかと探しているところです。

一応全画素に32バイト割り当てればそれぞれXorShiftの系列が張り付けられるかなとは考えましたが、
やはりちょっとワーキングセットが大きくなるのと、
XorShiftの系列間相関の有無がよくわからず、躊躇しています。

自分で実装しなければならないなら、各画素の計算では、画素の座標（各座標に固有だが相関たっぷり）と、
フレームごとに全部画素一律に参照できるベクトルを与えることができるので、
それをうまく使って乱数列の系列の途中の値をうまく与えられないかなあ、などと考えています。

**デフォルトの名無しさん** · 2010/01/08(金) 15:22:14

プールして切り出し

**デフォルトの名無しさん** · 2010/01/08(金) 15:33:08

xyz全部に相関なしか…そいつぁ難しいぜ
とりあえず画素毎に独立した個別の乱数を充てるのはダメだな
少なくとも画素以上の状態空間を持った乱数を用意しないと相関なしには出来ないんだぜ
適当に作っても任意の画素間で相関がないことを保証できないだろ？
そもそも同じ生成式を使えば初期値が違うだけで結局同じ乱数列しか得られないからな

とまあ大げさに書いたけど、本気で3次元完全無相関を目指してるわけじゃないよね？
落としどころとしてはMTとか周期の長い乱数を使って
一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
各画素はM系列とかXorShift?(いまいち信用できない)を使えばよろし。

**デフォルトの名無しさん** · 2010/01/08(金) 20:32:23

遅れまして申し訳ありません。

>>228
勉強になります。
一瞬、隣の画素の状態を見ながらメルセンヌツイスタのように「捻れ」ないかと思いましたが、
結局そこでデータコヒーレンシーの問題で並列化できなそうなのでそれも無理そうですね

結構本気で3次元無相関を目指しているというか無相関であることが優先される用途なので、
現在は時間を仕切って有限の大きさにしてプールして切り出し、というのが現実的な解となっています。
ただ長時間やるにはメモリがいくらあっても不足するような感じなので、
なんとか生成できないかなあと思う次第です。
副産物として、落としどころとしてそれっぽいものを作ることは吝かでもないですが。

**デフォルトの名無しさん** · 2010/01/08(金) 21:37:19

>>229
当然ながら精度と速度は両立しないんで、
どこまで必要なのか見極めて妥協することになるけど、
仮に1画素あたり32bitとして640*480なら、
最低でも1228800バイト以上の状態空間が必要だね。
これで1フレーム分だから残り何フレームまで必要なのか考えてみればいいよ。

>一瞬、隣の画素の状態を見ながらメルセンヌツイスタのように「捻れ」ないかと思いましたが、
MTの「捻り」はGFSRの短かった周期を理論値まで伸ばしてるだけ。
無闇に隣を参照したらダメだよ。

**デフォルトの名無しさん** · 2010/01/08(金) 23:07:46

>>230
ありがとうございます。
まずはM系列からということでググったり本棚をあさったりしていたのですが、
疑似乱数を作るということは、どういう遍歴をたどる数列を設計するかという話だ、ということが改めて身にしみました。
また、正しく「捻る」にはビットの遍歴が最長となるよう正しくビット間の周回コースを繋がなければならない、という理解でいいのでしょうか。

＞落としどころとしてはMTとか周期の長い乱数を使って
＞一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
という話は、最初見たとき手抜き実装かなと思ってしまったりしたのですが、
冷静に考えるとCPU側とGPU側の状態は両方とも完全に決定可能なのだから、
周期や分布もちゃんと計算できるのですね。
この方法が自分の目的にとっては王道のような気がしてきました。

まったく不勉強で疑似乱数の世界の入場門がどこにあるかがやっとわかった状態ですが、
道筋がなんとなく見えてきたので、次に質問する前に、もっと自分で勉強してみたいと思います。
素人の思いつきに懇切丁寧にご回答いただきありがとうございました。

**デフォルトの名無しさん** · 2010/01/09(土) 12:02:20

>>228
こういう用途なら、単純に１次元化して、正規乱数を利用すればいいんじゃないの？

**デフォルトの名無しさん** · 2010/01/09(土) 12:35:43

それじゃ速度が出ないだろ
というかそれでいいなら質問してこないだろ

**デフォルトの名無しさん** · 2010/01/09(土) 12:38:29

その前にその正規乱数はどこから持ってくるのかと小一時間(ry

**デフォルトの名無しさん** · 2010/01/09(土) 23:20:47

>アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。

あれ、ほんとに相関なしなん？＞詳しい人
なんか、いいセルオートマトンとかありそうじゃない？

**デフォルトの名無しさん** · 2010/01/10(日) 00:55:27

砂嵐状態っていっても度合いがあるからね。
元の信号が強く混ざってれば文字通り目に見えて分かるし。
砂嵐(スノーノイズ)の原因は熱雑音らしいから
S/Nが十分に悪ければ(笑)ほぼ相関なしといえると思う。

熱雑音はランダムか？という問題は話が別ね。
そっちは量子論の問題だから。
何か法則があるかも知れないしないかも知れないけど
とりあえず理論的に確認できる方法がないので(観測問題)
そこのところは考えないでおこうってのが今の主流。
どちらであっても今のところ結果は統計的な予測と一致している。
ので今のところ統計的に熱雑音はランダムと言えるっぽい。

そもそもランダム・不規則ってなんだ？ってのも哲学っぽくて難しい問題だ。
熱雑音も本当は原子の状態(擬似乱数でいう状態空間)を完全に知ることが出来れば
その後の振る舞いを予測することが出来るはずなんだけど(決定論)
前の状態と次の状態を同時に知ることが出来ない(観測問題)。
観測者の有無に関係なく次の状態は決まっていると考えたのはアインシュタインで
(神はサイコロを振らない)この説は今は少数派。
果たして観測者が次の状態に影響を与えた結果は如何に？

ところで仮に完全に熱雑音の振る舞いを表現することが出来たとして
それをもし理論的に解析できたとしたらその結果はランダムだろうか？
周期も分布も分かってる既存の擬似乱数の方が良かったらどうだろう？
今までに我々がランダムと呼んでいたものの正体は…？