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

疑似乱数２ ..

197:192
09/08/16 11:13:06
>>193 >>195 >>196

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

198:デフォルトの名無しさん
09/08/17 10:39:10
>>196
それらは「同じ数式」といえるのか?

199:デフォルトの名無しさん
09/08/17 13:04:38
>>194
有効桁数をちゃんと制御して、その動作が保証されている言語を使うなら、
バグでない限り有効桁数の範囲で変わることはない。

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

200:デフォルトの名無しさん
09/09/03 21:52:50
高次元均等分布性ってどういうこと？
p[i]=(x[Ni+0],x[Ni+1],…,x[Ni+N-1])
として作ったＮ次元乱数のＮ次元空間上散布図が
Ｎ次元空間内に平面作ったり偏ったりせずにぼんやり分布することと考えていいのかな？

201:デフォルトの名無しさん
09/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が多くなってトータルで均等になるわけさ。

202:デフォルトの名無しさん
09/10/04 07:32:06
一月あげ

203:デフォルトの名無しさん
09/10/05 10:51:02
unko

204:デフォルトの名無しさん
09/10/05 15:32:33
Blum-Blum-Shub のC/C++ の実装コードが掲示されているサイトを知ってる人いませんか？
java での実装例はここにあるんですが
URLﾘﾝｸ(code.google.com)

205:デフォルトの名無しさん
09/10/05 18:00:56
1+1=2

206:デフォルトの名無しさん
09/10/05 18:22:02
>>204
BlumBlumShub.java を C/C++ に書き換えるだけじゃだめなん？

207:デフォルトの名無しさん
09/10/05 18:34:10
C/C++ に BigInteger の標準的な代替物でもあれば楽勝だろうけど

208:デフォルトの名無しさん
09/10/05 18:55:46
blumblum.c とfreelip いうファイルを見つけ
URLﾘﾝｸ(www.mindspring.com)
URLﾘﾝｸ(math.arizona.edu)
blumblum.c をgcc (GCC) 4.2.4 でコンパイルするのですが
zcopy とか、zfree とか、zなんとかという命令がコンパイルできなくて詰まっています。
何なんだこのz何とかというコマンドは？cの命令セットにはないぞ、posix かなんかの命令セットなのか？

209:デフォルトの名無しさん
09/10/05 19:01:35
>>204、>>208です皆さんサンクスです。
>>207
その通りです、java からの移植はBigInteger を見て、ライブラリから作る羽目になりそうだったので
速攻あきらめました。boost にBlumBlumShubがあればいいのにな・・・・

210:デフォルトの名無しさん
09/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 が有ったような。使いものになるかしらんけど。

211:デフォルトの名無しさん
09/10/06 22:41:31
>210
gcc -o blumblum blumblum.c lip.c
このオペレーションも上手くいかない・・・orz

212:デフォルトの名無しさん
09/10/06 23:27:47
今度はオペレーションて

213:デフォルトの名無しさん
09/10/07 06:28:55
>>209 gmp じゃだめ？

214:デフォルトの名無しさん
09/10/07 08:53:51
どういうエラーが出てるのか書かなきゃ対処しようもないぞ

215:デフォルトの名無しさん
09/11/14 09:37:55
xorshiftをunsigned　longではなく32bit　intの範囲内でやる方法はありませんか？

216:デフォルトの名無しさん
09/11/14 16:45:06
complementary multiply-with-carry ってのが
周期長くて計算軽いってのは分かったけど
高次元での均等性はどうなの？
MTだと623個の組で使っても大丈夫ということだけど

217:デフォルトの名無しさん
09/11/14 19:33:47
RC4が最強だろ

218:デフォルトの名無しさん
09/11/15 00:29:33
>>215
符号無しの整数型が存在しない言語で実装しようとしているのか？
例えば、Javaとかだと符号付き整数型でも気にせずビット演算して大丈夫のはずなんだけど。

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

219:デフォルトの名無しさん
09/11/18 19:08:23
最近できた疑似乱数をまとめたサイトとかない？

220:デフォルトの名無しさん
09/12/05 08:22:52
起動戦士ランダム♪ランダム♪

221:デフォルトの名無しさん
09/12/05 11:36:41
俺がランダムだ

222:デフォルトの名無しさん
10/01/08 13:19:31
シェーダ/GPGPU向けでよい疑似乱数ってどんなのがあるでしょうか。
数列系の疑似乱数を直に使うことが出来ないのでいろいろ考えています。

223:デフォルトの名無しさん
10/01/08 14:30:20
もっと具体的に書かないと分からん
メモリアクセスが厳しいとかそういう話か？

224:デフォルトの名無しさん
10/01/08 14:35:46
もう一つ
>数列系の疑似乱数
擬似乱数はみんな数列だぞ

225:デフォルトの名無しさん
10/01/08 14:42:46
ワーキングセットが小さい、って意味か？
確かにMTは比較的大きいが。

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

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

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

227:デフォルトの名無しさん
10/01/08 15:22:14
プールして切り出し

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

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

229:デフォルトの名無しさん
10/01/08 20:32:23
遅れまして申し訳ありません。

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

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

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

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

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

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

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

232:デフォルトの名無しさん
10/01/09 12:02:20
>>228
こういう用途なら、単純に１次元化して、正規乱数を利用すればいいんじゃないの？

233:デフォルトの名無しさん
10/01/09 12:35:43
それじゃ速度が出ないだろ
というかそれでいいなら質問してこないだろ

234:デフォルトの名無しさん
10/01/09 12:38:29
その前にその正規乱数はどこから持ってくるのかと小一時間(ry

235:デフォルトの名無しさん
10/01/09 23:20:47
>アナログテレビの砂嵐状態のように、全画素を毎フレームノイズで埋め尽したいと考えています。

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

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

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

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

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

237:デフォルトの名無しさん
10/01/10 03:21:02
仕組みが分かったところで、解を出すためには初期条件が必要
シードを与えて一意な結果を出すのは一般的な乱数と同じものだろ

238:デフォルトの名無しさん
10/01/10 03:26:41
>>237
何の話？

239:デフォルトの名無しさん
10/01/10 04:32:49
物理量を離散的に捉えるのは根本的に違ってるぞ

240:デフォルトの名無しさん
10/01/10 05:36:42
サンプリングすればおk

241:デフォルトの名無しさん
10/01/10 19:07:32
DOOM をソフトウェアラスタライズしていた頃と比べれば、リアルタイム程度なら CPU で mt やって充分間に合いそうな気がする。
こういう大量生成が対象なら、前に Cell スレで盛り上がってたコンテストの最適化がフィットすると思う。
そんで別の種でマルチスレッドでクアッドコアで、って感じでどうだろう。

242:デフォルトの名無しさん
10/01/11 03:25:51
プリレンダした砂嵐テクスチャ並べて適当に描画すれば？

243:デフォルトの名無しさん
10/01/11 09:28:59
>>242
それは正しい処理だが、スレタイを翌嫁。

244:デフォルトの名無しさん
10/01/11 16:31:10
>>242,243
それだとテクスチャが沢山必要になるからi/oで引っかかって
擬似乱数より遅くなるよ

245:デフォルトの名無しさん
10/01/11 20:19:14
二次写像などのカオスの数値の下ビットを使うというのはどうだろう

でも実際に相関がないことを証明する必要があると面倒ですね。
plot(rand mod 640,rand mod 400,rand mod 16)
とかでとびとび直線が出てびっくりですよ

246:デフォルトの名無しさん
10/01/11 20:48:42
>>245
数理的な意味でのカオスってのは、テント写像に代表されるように
小数点以下を無限に汲みだす漸化式になっているから予測が難しいのであって、
種が有限桁数であっては成立しない。

むしろ、いかなる相関性のある入力に対しても、
周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。

247:デフォルトの名無しさん
10/01/11 20:48:48
こんなことを言い出すやつがいるとは…
それは線形合(ry
このスレは分かってる人とそうでない人のレベル差が妙に大きいな

248:デフォルトの名無しさん
10/01/11 20:57:18
>むしろ、いかなる相関性のある入力に対しても、
>周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。
いいわけない、というかそれはただのハッシュ
等確率性・分布・周期を保証できないし
入力がずっと同じだったらどうにもならん

249:デフォルトの名無しさん
10/01/11 21:02:21
>>248
アンカが抜けてた

>228の
＞落としどころとしてはMTとか周期の長い乱数を使って
＞一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
に対して、それなら各画素で回す周期は短くていいんじゃないかなと。
等確率性と分布は証明or検証する必要性があるとして。

250:デフォルトの名無しさん
10/01/11 21:36:24
>>246
頭悪そうな意見だな。周期が短い時点で相関性アリまくりだろうが。
↓こういう馬鹿(道化師)がいたことを思い出す。
【危険】とんでもプログラム告発スレッド【悪質】
ｽﾚﾘﾝｸ(tech板)
1 名前：デフォルトの名無しさん[] 投稿日：2007/10/09(火) 01:15:16
劣悪なプログラムやアルゴリズムを、恰も優れたものだと言い張り、
他人を騙しているサイトを告発、検証、監視することを目的としたスレッドです。
単純に技量不足だったり、稚拙であるもの、下らないものは対象としません。
第一弾として、
道化師氏のサイト(URLﾘﾝｸ(www.trickpalace.net))の
疑似乱数アルゴリズム「無相関性擬似乱数アルゴリズム-prime spiral-」
URLﾘﾝｸ(www.trickpalace.net)
を紹介します。このアルゴリズムおよび作者の言動の問題点は以下のとおり。
・MT(Mersenne Twister)がダメだと主張しながら、具体的な問題点は指摘できていない。
・MTより劣悪な乱数を生成しながら、MTより優れていると主張する。
・周期がたったの2^32のしかない(線形合同法と同レベル)
・無駄にテーブル参照するため遅い(線形合同法より劣悪)
・優れていると主張しながら、言葉の定義と評価基準を示すことはしない。
・indexと最低限の出力系列(各素数の和)が得られると、初期ベクトルが逆算ができてしまう。
・最低限の出力系列で、全パターンに出現する値の分布が確定する。
indexが確定すれば出現順まで確定するほど相関性が非常に高く劣悪。
・出ない値が確定するという点で乱数とはもはや呼べない。
・作者は暗号用途にも使えるつもりでいる。MTより「良い」乱数だと宣伝しているが、
実際は周期、分布などの点で低品質。信じて使うとろくなことにならない。

アルゴリズムの問題点や作者の人間性が明らかになる過程はこちらのスレで読めます。
擬似乱数
ｽﾚﾘﾝｸ(tech板)

251:デフォルトの名無しさん
10/01/12 01:04:22
これは過去ログ見てみたかったな
まあ乱数弄ってりゃそのうち巡り会うこともあろう

252:デフォルトの名無しさん
10/01/12 01:25:44
>>426が言いたいのはハッシュ関数かと思われ

253:デフォルトの名無しさん
10/01/12 03:31:52
>>251
過去ログ（1146071975.dat）うｐしたね
URLﾘﾝｸ(www.dotup.org)
よかたら見るね

254:デフォルトの名無しさん
10/01/12 11:59:26
>>226
ホワイトノイズ(一様分布)じゃなくてブルーノイズでも良いなら方法はある。
ブルーノイズはホワイトノイズの低周波成分を除いたもの。

ホワイトノイズではモアレのような模様が見えるがブルーノイズでは模様は見えない。

255:デフォルトの名無しさん
10/01/12 16:02:33
乱数をjpegなどのデコーダーに食べさせるって言うのはどうだろうか

256:デフォルトの名無しさん
10/01/13 01:01:39
>>253
頂きました！
どうもありがとう～
俺，週末になったらこれ読むんだ…

257:241
10/01/13 05:15:25
試してみたが、VC++2008EE の /O2 でコンパイルした MEXP=216091 の sfmt の gen_rand32() で
1920x1200 を 30 枚埋めるのに、2003年の CPU P4 2.6C で 600ms 弱くらい。
今なら余裕じゃない？