擬似乱数
レス数が1000を超えています。これ以上書き込みはできません。
0001デフォルトの名無しさん
2006/04/27(木) 02:19:350002デフォルトの名無しさん
2006/04/27(木) 02:21:190003デフォルトの名無しさん
2006/04/27(木) 02:26:290004デフォルトの名無しさん
2006/04/27(木) 02:35:58n * 1103515245 + 12345 mod 2147483648
の間違い
0005デフォルトの名無しさん
2006/04/27(木) 02:39:250006デフォルトの名無しさん
2006/04/27(木) 03:00:430007デフォルトの名無しさん
2006/04/27(木) 05:52:270008デフォルトの名無しさん
2006/04/27(木) 06:28:13乱数スレ
http://science4.2ch.net/test/read.cgi/math/1126350979/
電気電子板
【疑似】乱数をつくる【本物】
http://science4.2ch.net/test/read.cgi/denki/1074867250/
シミュ板
乱数
http://science4.2ch.net/test/read.cgi/sim/1100375806/
0009デフォルトの名無しさん
2006/04/27(木) 14:29:100010デフォルトの名無しさん
2006/04/27(木) 15:42:250011デフォルトの名無しさん
2006/04/28(金) 11:56:290012デフォルトの名無しさん
2006/04/28(金) 14:01:30http://www.toshiba.co.jp/about/press/2004_08/pr_j0901.htm
http://www.internix.co.jp/publish/newsletter/nl85_pdf/nl85fdk.pdf
http://www.hmi-jp.com/hmi/security/clutterbox.html
0013デフォルトの名無しさん
2006/04/28(金) 18:28:56アルゴリズムじゃなくて、その実装(mt19937ar.c)のアラでよければ。
MTは内部状態として624個のベクトルを持ち、そこから乱数をひねり出す。
つまりはMTは624*32=19968ビットの乱数生成器で、
その19968ビットの乱数表から32ビットずつ取り出すのがgenrand_int32()関数ということができる。
で、genrand_int32()を624回呼ぶごとに内部のベクトルを一度に「えいや」と更新するようになっている。
大量の乱数が必要な場合は並列処理が効くのでこれでよいのだが、
中程度数の乱数がリアルタイムで必要となる場合、これはいただけない。
例えばゲームでMTを使うとすると、624回乱数を生成するごとにフレーム落ちが発生、ということもありうる。
genrand_int32()を1回呼び出すごとに1つのベクトルを更新するようにすれば
いつでも同じ時間で乱数が得られる。
0014デフォルトの名無しさん
2006/04/28(金) 18:39:05「お前本当に分かっててその乱数発生器を薦めているのか?」と言いたくなる。
0015デフォルトの名無しさん
2006/04/28(金) 23:12:59>では手始めに、メルセンヌツイスタの荒探しの話題から頼む。
でかい、重い。
大体、普通の用途でここまで乱数性に拘る場面はそうそうない
(だから喧嘩を売られた knuth もスルーした)。
0016デフォルトの名無しさん
2006/04/28(金) 23:42:090017デフォルトの名無しさん
2006/04/28(金) 23:47:00まあ周期長いから頻繁に初期化するような使い方はしないが。
0018デフォルトの名無しさん
2006/04/28(金) 23:53:29unsigned long xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
0019デフォルトの名無しさん
2006/04/29(土) 00:09:50やっぱりどれもハッシュ関数みたくなるのな。
0020デフォルトの名無しさん
2006/04/29(土) 00:10:170021デフォルトの名無しさん
2006/04/29(土) 00:12:530022デフォルトの名無しさん
2006/04/29(土) 01:01:050023デフォルトの名無しさん
2006/04/29(土) 01:02:49均等な乱数が超大量に必要な場合に使う、みたいな。
0024デフォルトの名無しさん
2006/04/29(土) 01:43:550025デフォルトの名無しさん
2006/04/29(土) 04:20:02プログラマーには見えても、ユーザーには周期性は見えないよ。
1フレーム数回以下なら、必要なら重くても高品質なほうがいいんじゃない?
AI とか、 ランダムダンジョンとか。
0026デフォルトの名無しさん
2006/04/29(土) 07:30:180027デフォルトの名無しさん
2006/04/29(土) 20:33:091.ゲームプログラマの自己満足の為:86%
2.汎用のライブラリが乱数生成関数として
MT を採用しているから、いつの間にか使っている:10%
3.本来のシミュレーション用に使用:3%
4.その他:1%
位だと思う。
0028デフォルトの名無しさん
2006/04/30(日) 15:17:30ぐぐっても"well"なんて単語としてありきたりすぎて
関係ないページがヒットしまくりなんだが。
作者的には「より良い」と語呂合わせしたつもりなんだろうが、
いまや情報化社会。物にはなるべく一般的な語とかぶらないような名称をつけて頂きたい。
0029デフォルトの名無しさん
2006/04/30(日) 22:18:10(その時しかありえないようなPCの状態)を混ぜりゃほぼ
ランダムになる。
0030デフォルトの名無しさん
2006/04/30(日) 22:23:18その必要も無いのに、
テスト項目に「時間」と「ユーザーの入力」の要素が
入るような実装は、極力避けるべき。
テストの自動化が出来ない。
0031デフォルトの名無しさん
2006/04/30(日) 22:31:530032デフォルトの名無しさん
2006/05/03(水) 15:09:150033デフォルトの名無しさん
2006/05/03(水) 18:20:08パケットが通過する間隔はポアソン分布に従う、とかそういうのを利用するのか?
0034デフォルトの名無しさん
2006/05/03(水) 18:58:420035デフォルトの名無しさん
2006/05/03(水) 21:02:28これ確かに早いけど、種を選ぶのが難点だね。
128ビットで、そこそこ0と1が混じってないと駄目ってのが。
種用に物理乱数とか、遅くても質のいい乱数発生器を別個に使う必要があるなあ
0036デフォルトの名無しさん
2006/05/04(木) 00:41:36あと、初期化が糞だよねぇ。そのせいでかなり癖のある乱数列が生成される。理論台無し。
0037デフォルトの名無しさん
2006/05/04(木) 08:02:03xorgensでもMTでもどの擬似乱数でも言えることだけど。
0038デフォルトの名無しさん
2006/05/04(木) 08:09:300039デフォルトの名無しさん
2006/05/04(木) 08:14:570040デフォルトの名無しさん
2006/05/04(木) 08:26:4450万とか70万とかいうデータもあるが
0041デフォルトの名無しさん
2006/05/04(木) 08:37:490042デフォルトの名無しさん
2006/05/04(木) 08:51:130043デフォルトの名無しさん
2006/05/04(木) 09:36:18再現性がなくなるだけで、時間を加味していればテストは自動化できるだろ。
話それるがユーザー入力だって、ある程度自動化するし。
>>32>>33>34
全部ユーザー入力と一緒じゃね
0044デフォルトの名無しさん
2006/05/04(木) 10:57:54はつみみなのでソースおせーて
0045デフォルトの名無しさん
2006/05/04(木) 12:31:25読み飛ばすだけで癖が抜けるとは思えんのだが。
0046デフォルトの名無しさん
2006/05/04(木) 12:51:05その統計の在処をぜひ
0047デフォルトの名無しさん
2006/05/04(木) 14:23:52(新しい擬似乱数考えるのと同じになりそうだが)
0048デフォルトの名無しさん
2006/05/04(木) 14:37:16そんなの Windows なら CryptGenRandom 、Unix系なら /dev/urandom を使う・・・てのが常識では?
0049デフォルトの名無しさん
2006/05/04(木) 15:30:21まあ暗号用に使うんじゃなくてあくまで擬似乱数用の種だからCRCとかでもいいような希ガス
0050デフォルトの名無しさん
2006/05/04(木) 16:47:54厳密にやりたきゃ>>48の使えばいいし。
0051デフォルトの名無しさん
2006/05/04(木) 19:56:01自分で乱数性の検証はしていなかったんだな。
0052デフォルトの名無しさん
2006/05/05(金) 18:18:49当たり前だろw
偉い人が使えるって言えば使うだけ
0053デフォルトの名無しさん
2006/05/05(金) 18:25:54M系列が2^127-1の周期で線形合同法が2^32の周期だから 合成周期は掛け算でいいんだよな?
0054デフォルトの名無しさん
2006/05/05(金) 19:59:17それが厨の厨たる所以。
>>53
ヒント 指数は掛け算が足し算。
つまり合成周期は2^159弱ってこった。
0055デフォルトの名無しさん
2006/05/05(金) 20:47:20簡単に種を見つけるアルゴリズムはあるのだろうか?
0056デフォルトの名無しさん
2006/05/06(土) 15:07:250057デフォルトの名無しさん
2006/05/06(土) 18:27:200058デフォルトの名無しさん
2006/05/06(土) 19:05:500059デフォルトの名無しさん
2006/05/06(土) 19:51:450060SOURCE ◆tAo.kQ2STk
2006/05/06(土) 20:53:53両方の式を満たすような特殊な式があればいくらでも出来そうなキガス。
線形合同法は離散対数とかの扱いが面倒だが?
>>56
総当りすればいつかは解けるけどさ、現実的な時間内で2^159弱ある鍵空間を全て試せるのか?
2^159≒10^47*7.3
一秒間に10^39回強のスピードで当たれるとして23年ほどかかるぞよ。
>>58
それは正しいけど、総当り以外に破る方法が存在しない事を証明する事は難しいとオモフ。
0061デフォルトの名無しさん
2006/05/07(日) 12:15:430062デフォルトの名無しさん
2006/05/07(日) 13:19:27総当たりで簡単に種を探せるようなスペックのマシンが動いている気がする。
0063デフォルトの名無しさん
2006/05/07(日) 13:38:43光の速度を考えると、本当にそんなマシンが出来ると思う?
0064デフォルトの名無しさん
2006/05/07(日) 14:34:540065デフォルトの名無しさん
2006/05/07(日) 14:44:58この場合、全部の組み合わせを検索しなければならないのだとしたら
まず全部の組み合わせをどこかに入れておく必要があるんじゃないの?
そうすると物理的に不可能でしょ
0066デフォルトの名無しさん
2006/05/09(火) 00:29:21半導体中の熱電子の揺らぎを使った、
熱的乱数発生モジュールを売っているベンチャーもある。
もう数年前の話だけど。
0067デフォルトの名無しさん
2006/05/11(木) 00:56:09一つの量子に複数の状態を重ね合わせることが出来るので
理論上はあらゆる組み合わせを一箇所に保管できるようになる。
現在の技術では4状態で実験に成功したそうだw 先は長い……
00681つ、二つ、おっぱい。
2006/05/11(木) 22:14:09〜〜〜〜〜〜〜〜
> 理論上はあらゆる組み合わせを一箇所に保管できるようになる。
〜〜〜〜〜〜〜〜〜〜〜〜〜
後半ダウト。
「複数=あらゆる」って、おまいは大きな数を数えられない未開人ですか?
0069デフォルトの名無しさん
2006/05/12(金) 04:36:310070デフォルトの名無しさん
2006/05/13(土) 10:13:330071デフォルトの名無しさん
2006/05/14(日) 08:48:58一個の量子ビットにN個の状態を重ね合わせる量子アルゴリズムを使うなら
別におかしくないね
0072デフォルトの名無しさん
2006/05/14(日) 10:29:03頭悪すぎ
0073デフォルトの名無しさん
2006/05/14(日) 10:34:05量子と周囲とのインタラクションを完全遮断して、
かつ、その量子に任意個数の状態を保持可能なのかwww
ずいぶん貧弱な理論だなwww想像力が足りないというかwww基礎知識がない素人の発言は怖いというかwww
0074デフォルトの名無しさん
2006/05/14(日) 10:48:20検索が高速だとしても、
1万なら1万通りの状態を一瞬で作る方法があるのか?
あるなら、既にその問題は解けてるわけじゃないのか?
007571
2006/05/14(日) 11:07:33>かつ、その量子に任意個数の状態を保持可能なのか
一体何の話?
0077デフォルトの名無しさん
2006/05/14(日) 11:23:40>一個の量子ビットにN個の状態を重ね合わせる
とか言ってる時点で素人モロバレ
0079デフォルトの名無しさん
2006/05/14(日) 17:12:03それって周囲の温度によって乱数変わったりしない?
0080デフォルトの名無しさん
2006/05/14(日) 17:13:200081デフォルトの名無しさん
2006/05/14(日) 18:25:000082デフォルトの名無しさん
2006/05/16(火) 05:54:12static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
x
11101011011 1100110100010101
y
10101100110100101010111100101
z
11111000100100011101110110101
w
10101001 0010001001100110011
tの初期値が種?
0083デフォルトの名無しさん
2006/05/16(火) 07:51:37よく見ろ、t の初期値は使われてないぞ。
0084デフォルトの名無しさん
2006/05/16(火) 08:14:36static unsigned long x=123,y=456,z=78,w=90;
unsigned long t;
t=(x^(x<<13));x=y;y=z;z=w; return( w=(w^(w>>7))^(t^(t>>5)) );
}
こんなのでもいいの?
種(xyzw)の選び方やシフトするbit数の根拠がよう解らんのですわ。
0085デフォルトの名無しさん
2006/05/16(火) 12:12:560086デフォルトの名無しさん
2006/05/16(火) 14:33:23こんなところにタダで書くわけにも
0087デフォルトの名無しさん
2006/05/16(火) 22:17:00乱数全然わからんけど、
y,zはただのキャリアーでx,wの上下32bitを使うのね。
中間の64bitは使わなくてもいいの?
その方が出力が読みにくかったりする?
0088デフォルトの名無しさん
2006/05/17(水) 05:19:450089デフォルトの名無しさん
2006/05/17(水) 06:36:50よく見れ、種として機能している。
0090デフォルトの名無しさん
2006/05/17(水) 17:02:000091デフォルトの名無しさん
2006/05/17(水) 18:20:510092デフォルトの名無しさん
2006/05/17(水) 20:48:260093デフォルトの名無しさん
2006/05/17(水) 20:51:13セキュリティ関係の用途の時には >>48 。
0094デフォルトの名無しさん
2006/05/17(水) 21:32:340095デフォルトの名無しさん
2006/05/17(水) 22:47:54俺DTMやっててフルデジタル環境なのでサウンド入力は常時0になりますが……
もしかして俺の環境だとうまく乱数吐かないソフトあるんかな?
0096デフォルトの名無しさん
2006/05/17(水) 23:28:26それ、ほとんど毎回同じになるだろ。
0097デフォルトの名無しさん
2006/05/18(木) 00:42:15CPU稼働率
メモリ使用率
メモリキャッシュ量
HD容量+使用率
0098デフォルトの名無しさん
2006/05/18(木) 01:46:470099デフォルトの名無しさん
2006/05/18(木) 17:28:170100デフォルトの名無しさん
2006/05/18(木) 17:35:530101デフォルトの名無しさん
2006/05/18(木) 18:28:39そういやファミコンはアナログ信号ピンがあってカートリッジ側でそいつを読めたんだっけ?
それを乱数に使ったゲームは知らないが。
0102デフォルトの名無しさん
2006/05/18(木) 20:56:02MSが標準で提供してるサービスプロバイダを選んでちゃんとした初期化をすれば、失敗する環境なんてないだろ?
...俺も、以前はヘタレなコードを書いて環境よっては失敗するからなんでだろう?
と悩んでたけど初期化コードの問題だったぞ。(状態によって初期化方法を変える必要がある。)
0103デフォルトの名無しさん
2006/05/18(木) 21:01:00そういえば、Z80のアセンブラとかではリフレッシュレジスタ(※)の値を利用するなんて話もあったなぁ。
※昔のメモリシステムの名残で、メモリの内容が揮発しないように定期的にリフレッシュするのに
使われたレジスタ。どこのメモリブロックをリフレッシュするべきかを指し示して高速にその値が循環する。
0104デフォルトの名無しさん
2006/05/18(木) 21:04:34>>3
0105デフォルトの名無しさん
2006/05/18(木) 21:05:41連続起動時間とそうたいして変わらんと思う
0106デフォルトの名無しさん
2006/05/18(木) 21:14:180107デフォルトの名無しさん
2006/05/18(木) 23:11:517ビットだよ。
しかし互換CPUでは全く変化しないこともある罠。
0108デフォルトの名無しさん
2006/05/20(土) 18:47:53http://csrc.nist.gov/rng/
とかさ
0109デフォルトの名無しさん
2006/05/20(土) 19:38:12俺は乱数を自作したりその乱数性を評価するときにはその評価対象の乱数である程度のサイズの
乱数列を生成しそれをそのままファイルとして保存し、ファイルの圧縮プログラムを使ってその結果
の圧縮率が悪いほどエントロピーが高い良い乱数として評価してる。俺的にはこの方法はお手軽で
且つかなり有効なテストの方法だと思ってるんだけど、ちょっと他人の意見を聞いてみたい。
所謂「後出し」にならないように付け加えておくと、俺はこの評価方法は飽くまでエントロピーの高さを
計るものであって真性乱数性を計るものではないと自覚している。真性乱数性はその特性上
(まともな)評価方法は存在しないものと思ってる。( だって、ずっと同じ値を吐き続けたって真性乱数
の場合はアリってされるんだから、そんなもん評価のしようがない。 )
ちなみに俺はこのスレでMTに癖があるって言い出したヤツだけど、
それはこの方法による評価でMTで生成した乱数列の圧縮率がよかったから。
0110デフォルトの名無しさん
2006/05/20(土) 21:36:02偏りがないって事だろ。
MTほどの長い周期であれば部分的に偏りが生じる区間があるのは当然じゃない。
重要なのはその区間から次の区間を予測できないことな訳だ。
むしろ、いつどの区間を見ても偏りがないのなら短い周期しかもっていないことになる。
高々数MB、数GB程度のサイズじゃ乱数性は測れないよ。
試しに普通の線形合同法で乱数を生成してみれば分かる。
普通に圧縮できないから。
下位ビットは使うなよ。
0111デフォルトの名無しさん
2006/05/20(土) 21:48:45おまい、ちゃんとわかってる? ちゃんと実測した?
俺はMTの理論に問題があるなんて言ってない。初期化が糞だって言っただけ。
MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、
線形合同法なんかだと下位ビット捨てても圧縮率はいいぞ。
0112デフォルトの名無しさん
2006/05/20(土) 21:50:44> MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、
それって、 MT には何にも問題ないってことだよな?
0113デフォルトの名無しさん
2006/05/20(土) 22:20:49圧縮ソフトが何やってるのか調べた方がいいぞ。
0114デフォルトの名無しさん
2006/05/20(土) 22:26:01そだよ。だけど、極端な話すると100万回やっても同じ値を吐き続けるとってもあほみたいに周期の長い乱数と
100万回で一週しちゃうんだけどその間のエントロピーは文句なしの乱数のどっちが実用的だと思う?
少なくともあの実装のMTではモンテカルロ法に利用すんのも止めといたほうがいいぞ。
0115デフォルトの名無しさん
2006/05/20(土) 22:27:42そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。
だからこそ、他人の意見を聞きたい。
0116デフォルトの名無しさん
2006/05/21(日) 08:53:550117デフォルトの名無しさん
2006/05/21(日) 09:25:46にも関わらず、MTや線形合同法では圧縮率がいいんですよ。
てか、他の優れた評価方法とかないの?
俺も多少は乱数性の評価方法とか調べたけどあまりにもしょぼいしのか見つからなくてよー
たとえ例えハックにも過ぎなくても、これじゃ圧縮を利用したほうが断然いいじゃん・・・て、今んとこ結論してるわけよ。
0118デフォルトの名無しさん
2006/05/21(日) 10:49:31>おまい、ちゃんとわかってる? ちゃんと実測した?
実測データキボンヌ
0119デフォルトの名無しさん
2006/05/21(日) 14:52:24俺も記録をちゃんと残してたわけじゃないから、精確な情報じゃないけど
数十MB規模のデータでMTの場合、だいたい圧縮率が90%代後半で
線形合同法だと圧縮率が80%代後半だった。
ちなみに俺が自作したヤツやMTでも初期化をちゃんとしたヤツだと
圧縮率は100±1%ぐらいだった。
↑これは記憶を元に書いたんで多少間違ってるかもしれん。
精確なデータが欲しかったら自分で実測すれ。
あと俺が試した圧縮アルゴリズムはLZHとZIP。この二つはアルゴリズムが
かなり似てるから本当はもっといろんなアルゴリズムで比較したほうが
いいんだろうけど俺はそこまではやってない。
# 当然だけど、LZHとZIPではほとんど圧縮率に差がでなかった。
0120デフォルトの名無しさん
2006/05/21(日) 15:33:550121デフォルトの名無しさん
2006/05/21(日) 15:39:52別にどうもしないけど。圧縮アルゴリズムが違えば結果も異なるのは当たり前。
しいて言うなら評価をする為の圧縮アルゴリズムのひとつとして採用するだけ。
0122デフォルトの名無しさん
2006/05/21(日) 15:44:50俺自身も知識よりは閃きの人間だから、知識のないヤツは黙ってろとかは思わないが、
できれば知識を持ってる人間の意見を聞きたい。
0123デフォルトの名無しさん
2006/05/21(日) 15:53:050124デフォルトの名無しさん
2006/05/21(日) 15:58:02そんなこと言わないで、頼むよ〜
0125デフォルトの名無しさん
2006/05/21(日) 17:11:270126デフォルトの名無しさん
2006/05/21(日) 17:32:09そこまでテキトーなこと抜かすなよ。
ちょっとバイナリでの表現がどうなるか考えりゃ、圧縮できることぐらいわかんだろ。
せめてもうちゃっと考えてから書き込んでくれ、な?
0127デフォルトの名無しさん
2006/05/21(日) 17:51:37いや循環し続けるデータなら ハフマンでは圧縮出来ないのは正しいだろ
ただ、差分をとれば途端に圧縮出来るのだが
0128デフォルトの名無しさん
2006/05/21(日) 17:58:040129デフォルトの名無しさん
2006/05/21(日) 18:30:55理論ベースで言えば確かに >>125 が言わんとすることもわからんでもないが
実装ベースで考えれば >>125 の言う理論は途端に破綻する。
>>125 があげたようなデータを 8bit 表記にすればたかだか256バイトで循環するデータになるし
32bit 表記にすれば上位bitが圧縮可能なデータ群と可す。
が、bit幅可変長表記にすれば、確かに少なくともbit幅固定表記に比べ圧縮し難いデータには
なるだろう。しかし、それはランダム性がないデータと言えるか? これをランダム性のないデータ
だと言うヤツがいても、俺はそれを否定しないが、これがランダム性のないデータとするならあら
ゆる疑似乱数もランダム性がないものと評価するべきだろう。
>>128
ランダム性の定義ではないが、
圧縮アルゴリズムによる評価目的はエントロピーの高さを測ること。
0130デフォルトの名無しさん
2006/05/21(日) 18:37:41付け加えておくと、それはもっとも簡単な疑似乱数列だぞ。
0131デフォルトの名無しさん
2006/05/21(日) 18:43:471,2,3,・・・,2^32までのデータを使えば32bit表記では各ビットパターンは一回ずつ登場する事になるぞ
0132デフォルトの名無しさん
2006/05/21(日) 19:15:14それでも圧縮は可能だろうが。
やっぱり、こんなとこでまともな意見を求めた俺がバカだったか。
こんなやりとり続けても時間の無駄だしもっと生産的なことに時間をつかうよ。じゃぁな。ノシ
0133デフォルトの名無しさん
2006/05/21(日) 19:21:20>そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。
それは唯のハックでは無いだろ?
むしろ、コルモゴロフの定義に忠実すぎるぐらいだ。
ちなみに俺も同じ方法で別のものを評価していたりする。
それはソースコード。
圧縮率が高いコードは間違いなく糞コードだったりする。
圧縮後のファイルサイズは、いわゆるステップ数なんかよりも、
ずっとよい指標になる。
0134デフォルトの名無しさん
2006/05/21(日) 19:30:37基準はどれぐらい?
テキストなんでだいたい 20% ぐらいになるのも普通かと思うんだが。
0135デフォルトの名無しさん
2006/05/21(日) 19:36:20その実行結果について議論をするどころか、
>>117
>てか、他の優れた評価方法とかないの?
>俺も多少は乱数性の評価方法とか調べたけどあまりにもしょぼいしのか見つからなくてよー
とかぬかしている件について、どうよ?
0136デフォルトの名無しさん
2006/05/21(日) 19:41:20むしろ圧縮後のサイズがポイントだな。
圧縮した後のファイルサイズで、
「このアプリは、この程度の規模の複雑さを持っているんだな」
ってのが、意外に分かると思う。
0137デフォルトの名無しさん
2006/05/21(日) 20:01:01圧縮云々を言うならせめて情報理論ぐらい勉強しろよ・・・
0138デフォルトの名無しさん
2006/05/21(日) 20:06:51コメントに日記が書かれていても複雑なプログラムなのかw
0139デフォルトの名無しさん
2006/05/21(日) 20:33:04で?何?
0140デフォルトの名無しさん
2006/05/21(日) 21:38:440141デフォルトの名無しさん
2006/05/22(月) 00:21:49>>114
>そだよ。だけど、極端な話すると100万回やっても同じ値を吐き続けるとってもあほみたいに周期の長い乱数と
>100万回で一週しちゃうんだけどその間のエントロピーは文句なしの乱数のどっちが実用的だと思う?
確かに。
「100万ビットでも同じ値が続いてくれることがありえないと困る」ような乱数の使用法をしてるか否か、ってことだよね。
ゲーム用途なら下位ビットが最悪のrand()の方が人間相手には『確実にランダムっぽく』見える分有利かもしれないな。
でもそれはつまるところ、人間の持つ「ランダムさ」の感覚が
シャノン情報量の大小と一致していないところに問題があるわけだよね。
だから、マジで何万回も同じ値が出続けるかもしれないサイコロ振りより、例えばM系列の方が喜ばれたりする。
難しいねえ。
0142・∀・)っ-○◎● ◆toBASh....
NGNG俺はboost::random::mt19937使ってる
0143デフォルトの名無しさん
2006/05/22(月) 00:37:45そりゃー32bitの乱数なら100万回同じ値になる確率は1/((2^32)^999999)なんだから
そうそう簡単に再現されるわけ無いじゃん。
0144デフォルトの名無しさん
2006/05/22(月) 00:39:24「はじめっからそんな値を吐かないアルゴリズムでも問題ないよな?」
という考え方で、もっと短周期の乱数アルゴリズムが『実用的』とみなされている。
ってこと。
0145デフォルトの名無しさん
2006/05/22(月) 00:42:00同じ使うにしても本家サイトで公開されてる「高速化版」に差し替えた方がいいかも。
(乱数生成アルゴリズムを入れ替えできて、同じインターフェースを提供、ってのがboostのいいところだしな)
0146デフォルトの名無しさん
2006/05/22(月) 00:43:170147デフォルトの名無しさん
2006/05/22(月) 00:46:420148デフォルトの名無しさん
2006/05/22(月) 04:08:13理解度が低い側の人が自分自身の理解度が低いということすらが自覚してなさげだね。
最低限↓このページの最初に書かれていることぐらいは理解したうえで議論すべきだと思うけど。
http://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0
0149デフォルトの名無しさん
2006/05/23(火) 18:43:510150デフォルトの名無しさん
2006/05/23(火) 18:45:47└┘ そうだね
0151デフォルトの名無しさん
2006/05/25(木) 21:30:160152デフォルトの名無しさん
2006/05/25(木) 21:42:010153デフォルトの名無しさん
2006/05/31(水) 02:33:350154デフォルトの名無しさん
2006/05/31(水) 21:39:14ちなみに、暗号化した結果をさらに暗号化して、次の乱数を出していくような形だと、悪い性質が出てきたりするのかな?
0155デフォルトの名無しさん
2006/05/31(水) 22:23:43じゃなくって、生成器Aで作った乱数列を鍵にして生成器Bで乱数列を作る、ってこと?
0156デフォルトの名無しさん
2006/05/31(水) 22:50:20そうであれば、たしかに OFBですね。
0157デフォルトの名無しさん
2006/05/31(水) 22:52:01悪い性質が出てきたりはしない筈…ですかね?
0158デフォルトの名無しさん
2006/06/01(木) 00:25:28全0の数列とXORして結果を得ていると考えればOFBの一種だな
0159デフォルトの名無しさん
2006/06/01(木) 00:26:39その「まともな暗号」を考えるのがムツカシイ
0160デフォルトの名無しさん
2006/06/01(木) 10:58:08154で書いた通り、前提として、AESやtwofishを想定していますけれど。
暗号の世界の死屍累々の歴史を見れば、よほどでなければ俺様暗号を作ろうなんて傲慢な気持ちにはなれないですよね。
AES 選考のときも、ドイツテレコムが採用していた暗号が 10秒で即死したり、笑い話に事欠かない世界…怖いですね。
http://h2np.net/bit/aes-rep.html
0161デフォルトの名無しさん
2006/06/01(木) 13:58:02ハァハァ 読んでて興奮するね。
0162デフォルトの名無しさん
2006/06/03(土) 04:14:33カコイイ!!
0163デフォルトの名無しさん
2006/06/03(土) 05:16:05最終的にAESに選ばれたのはそこで名前すら挙がっていなかったRijndaelだというのも
おもしろいな
0164デフォルトの名無しさん
2006/06/05(月) 00:58:00この二つってそんなに演算早いの?
加減算やローテートは遅い部類なの?
0165デフォルトの名無しさん
2006/06/05(月) 01:32:04加減算は変わりそう
0166デフォルトの名無しさん
2006/06/05(月) 01:42:13命令自体は別に変わらないよ。
M系列でググると分かるけど、
ある周期で全てのビットが0である場合を除いて、
全ての0と1の組み合わせが出現するアルゴリズムがある。
そんでそれはシフトとxorのみで実現する事が出来るというだけ。
これはなかなか自然的な乱数の性質に近くて、
しかもコンピューターに都合のいい形をしている。
で、よく使われる。
加減算やローテートでも実現出来るんじゃないかな。
ただ、周期を大きくするのが難しそうだ。
0167デフォルトの名無しさん
2006/06/05(月) 01:53:02使用する環境が決まってるならCPUに特化した乱数ルーチンもアリだと思う。
0168デフォルトの名無しさん
2006/06/06(火) 17:33:17そのために、RCなんとかコンテストで、PowerPC とかがクロックの割に健闘したりってことがあった気が。
そういえば、CPU自体が(熱雑音とかを使った?)乱数生成器を持っているやつって、あるのかな?
0169デフォルトの名無しさん
2006/06/06(火) 22:10:12ぐぐったら出てきた
ttp://journal.mycom.co.jp/news/2003/01/22/15.html
0170デフォルトの名無しさん
2006/06/07(水) 10:40:12http://www.intel.co.jp/jp/intel/pr/press99/991116.htm
インテル 820 チップセットは〜インテル(R) ランダム・ナンバ・ジェネレータ(乱数生成器)を搭載しています。
0171デフォルトの名無しさん
2006/06/07(水) 20:49:19でも…… ワーキングメモリが2.5倍強ほど必要になってしまう…
ただでさえデカイと評判のMTがさらにでかく…
くそっ、SSEに128ビットアライメント縛りなんてものがなければ……
せめて64ビット縛りならいいのに
0172デフォルトの名無しさん
2006/06/07(水) 21:37:59組み込みで使うならともかく
0173デフォルトの名無しさん
2006/06/07(水) 21:46:05SSE2使おうってCPUならキャッシュで収まるもんね。
気兼ねせず実装することにしますわ。
でもアライメント縛りって本当に鬱陶しいな。スレ違い愚痴スマソ
0174デフォルトの名無しさん
2006/06/07(水) 23:20:13組み込み系だと日常茶飯事だけどw
0175デフォルトの名無しさん
2006/06/11(日) 14:44:380176デフォルトの名無しさん
2006/06/11(日) 16:49:37うpはdvi形式でおk
0177デフォルトの名無しさん
2006/06/11(日) 17:06:53オリジナルのMTも32bit版と64bit版で出力違うから気にしなくていいと思う
0178デフォルトの名無しさん
2006/06/12(月) 06:13:170179デフォルトの名無しさん
2006/06/12(月) 10:48:14そもそも何で乱数に初期化が必要なんだ?
種から生成するアプローチ以外の方法は無いのか?
0180デフォルトの名無しさん
2006/06/12(月) 16:50:290181デフォルトの名無しさん
2006/06/12(月) 18:19:340182デフォルトの名無しさん
2006/06/12(月) 18:21:24心配なら暗号論的乱数で初期化汁、そこまで気にしないならどうでもいい、でFA出ちゃったからね。
0183デフォルトの名無しさん
2006/06/12(月) 18:57:12場合によっては
0184デフォルトの名無しさん
2006/06/13(火) 00:26:320185デフォルトの名無しさん
2006/06/13(火) 00:48:08そんなこと言ってないでなにか話題提供してくれよ
0186デフォルトの名無しさん
2006/06/13(火) 03:09:15(0,1)の擬似乱数をMT19937(作成者のHPからFortranソースを拾ってきた)で発生させて、
その平均値と標準偏差が0.5と0.25になるのを確認しようとしました。
(作者の作成したサンプルデータと同じ結果がでることを確認しました。)
平均値は0.5にかなり近づくんですが、標準偏差が0.28程度になります。
乱数の個数を増やしていくと、0.28程度で収束しているように見えます。
octave(実装されてる乱数生成器)でもやってみたんですが、0.25程度に収束しません。
よろしくお願いします。
0187デフォルトの名無しさん
2006/06/13(火) 04:27:111/sqrt(12) に収束するのは別に何もおかしいところが無いわけだが
乱数の話というよりか確率・統計の話だな
0188デフォルトの名無しさん
2006/06/13(火) 13:49:37ありがとうございます。
たしかに、1/3-(1/2)**2でも0.288...になりました。
0.25と思い込んでいました。
0189デフォルトの名無しさん
2006/06/14(水) 01:07:11それ以前に、メルセンヌツイスタはBSDライセンスのはずなのに
ソースコード中にライセンスについて一切の記述がない事がまずいと思う。
SYN氏、忘れてんのか?
0190デフォルトの名無しさん
2006/06/14(水) 01:13:54AESはフリーなんだっけ?
0191デフォルトの名無しさん
2006/06/14(水) 05:53:410192デフォルトの名無しさん
2006/06/14(水) 21:52:440193デフォルトの名無しさん
2006/06/15(木) 10:46:520194デフォルトの名無しさん
2006/07/08(土) 19:10:200195デフォルトの名無しさん
2006/07/08(土) 22:27:590196デフォルトの名無しさん
2006/07/09(日) 02:16:370197デフォルトの名無しさん
2006/07/09(日) 08:39:000198デフォルトの名無しさん
2006/07/09(日) 09:45:090199デフォルトの名無しさん
2006/07/09(日) 12:52:06決定性チューリングマシンだから。
ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか?
0200デフォルトの名無しさん
2006/07/09(日) 14:55:03つ /dev/random
0201デフォルトの名無しさん
2006/07/09(日) 19:03:50> ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか?
真性乱数は無理。
というか、非決定性チューリングマシンができてしまうと、
今まで暗号論的擬似乱数と呼んでいたものの前提が全て崩れちまうな。
ttp://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0
0202デフォルトの名無しさん
2006/07/10(月) 01:33:58えっと、そんなことはないです、オーダー的に。デタラメ言わないで。
0203201
2006/07/10(月) 02:36:50え、なんでだ?
非決定性チューリングマシンとはNP完全な問題を多項式時間で解くマシン、
すなわち、単純な総当たりで解くしかない(=解くには指数時間かかる)と思われていた問題を
多項式時間で解いてしまうことのできるマシンであるから、
RC4などストリーム暗号で使われる暗号論的擬似乱数列も多項式時間で解けちゃうでしょ。
0204デフォルトの名無しさん
2006/07/10(月) 21:01:48俺が書いた文章だったりするからwww
0205デフォルトの名無しさん
2006/07/10(月) 21:13:30嘘書いたの?
0206デフォルトの名無しさん
2006/07/11(火) 06:52:210207デフォルトの名無しさん
2006/07/11(火) 13:35:06どの乱数列データもまったく圧縮できないorz
0208デフォルトの名無しさん
2006/07/11(火) 18:56:18いやそういう意味じゃないが、非常に照れくさい……
0209デフォルトの名無しさん
2006/07/19(水) 03:02:360210デフォルトの名無しさん
2006/07/19(水) 03:07:160211デフォルトの名無しさん
2006/07/19(水) 12:52:580212デフォルトの名無しさん
2006/07/19(水) 13:08:010213デフォルトの名無しさん
2006/07/19(水) 18:00:52どんなアルゴリズムなの?
0214デフォルトの名無しさん
2006/07/19(水) 18:12:330215デフォルトの名無しさん
2006/07/19(水) 20:30:32狭義のlagged Fibonacciだとa = b = 1.
0216デフォルトの名無しさん
2006/08/26(土) 01:43:170217デフォルトの名無しさん
2006/10/08(日) 06:58:26一様では乱数とは言わない。
特定の周波数幅に対するホワイトノイズ乱数というのなら可能。
この場合は特徴があるが、目的に使う限り特徴は現れにくい。
0218デフォルトの名無しさん
2006/10/08(日) 07:16:59フィルタ使わずそんなもん発生する事できるのか
是非教えてくれ
0219デフォルトの名無しさん
2006/10/09(月) 18:00:370220デフォルトの名無しさん
2006/10/09(月) 18:54:49シャブ打ってラリってそうな響きだ
0221デフォルトの名無しさん
2006/10/09(月) 23:00:54例えば想像する対象をサイコロの目としてみる。
1から6まで均等にでる乱数なら可能だろ
その種類だけ格納するテーブルを作って
確立が高い部分か低い部分を再度乱数を求め補正するだけ
原始的な方法で昔から使われている。
記憶容量に依存するが、多重評価することで要求に対するバランスが測定
可能であれば、それを元に補正するだけでいい。
この方法だと周期はでるが、結果として分かっている周期を補正するのは
容易だろう。
任意の偏りがでるかスペクトルを測定し再評価すればいいだけの話だね。
0222デフォルトの名無しさん
2006/10/10(火) 00:38:32時系列で見ると偏ってるからね。
0223デフォルトの名無しさん
2006/10/10(火) 00:45:37パチンコやスロット台で波が出来るのもこのせい。
0224デフォルトの名無しさん
2006/10/10(火) 01:20:5710年間同じ値が続いても乱数。無限に長い時間からすれば確率的には存在する。
そのぐらい理解しておけ
0225デフォルトの名無しさん
2006/10/10(火) 01:23:04元の擬似乱数にある偏りが表にでただけで偏りがすくないものなら
測定できるような波はでない。
それに波がでたとしてもそれをフィードバックさせるだけで補正は可能。
0226デフォルトの名無しさん
2006/10/10(火) 01:25:250228デフォルトの名無しさん
2006/10/10(火) 19:31:09一様乱数は一様ではないの?
0229デフォルトの名無しさん
2006/10/10(火) 19:40:530230デフォルトの名無しさん
2006/10/10(火) 23:18:000231デフォルトの名無しさん
2006/10/13(金) 14:21:51一様だと周期があるということになるのは理解できない?
一様乱数とは有限の範囲内では周期がないが、それ以上だと
周期がある乱数を言う。
>>224
それは自然乱数の本質だな
>>225
これは正規乱数の類だな。上のwikiに解説してあるからしっかり読んでおけ。
0232228
2006/10/13(金) 17:44:49>一様だと周期があるということになるのは理解できない?
はい。
「一様であること」とは「偏りがないこと」と理解しています。なので、
>それ以上だと
>周期がある乱数を言う。
「一様であること」と「周期があること」の関係が解らないでいるのです。
0233デフォルトの名無しさん
2006/10/14(土) 01:15:080234デフォルトの名無しさん
2006/10/14(土) 02:45:28暗号と情報セキュリティのお勉強はしたけど、正直乱数はよくわからん
0235デフォルトの名無しさん
2006/10/14(土) 03:09:53特定の有限回の試行での一様性が担保されているなら、
それは全く乱数ではない、というのは自明だと思う。
ところで、疑似乱数は内部状態を有限量のデジタルデータで
持つという仕組み上、有限の周期をもつこともまた自明。
なわけで、一様な疑似乱数=乱数ではない、ということになる。
のか?
一様だろうがそうでなかろうが、所詮周期があるという点で
「疑似」乱数でしかないわけだけど、一様性が担保されている
場合は、そうでない(一様かどうか不明な)場合と違って、
周期の終わりの方では次にでる数字を推定しやすくなる。
ギャンブルには使いにくい。
0236デフォルトの名無しさん
2006/10/14(土) 08:34:340237デフォルトの名無しさん
2006/10/14(土) 09:57:420238デフォルトの名無しさん
2006/10/14(土) 10:04:340239デフォルトの名無しさん
2006/10/14(土) 13:11:10ttp://www.optoscience.com/maker/id/id.html
の真性乱数発生器ってのはホンモノなの?
熱雑音を利用したチップやボードはよく見かけるけど、
量子乱数ってのはあまり見かけないような気がするッス
どういう仕組みになってるんだろうか…
0240デフォルトの名無しさん
2006/10/14(土) 13:58:000241デフォルトの名無しさん
2006/10/14(土) 14:48:04いまどき普通のrandを使う理由は?
0242デフォルトの名無しさん
2006/10/14(土) 14:50:22いまどきじゃないrandが存在する理由は?
0243デフォルトの名無しさん
2006/10/14(土) 17:37:21いまどきじゃない方が便利だから
0244デフォルトの名無しさん
2006/10/14(土) 17:40:53重要なのは、目的を達成するための手段として妥当かどうかだよ。
0245デフォルトの名無しさん
2006/10/14(土) 23:00:51ユーザ「なんでここで○○が出て来るんだよ!ありえないだろ!!!」
開発者「MTですから、乱数に変な癖は無いですよ」
ユーザ「そうか・・・偶然じゃあしょうがないな・・・」
みたいな。
0246デフォルトの名無しさん
2006/10/14(土) 23:20:350247デフォルトの名無しさん
2006/10/14(土) 23:36:06作者はもう慶応には居ないってこと?
0248デフォルトの名無しさん
2006/10/14(土) 23:45:00普通に"MT 乱数"とかでググれば出てくると思うが
0249デフォルトの名無しさん
2006/10/16(月) 10:22:550250デフォルトの名無しさん
2006/10/16(月) 12:05:45適当な資料をご存じの方がいたら教えてください。
0252デフォルトの名無しさん
2006/10/18(水) 17:36:16本物?釣り氏?w
0253デフォルトの名無しさん
2006/10/18(水) 18:18:59使うんならあまり問題にならないような気がする。
40万組みのシャフルしたトランプから10枚だけ引くとか。
0254デフォルトの名無しさん
2006/10/18(水) 20:06:33(1)周期があるというのは、別に一様にしようがしまいが疑似乱数である限り言えること
(2)一様乱数の場合は、そうでない疑似乱数と比べて
周期の終わりに近づくにつれてさらに予測しやすくなる
(3)>>231が前半二行で(1)以外の情報を伝えたかったのかどうかは不明
0255デフォルトの名無しさん
2006/10/18(水) 23:53:23(正しく作られた)サイコロは過去の出目に関係なく、次にある数字が出る
確率はすべて等しい。= 一様である。
サイコロを続けて振って得られる数列は一様乱数になる。
ソフトウエアで生成する乱数が原理的に真性乱数になり得ないのは
まったく別の話。一様性とは無関係。
0256デフォルトの名無しさん
2006/10/19(木) 03:41:58悪貨が良貨を駆逐するとはこのことか。
0257デフォルトの名無しさん
2006/10/19(木) 04:10:57やっぱそうなのか
上の話を読んで
「サイコロを6回ふったら、1から6までの目がどれもぴったり1回出る」
が一様乱数かと思って焦ったよ
0258デフォルトの名無しさん
2006/10/19(木) 11:45:46疑似乱数の場合、
>確率はすべて等しい。= 一様である。
ものと、そうでないものがある、というのはわかっていますか?
0259デフォルトの名無しさん
2006/10/19(木) 12:08:06ム板の特徴なのかな
0260デフォルトの名無しさん
2006/10/19(木) 12:16:47(有限の)周期があって、かつ一様な疑似乱数の特性について
教えてください。1周期内では各数字は同じ回数だけ現れますか?
0261デフォルトの名無しさん
2006/10/19(木) 14:32:38なぜ「過去の出目に関係なく」という部分まで引用しない。
重要なところだぞ。
また、間違ってると思ったらどこがどう間違ってるか書いてくれ。
0262デフォルトの名無しさん
2006/10/19(木) 23:38:430263デフォルトの名無しさん
2006/10/20(金) 11:30:26厳密に一様というのは、愚かな考え。
1つの周波数に対して一様なのは可能だが。
0264デフォルトの名無しさん
2006/10/20(金) 22:58:19プロと対峙して「てめぇいかさまだな」とか言われた日には。
0265デフォルトの名無しさん
2006/10/23(月) 11:35:42その日を境に行方不明になると
0266デフォルトの名無しさん
2006/10/25(水) 00:15:58理屈の上の乱数と実際に作れる乱数とは別なことを理解できないとは
愚かだよな。
理屈上のサイコロでも「有限回数」の出目は一様ではない事実、これが何故か
理解できないの池沼に説明しても無駄だから放置だw
0267デフォルトの名無しさん
2006/10/25(水) 00:29:16「どの目も同じ回数出る」と誤解してる人がいて
勘違いしてる人もしてない人も混乱しただけだろ。
0268デフォルトの名無しさん
2006/10/25(水) 00:51:09どの目でも確率分布を一様にさせると言う事は、出る回数が同じになって行くと言う事じゃないのか?
0269デフォルトの名無しさん
2006/10/25(水) 00:56:51そうじゃなくてサイコロを600回振ったら100回1が出る
という意味の「同じ回数」。
出目が一様なサイコロを600回振っても1が100回じゃない
ことの方がずっと多い。
0270デフォルトの名無しさん
2006/10/25(水) 01:02:53100回でも99回でも101回でもいいけど、100回に近くするって事だろ?
99回ならもう一回出そうかな?とか、101回出てたら、もう控えようかな? とか、操作するんだよね?
0271デフォルトの名無しさん
2006/10/25(水) 01:03:44> どの目でも確率分布を一様にさせると言う事は、出る回数が同じになって行くと言う事じゃないのか?
全然違う。
たとえば、n回サイコロを投げて1の目が出た回数をk1、2の目が出た回数をk2とすれば、
nを大きくしていくと k1/n と k2/n はともに 1/6 に収束していく(大数の法則)が、
|k1-k2|の期待値は大きくなっていくんだよ。
0272デフォルトの名無しさん
2006/10/25(水) 01:09:33何の話だ?
まず、そういう操作をしたら一様でなくなってしまう。
過去の出目から未来がある程度予測できてしまうから。
で、そういう操作をする乱数の名前は知らない。
確かに、「誤用の一様」の意味はそれかも。
実用性はありそうだが、名前付いてる?
0273デフォルトの名無しさん
2006/10/25(水) 01:20:30ギャンブルマシンと言われるゲーム機やパチンコ台やスロットの中身
0274デフォルトの名無しさん
2006/10/25(水) 14:07:29しかし、初期条件で全て決定される疑似乱数で各出目の出現回数が違ったら、
それは一様でないということなんじゃないの?
>>273
スロやパチはほとんど真性乱数とみて問題無いよ。
現在スロで主流の方法は、数MHzのクロックを16bitのカウンタで数えていて
レバーが叩かれた時にラッチするというもの。
カウンタが1周する周期が0.03秒とかだから、人間がレバーを叩いているかぎり
ほとんど真性乱数といえる。(だからソレノイドでレバーを叩いて狙う方法が存在する)
0275デフォルトの名無しさん
2006/10/25(水) 23:49:24> (2)一様乱数の場合は、そうでない疑似乱数と比べて
> 周期の終わりに近づくにつれてさらに予測しやすくなる
それは違う。
一様でない疑似乱数、たとえば"1"が1/2の確率で"2"〜"6"がそれぞれ1/10の確率で
出現する疑似乱数列があるとして、その周期の大半を消費したとき"1"の出現率が
1/2より小さければ、周期の残りでは"1"の出現率が1/2より大きくなる。
つまり、次にでる数字を推定しやすいのは、その疑似乱数列の周期と分布が
「既知」であり、その周期に対して十分な長さの過去の乱数列を知っている場合だってこと。
その既知の分布の種類は、一様分布でなく二項分布であってもいいわけだ。
0276デフォルトの名無しさん
2006/10/26(木) 11:02:45サイコロの目のような有限の個数の値が
どの数も確立も一定なら真の乱数ではない。
単なるスペクトルの問題であり、長超周期の乱数を否定しなければ
短期間の乱数の一様性を守ることは不可能だろ。
おまいらが有限と思っている期間でさえ無限に近い乱数の価値観から
すれば短い期間であり、同じ値が続いたとしても確立の1つである。
短い期間が1億回同じ値が続くケースが存在したとしても、
乱数として間違いはない。
つまりだ、人間が扱える乱数とは有限回数の中でどの周波数成分でも
似た値を示すような数値を乱数と判断しているだけ。周期は確実にあり、
実用であるか、どうかの問題にしかすぎない。
プログラム板としては。ライブラリーが提供するような激しく短いビット
数の乱数を使うからこそ周期や特徴が出てしまうだけで、長い周期を
比較的単純なアルゴリズムで作れば問題はありえない。
円周率とか、無限級数でも使えw
0277デフォルトの名無しさん
2006/10/26(木) 15:11:27>それは違う。
中略
>つまり、次にでる数字を推定しやすいのは、その疑似乱数列の周期と分布が
>「既知」であり、その周期に対して十分な長さの過去の乱数列を知っている場合だってこと。
「違う」といいながら同じことを言っているような気がする。
0278デフォルトの名無しさん
2006/10/26(木) 16:44:04何を主張したいのかよくわからんが、
一様の説明で例に出したサイコロは理想的なサイコロで、
理想的なサイコロは完全な一様性を示す。
有限回振ることが前提でも一様性は変わらない。
>>270みたいのを一様だと思っているのか?違うぞ。
>>277
同じことは言ってないだろ。ちゃんと違うよ。
>>254は一様乱数の場合に予測できると書いていて、(←間違い)
>>275は周期と分布が既知の擬似乱数の場合に予測できると書いている。
0279デフォルトの名無しさん
2006/10/26(木) 20:38:54周期の終わりの方を使っていることが解る⇒周期が既知、
が前提なんじゃないのか?分布も「一様」が前提だし。
0280デフォルトの名無しさん
2006/10/26(木) 20:58:11ああ、そういうことか。
>>254(2)は、一様かつ周期があると言っているが、
これは言葉が矛盾してる。周期があったら一様じゃない。
ていうか擬似乱数は一様にならないだろ。
0281デフォルトの名無しさん
2006/10/26(木) 21:28:230282280
2006/10/26(木) 21:34:11>>275は周期のある擬似乱数に関して、
分布が既知ならそれが「一様分布でなくても」
予測ができる、と主張してるんだ。
>>254の勘違いは、一様の意味を>>268のように思っていること。
実際は>>271の言うように一様でも|k1-k2|の期待値は大きくなっていく。
更に、>>268のような数列は乱数ではあり得ない。
一様であるなしに関わらず乱数ならば過去の数列から予測は不可能。
逆に擬似乱数の場合、分布が一様でも何でも既知ならある程度予測ができる。
ということは、>>255も誤解を招く表現だ。
サイコロで次に出る目が過去の出目に関係ない=乱数
サイコロでどの目が出る確率も同じ=一様
擬似乱数に対して一様という言葉を使うかどうかは知らないが、
乱数であるならば既に過去の出目には関係ないので、
過去の出目に関係ないことを言うのに一様を主張する必要はない。
0283デフォルトの名無しさん
2006/10/26(木) 21:48:580284デフォルトの名無しさん
2006/10/27(金) 00:38:08勘違いしているなら、「あ、ちょっと勘違いしてたかも。」は
常識が無い発言だよなw
0285デフォルトの名無しさん
2006/10/27(金) 02:02:260286デフォルトの名無しさん
2006/10/27(金) 02:07:39一様性を「証明」する方が重要じゃないの
0287デフォルトの名無しさん
2006/10/27(金) 23:14:52>>254は「この人はこう言いたかったのかな?」と予想して書いたものなんで悪しからず
>>276
>短い期間が1億回同じ値が続くケースが存在したとしても、
>乱数として間違いはない。
確率分布が一様分布な確率変数のとる値が、たまたま一億回同じ値だったとしても
それは乱数ってことですよね。
(ここのほとんどの人は最初からそれは了解してるように思う)
>つまりだ、人間が扱える乱数とは有限回数の中でどの周波数成分でも
>似た値を示すような数値を乱数と判断しているだけ。
何か数列があって、それがバラバラな値の列だから乱数だ、そうでないから乱数じゃない、ってのは
そもそも違うってことですよね?
「どうやって採られたものか」が重要である、と。
んで
・有限長の数列を用意して、それを乱数として使う場合は
統計的に値の出現頻度が偏っているときに、それを補正することもある
・疑似乱数は有限の長さの数列の後に同じ数列の繰り返しになる
この二点がとりあえず事実ということでおk?
0288デフォルトの名無しさん
2006/10/27(金) 23:15:59×疑似乱数は
〇疑似乱数生成器の出力は
0289デフォルトの名無しさん
2006/10/28(土) 01:02:27ものを利用して乱数の一様性を補正すれば、乱数ではなくなるように勘違い
しているとかか?
極度に短い擬似乱数ではなく、極度に長い周期の乱数を用いて、目的の
一様性が保たれれば変な癖などでないだろ。元にしている擬似乱数が
貧弱すぎるじゃまいか?
0290デフォルトの名無しさん
2006/10/28(土) 08:19:35>統計的に値の出現頻度が偏っているときに、それを補正することもある
どういう補正を考えてるの?
「1が続いたので次に1が出る確率を減らす」ような処理ならばNo。
そのような数列は乱数とは呼ばない。
乱数とは過去のデータにかかわらず常に一定の確率分布を持つもの。
計算によって異なる確率分布の乱数を作る事はある。
例えば、一様分布の乱数を利用して正規分布の乱数を得る等。
0291デフォルトの名無しさん
2006/10/30(月) 01:03:45基本の擬似乱数発生から乱数がでる目の数だけ記録
(1から1000なら1000ビット)
同じ値が出た場合は出てないビットがでるまでか、適当な位置から
出ていない数値を検索しそれを乱数とする。
この場合だと1000回の周期があるが1000回中は同じ値がでないように
できる。
1から1000まで同じ確立で発生し、その発生根本は別の擬似乱数など
から流用すればいい。
これは表面上は同じ値が続かないし元の擬似乱数が乱数的であれば
それなりに使える、例えばシャッフル再生などの音楽プレーヤーの
アルゴリズムなどで採用されている例がある。
0292デフォルトの名無しさん
2006/10/31(火) 17:45:56それがFA?
0293デフォルトの名無しさん
2006/10/31(火) 22:32:18>>>254の勘違いは、一様の意味を>>268のように思っていること。
>実際は>>271の言うように一様でも|k1-k2|の期待値は大きくなっていく。
それは真の乱数の話ではないでしょうか。
このスレでは疑似乱数についてだけ話すようにしないと混乱の元では?
>>更に、>>268のような数列は乱数ではあり得ない。
これも同様。
0294デフォルトの名無しさん
2006/10/31(火) 22:41:15それは乱数というよりシャフルというかなんというか。
それはともかくとして、確率分布を補正する方法としては
目的の分布をもつ真の乱数列からなる適当なサイズの乱数表があれば、
疑似乱数でその表のn番目を拾ってゆくような方法があるような気がする。
どれくらいの大きさの表が必要なのかはよく分からないけど。
0295デフォルトの名無しさん
2006/10/31(火) 22:47:130296デフォルトの名無しさん
2006/10/31(火) 23:11:02その通りだ。混乱しそうな場合は単に乱数と言わず、
「真の乱数」「擬似乱数」と言った方がいいね。
>>282は真の乱数のつもりで話している。
擬似乱数に対して一様という言葉を使ったら、
単に擬似乱数の周期の中でどの数が出る回数も同じという意味だよな。
1,2,3,4,1,2,3,4,・・・という周期的な擬似乱数(質は最悪だが)も、一様ということになる。
こういう使い方は正しい?
0297デフォルトの名無しさん
2006/10/31(火) 23:26:51> 1,2,3,4,1,2,3,4,・・・という周期的な擬似乱数(質は最悪だが)
そこまで短い周期の数列を「擬似乱数」と呼ぶのは変だと思う。
「擬似」乱数なんだから、ある程度は真の乱数の代替に使えるくらいの
性質を持ってないと。
だから、ちょっとやそっとじゃ一周できないくらいの長い周期を持っていることは
「擬似乱数」と名乗るための重要なファクターだと思う。
0298デフォルトの名無しさん
2006/10/31(火) 23:30:17つまり、ある程度乱数っぽい列に対しては
一様乱数という言葉を296の意味で使っていいということ?
0299デフォルトの名無しさん
2006/10/31(火) 23:58:370300デフォルトの名無しさん
2006/11/01(水) 00:24:541億桁目までの数字の偏りとかじゃなくて、本質的にわかっている部分で。
0301デフォルトの名無しさん
2006/11/01(水) 00:43:21今まで出た数値が円周率の数値と同じならば、次に出る数値は計算によって算出可能。
この事は、予測可能な事を意味する。
よって乱数ではない。
0302デフォルトの名無しさん
2006/11/01(水) 01:37:13下手な疑似乱数より周期長くていいぞw
0303300
2006/11/01(水) 01:42:15> 今まで出た数値が円周率の数値と同じならば、次に出る数値は計算によって算出可能。
円周率に近い別の無理数かもしれない。例えばπ+1/√(10^1000+1)とか。
で、俺が聞きたかったのはそういうことではなくて、
例えば円周率の10^1000+1桁目から10^1000+10^20桁目までの列と、
真性乱数の10^20個の列を与えられたときにある程度の区別が付くか、ということ。
わかりにくくてスマソ。
0304デフォルトの名無しさん
2006/11/01(水) 06:39:59数列だけを比較して区別するなんて不可能でしょ。
0305デフォルトの名無しさん
2006/11/01(水) 08:08:48そんなことはわかっている。
だが、例えば「1の後には2が来やすい」のような傾向があれば
十分な長さの列があればほぼ確実に判定できるだろ。
0306デフォルトの名無しさん
2006/11/01(水) 09:02:290307デフォルトの名無しさん
2006/11/01(水) 23:39:31ttp://www.faireal.net/articles/4/23/#d60401
0308デフォルトの名無しさん
2006/11/01(水) 23:53:09あのカスラックなら本当に言い出しかねんな
0309デフォルトの名無しさん
2006/11/02(木) 00:34:57無限に続くものは任意の桁まで計算できない。
理由は、計算するまでに宇宙が終わるw
人類も機械も消える。
愚かだなw
0310デフォルトの名無しさん
2006/11/02(木) 00:48:07「無限桁目にします」
0311デフォルトの名無しさん
2006/11/02(木) 01:07:130312デフォルトの名無しさん
2006/11/02(木) 01:47:41というのは、ガセ。
0313デフォルトの名無しさん
2006/11/02(木) 02:56:590314デフォルトの名無しさん
2006/11/02(木) 03:57:58要するにマンコ
0315デフォルトの名無しさん
2006/11/02(木) 14:23:01象が支えて亀が歩いているんだ。
宇宙があるなんて都市伝説だ。
0316デフォルトの名無しさん
2006/11/02(木) 20:25:42これは全部俺の妄想だ、夢だ。
0317デフォルトの名無しさん
2006/11/03(金) 04:02:16お前今「嘘」ってWOP使うの避けたろ
0318デフォルトの名無しさん
2006/11/03(金) 12:40:490319デフォルトの名無しさん
2006/11/03(金) 12:57:370320デフォルトの名無しさん
2006/11/04(土) 02:58:270321デフォルトの名無しさん
2006/11/04(土) 04:25:470322デフォルトの名無しさん
2006/11/06(月) 00:48:310323デフォルトの名無しさん
2006/11/10(金) 15:09:58短い周期なら乱数だろ?0と1の2種類とかw
0324デフォルトの名無しさん
2006/11/10(金) 17:27:29最初は[1,n]の乱数で、次は[1,n-1]の乱数…と発生させてその出力を使えば同じこと。
0325デフォルトの名無しさん
2006/11/23(木) 11:03:50なりやすい擬似乱数だろ?
プロセッサのリヤルタイムクロックに同期するようなプログラムはほぼ
困難というか事実上は不可能だろうから
それでも利用すればいいんじゃないか?連続に高速で利用する場合も
考慮して乱数テーブルでも用意してミックスすればよさげ。
0326デフォルトの名無しさん
2006/11/23(木) 11:06:39http://www.t-rs.co.jp/products/p-5/index_j.htm
0327デフォルトの名無しさん
2006/11/23(木) 12:08:13擬似乱数を発生させたいんだけど
不確定要素が無いので種がいつも同じなので
動作が常に一定になってしまい
擬似乱数にならないのです
どうしたらいいのでしょうか?
0328デフォルトの名無しさん
2006/11/23(木) 13:45:000329デフォルトの名無しさん
2006/11/23(木) 13:55:210330デフォルトの名無しさん
2006/11/23(木) 14:10:35よく使う手だけど
メモリをちょっと壊す
0331デフォルトの名無しさん
2006/11/23(木) 15:13:12人間に2回何かさせる。
0332デフォルトの名無しさん
2006/11/23(木) 15:15:11原理的に不確定要素が必要だから、何とかするしかない。
メモリ状態、ユーザの入力、CPUjの状態、
それでもダメなら種を予め手入力しておく。
0333327
2006/11/23(木) 16:19:37アドバイスありがとうございました
0334デフォルトの名無しさん
2006/11/23(木) 20:23:100335デフォルトの名無しさん
2006/11/26(日) 12:39:360336デフォルトの名無しさん
2006/11/26(日) 17:18:11ずっとHLTでもしてるのか?
0337デフォルトの名無しさん
2006/11/26(日) 18:21:36初期値がクリアされているシングルスレッドではないかと・・・
いや、やっぱずっとHLTかな・・・
0338デフォルトの名無しさん
2006/11/28(火) 05:08:43昔と違ってOSが動いているPCなら普通に不確定要素のタイミングで
動いている。
CPUコアのリヤルタイムクロックとアイドリングで動くカウンター要素
等を組み合わせても不確定要素を簡単に抽出可能だろ。
ワンチップマイコンや電子回路程度では話は変わってくるだろうけどな
0339デフォルトの名無しさん
2006/11/28(火) 05:11:250340デフォルトの名無しさん
2006/11/28(火) 08:05:300341デフォルトの名無しさん
2006/11/28(火) 13:50:36プーチン政権を批判するロシア人に持たせれば
良質な乱数が作れそうだな。
0342デフォルトの名無しさん
2006/11/28(火) 14:57:40All1で乱数にならない罠。
0343デフォルトの名無しさん
2006/11/29(水) 16:51:410344デフォルトの名無しさん
2006/11/30(木) 12:06:530345デフォルトの名無しさん
2006/12/02(土) 22:43:18>で、おまいらがほしい乱数とは、数値が連続せず、どの数値も同じ確立に
>なりやすい擬似乱数だろ?
このへんが少し困るところだよな。
人によっては(もしかするとかなり多くの人が)その方がランダムだと
思っちゃうんだよな。
もしサイコロで6が5回位続いたら仕込んであると怪しまれそう。
同じ目が続かない方が乱数としてはおかしいんだけどな。
短周期で目の分布がいつも揃ってたらそれもおかしいし。
52314ときたら次は6だろうみたいな。
人の感じる乱数性は真の乱数性とは違うんだろう。
0346デフォルトの名無しさん
2006/12/03(日) 22:06:11人がランダムと感じることこそが重要だが、
こういう擬似乱数列を得る手法で有名どころとかある?
0347デフォルトの名無しさん
2006/12/03(日) 22:46:36単なるシャッフル再生じゃダメなのけ?
0348デフォルトの名無しさん
2006/12/03(日) 23:13:51某MP3プレーヤのシャッフルリピートは同じ曲を3回繰り返したし、
某なんとかシャッフルのシャッフルリピートは同じ曲を一回おきに3回繰り返した。
0349347
2006/12/03(日) 23:41:42ランダム再生
… 一曲終わるたびに、次に再生する曲を全プレイリストの中からランダムに選ぶ。
シャッフル再生
… 再生開始時にプレイリストの一覧をシャッフルしたものを内部的に作り、
その順序にしたがって再生する。プレイリストの全曲を再生し終わったら
もう一度プレイリストをシャッフルする。
この分類だと、>348のようなことはランダム再生だと起こりうるが、
シャッフル再生だと起こらない。
0350デフォルトの名無しさん
2006/12/03(日) 23:54:15言われてみればそうだな。連続出現の心配はなくなるわけだ。
あとで思い出したが、同じアルバムの曲が10曲中3曲もあるから
ランダムじゃないと感じることもある。
まあこれもバラし方を考えればいいだけで、
乱数の発生方法とは関係ない話だったな。
0351デフォルトの名無しさん
2006/12/04(月) 11:10:31>>324みたいな乱数列を作ればいい訳で
0352デフォルトの名無しさん
2006/12/05(火) 13:57:14擬似乱数なんだから乱数を元にしたシャッフルで問題ないだろ。
現実のサイコロにしても目の数の周期性はあるわけだし。
※理論的なサイコロではない。
単に乱数に拘るのは周期が短いライブラリーなどにある乱数関数を使うと
規則性が表面に出て見えることがある。
この点であると思う。真の乱数であるなばら規則性が目立っても
それは一時的(数年続いても無限からすれば極短期間)な挙動であって
乱数である。
何かの規則で一様性な分布がほしいのであれば「無限級数」等を使えば
言い訳で、人間から見て一様乱数にみえるのはシャッフルがもっとも
近いものじゃないか?
0353デフォルトの名無しさん
2006/12/05(火) 18:28:56ぐだぐだな日本語に気持ち悪くなってくる。
>擬似乱数なんだから乱数を元にしたシャッフルで問題ないだろ。
シャッフルな用途にはシャッフルで問題ない。シャッフルでは困る用途もきっとある。
>現実のサイコロにしても目の数の周期性はあるわけだし。
現実のサイコロに周期性など無い。ってか「目の数の周期性」って何?
>単に乱数に拘るのは周期が短いライブラリーなどにある乱数関数を使うと
>規則性が表面に出て見えることがある。
この文は「周期が短い乱数関数を使うと規則性が見える。」でよいか?
(冒頭の「単に乱数に拘るのは」はなんなんだろう?)
>この点であると思う。
何が??
>真の乱数であるなばら規則性が目立っても
>それは一時的(数年続いても無限からすれば極短期間)な挙動であって
>乱数である。
最後の「乱数である。」はいらない。「挙動である。」で締めましょう。
>何かの規則で一様性な分布がほしいのであれば「無限級数」等を使えば言い訳で、
無限級数なんて関係無いでしょう。級数=数列の和 ですよ。
>人間から見て一様乱数にみえるのはシャッフルがもっとも
>近いものじゃないか?
人がどう見るかなんて、その人によるとしか言えない。
一巡するまで同じものが出ないものは一様乱数にみえないって人もいるだろう。
0354デフォルトの名無しさん
2006/12/06(水) 00:16:44ttp://bugfix.jp/blog/culdceptsaga/2006/12/post_42.html
0355デフォルトの名無しさん
2006/12/06(水) 10:33:38釣り氏?
0356287
2006/12/06(水) 15:34:10>>統計的に値の出現頻度が偏っているときに、それを補正することもある
>どういう補正を考えてるの?
全然わからないです.というか
>「1が続いたので次に1が出る確率を減らす」ような処理ならばNo。
>そのような数列は乱数とは呼ばない。
>乱数とは過去のデータにかかわらず常に一定の確率分布を持つもの。
私もそう思う(そういう定義しか知らない)ので・・・
0357デフォルトの名無しさん
2006/12/08(金) 23:57:04ここは擬似乱数のところだから、真の乱数、つまり論理的な真の乱数を
言うのならそれなりの説明が必要とおもわれる。
実際に必要とされるのは真の乱数ではなく、擬似乱数であり
擬似乱数にはいろいろ種類があり、用途別に話しを展開しなければ
無意味な議論じゃないのか?
0358デフォルトの名無しさん
2007/01/06(土) 20:21:250359デフォルトの名無しさん
2007/01/31(水) 23:01:07しょ、詳細を…
0360デフォルトの名無しさん
2007/02/01(木) 22:52:43カオスのバタフライ現象を簡易化した形を使うのが簡易です。
シフトとビット操作で比較的簡単に作れる。
放送大学で具体的手法まで解説していたよ。
全体を均一にしたい場合はCDプレイヤーなどで
使われるシャッフルのアルゴリズムが一番簡易です。
0〜999の間なら1000ビットのRAMが最低必要になりますが。
0361デフォルトの名無しさん
2007/02/02(金) 08:09:20#中には同じ曲が連続しやがるCDプレイヤも一回置きに繰り返すCDプレイヤもあるのだが。
0362デフォルトの名無しさん
2007/02/02(金) 08:46:340363デフォルトの名無しさん
2007/02/02(金) 09:17:280364デフォルトの名無しさん
2007/02/02(金) 16:31:17Morph Rateとか名づけてたっけ
0365デフォルトの名無しさん
2007/02/02(金) 16:32:05Winampはオプションで完全なシャッフルから完全なランダムまで変化の度合いを
0366デフォルトの名無しさん
2007/02/02(金) 22:52:08シャッフルを正しく実装しているものは同じ曲をバラバラにすべての曲を
1回づつ再生する機能のこと。
ランダム再生をしているのにシャッフルと名前を付けている
のは単に誤訳か、まがい物じゃないか?
http://e-words.jp/w/E382B7E383A3E38383E38395E383ABE5868DE7949F.html
0367デフォルトの名無しさん
2007/02/02(金) 22:54:160368デフォルトの名無しさん
2007/02/02(金) 23:50:08iPodShuffule訴えてくれ。
0369デフォルトの名無しさん
2007/02/03(土) 22:08:43アップルに騙されたオマイがDQN
0370デフォルトの名無しさん
2007/02/11(日) 10:15:460371デフォルトの名無しさん
2007/02/11(日) 10:25:270372デフォルトの名無しさん
2007/02/11(日) 10:53:43ttp://ja.wikipedia.org/wiki/擬似乱数
0373デフォルトの名無しさん
2007/02/11(日) 11:21:27地球上でもっとも虐げられている擬似乱数アルゴリズムは
やっぱ線形合同法なんじゃね?
0374デフォルトの名無しさん
2007/02/11(日) 18:07:285かけて1足してffでマスク
0375デフォルトの名無しさん
2007/02/14(水) 06:24:21擬似バタフライ効果があれば何でもいいんじゃない?
0376デフォルトの名無しさん
2007/03/06(火) 15:47:49常に定数を返す擬似乱数がもっとも周期が短い。
これより周期の短い擬似乱数はない。
0377デフォルトの名無しさん
2007/03/06(火) 22:46:090378デフォルトの名無しさん
2007/03/07(水) 07:58:43何も返さない擬似乱数は分布が偏っているとは言えない。
何も返さない擬似乱数は擬似乱数テストプログラムをテストするために使えない。
370の目的はたぶん最後のコレ。
0379デフォルトの名無しさん
2007/03/07(水) 20:58:47定数ってだけじゃなく1bitであるべき(どうしても int にするなら 0 or -1)だろうな。
そうじゃないとbit単位のストリームとして見たときにbit数分の周期が存在することになる。
0380デフォルトの名無しさん
2007/03/08(木) 08:13:45そして、0超過状態からの脱出という観点からは0であるべきだな。
0381171
2007/04/10(火) 04:02:15まあ俺が以前いってたSIMD対応はメモリ上の並びをパズルみたいにコチョコチョいじるだけで
メモリ使用量も増やさず意外と簡単にできたんだが、
それ以外の改良となると、やっぱじっくり研究しないといかんわな。
悔しいが現役の学生にはかなわん。これは認めておいて、
とりあえずコード読んで高速化の余地を探すとするか。
0382デフォルトの名無しさん
2007/04/10(火) 04:26:310383382(乱数の精度判定)
2007/04/10(火) 05:08:58#include <stdlib.h>
#define N 2147483647
#define kaisu 10000000
#define PI 3.141592653589
unsigned int ransuusyokiti=1;
double rnd(){
ransuusyokiti=(int)(1664525*(double)ransuusyokiti+1013904223)&N;
return ransuusyokiti/((double)N+1);}
int main(){
unsigned int i;
double n=0.0,x,y;
for(i=0;i<kaisu;i++){
x=rnd();y=rnd();
if(x*x+y*y<=1.0)n+=1;}
printf("自前のrandの精度(値が小さいほど良い) %1.9f\n",4*n/kaisu-PI);
n=0.0;
for(i=0;i<kaisu;i++){
x=rand()/(RAND_MAX+1.0);y=rand()/(RAND_MAX+1.0);
if(x*x+y*y<=1.0)n+=1;}
printf(" Cのrandの精度(値が小さいほど良い) %1.9f\n",4*n/kaisu-PI);
return 0;}
0384382 改良版
2007/04/10(火) 05:40:20#include <stdlib.h>
#include <math.h>
#include <time.h>
#define N 2147483647
#define kaisu 50000000
#define PI 3.141592653589
unsigned int ransuusyokiti=1;double rnd(){
ransuusyokiti=(int)(1664525*(double)ransuusyokiti+1013904223)&N;
return ransuusyokiti/((double)N+1);}
double xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return(double)( w=(w^(w>>19))^(t^(t>>8)) )/4294967296; }
double xorHoge(){
static unsigned long x=123,y=456,z=78,w=90;unsigned long t;
t=(x^(x<<13));x=y;y=z;z=w; return(double)( w=(w^(w>>7))^(t^(t>>5)) )/4294967296; }
main(){unsigned int i,t;double n,x,y;
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=xor128();y=xor128();if(x*x+y*y<=1.0)n+=1;}
printf(">>18のrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=xorHoge();y=xorHoge();if(x*x+y*y<=1.0)n+=1;}
printf(">>84のrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=rnd();y=rnd();if(x*x+y*y<=1.0)n+=1;}
printf("自前のrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=rand()/(RAND_MAX+1.0);y=rand()/(RAND_MAX+1.0);if(x*x+y*y<=1.0)n+=1;}
printf(" Cのrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);}
0385382
2007/04/10(火) 05:43:38>>18のrandの精度(値が小さいほど良い) 0.000233346 生成速度8.329000秒
>>84のrandの精度(値が小さいほど良い) 0.000106306 生成速度8.171000秒
自前のrandの精度(値が小さいほど良い) 0.000263426 生成速度19.563000秒
Cのrandの精度(値が小さいほど良い) 0.000001454 生成速度9.734000秒
0386CryptGenRandomはいまいち
2007/04/10(火) 06:28:12#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <time.h>
#define N 2147483647
#define kaisu 200
#define PI 3.141592653589
double win_rand(){
HCRYPTPROV hProv;BYTE b[4];
CryptAcquireContext(&hProv, NULL, NULL, PROV_RSA_FULL, 0);
CryptGenRandom(hProv, 4, b);CryptReleaseContext(hProv, 0);
return (double)(b[0]+(b[1]<<8)+(b[2]<<16)+((b[3]&127)<<24))/2147483648;}
double xor128(){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return(double)( w=(w^(w>>19))^(t^(t>>8)) )/4294967296; }
double xorHoge(){
static unsigned long x=123,y=456,z=78,w=90;unsigned long t;
t=(x^(x<<13));x=y;y=z;z=w; return(double)( w=(w^(w>>7))^(t^(t>>5)) )/4294967296; }
main(){unsigned int i,t;double n,x,y;
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=xor128();y=xor128();if(x*x+y*y<=1.0)n+=1;}
printf(">>18のrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=xorHoge();y=xorHoge();if(x*x+y*y<=1.0)n+=1;}
printf(">>84のrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=rand()/(RAND_MAX+1.0);y=rand()/(RAND_MAX+1.0);if(x*x+y*y<=1.0)n+=1;}
printf(" Cのrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
n=0.0;t=clock();for(i=0;i<kaisu;i++){x=win_rand();y=win_rand();if(x*x+y*y<=1.0)n+=1;}
printf(" winのrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);}
0387デフォルトの名無しさん
2007/04/10(火) 12:22:010388デフォルトの名無しさん
2007/04/11(水) 01:36:140389デフォルトの名無しさん
2007/04/11(水) 02:34:04いって近似がパイに近づかなくなる回数を調べる事も重要
0390デフォルトの名無しさん
2007/04/11(水) 16:34:530391デフォルトの名無しさん
2007/04/11(水) 21:27:44この精度がいいと(あるいは悪いと)どういう乱数ってことになるの?
あと、なんで win_rand() だけ 1 bit 捨ててんの?
0392デフォルトの名無しさん
2007/04/16(月) 16:57:12円周率は、3.1415である
正方形(サイズは40000とする)の内部にランダムに
点を4万回打てば、それに内接する円の内部に点が打たれる回数は
31415回程度になる
試行回数を増やせば増やすほど円周率にちかずく
ここで乱数の生成が均等であるほど近くなる
0393デフォルトの名無しさん
2007/04/16(月) 20:00:370394デフォルトの名無しさん
2007/04/16(月) 20:59:09�d。
win_rand() で 1 bit 捨ててんのはなんで?
0395デフォルトの名無しさん
2007/04/16(月) 21:15:240396デフォルトの名無しさん
2007/04/16(月) 21:25:48それはなんかチョンボってないか?
俺んとこじゃ
return (double)(b[0]+(b[1]<<8)+(b[2]<<16)+(b[3]<<24))/4294967296;
で、エラーにはならんし。kaisu を 1000000あたりで試行した時は
win_rand() が断トツの精度を誇るぞ。
# 処理に要する時間も断トツだけどw
0397デフォルトの名無しさん
2007/04/16(月) 22:10:39共立じゃなくてサイエンス社
0398デフォルトの名無しさん
2007/04/16(月) 22:12:250399デフォルトの名無しさん
2007/04/17(火) 01:51:37というか実質的には最強。
とりあえずwikiでも読んでみなよ。
0400デフォルトの名無しさん
2007/04/17(火) 07:06:41SIMD-oriented Fast Mersenne Twister (SFMT):
ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
0401デフォルトの名無しさん
2007/04/17(火) 19:30:13これでしばらくMTの系譜が続くのは確定だな
0402デフォルトの名無しさん
2007/04/17(火) 22:40:440403デフォルトの名無しさん
2007/04/18(水) 00:14:07ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html
0404デフォルトの名無しさん
2007/04/18(水) 10:51:220405デフォルトの名無しさん
2007/04/19(木) 20:33:08>>404
だからSFMTでは短周期版も作ったんじゃないか
0406デフォルトの名無しさん
2007/07/04(水) 20:56:270407デフォルトの名無しさん
2007/07/08(日) 00:18:50単にカオスの簡単な例「2重振り子」を演算で出しただけじゃん。
適度に内部ビット数増やせば、周期なんて測定不能な域にするのは容易じゃん。
ワンチップとかの超小型マイコンで作るんじゃないんだし、今のPCなら
乱数で使うメモリは捨てるほどあるわけだしな。
0408デフォルトの名無しさん
2007/07/08(日) 00:29:35それを実装したことに意味があるんじゃん。
…って開発者が言ってた。
0409デフォルトの名無しさん
2007/07/09(月) 23:43:55似た事を主張した奴とか類似物を作ったやつも、正式に論文発表しなかった
だけにすぎない。
0410デフォルトの名無しさん
2007/07/10(火) 09:47:420411デフォルトの名無しさん
2007/07/10(火) 09:52:530412デフォルトの名無しさん
2007/07/10(火) 10:22:530413デフォルトの名無しさん
2007/07/10(火) 13:30:58せめて西ジパング諸島と呼ぶべきだったと思う。
0414デフォルトの名無しさん
2007/07/10(火) 15:29:18遺伝子確認で分かっている点について(ry
0415デフォルトの名無しさん
2007/07/10(火) 20:29:40コロンブスチームのマーケティングの勝利
0416デフォルトの名無しさん
2007/07/10(火) 20:40:370417デフォルトの名無しさん
2007/07/11(水) 01:10:25荒縄静香を思い出した
確かWeb魚拓は取っといたはずだけど どこいっちゃたtかな
0418デフォルトの名無しさん
2007/07/11(水) 01:16:28ttp://news21.2ch.net/test/read.cgi/news4plus/1183572310/l50
0419・∀・)っ-○◎●
2007/07/11(水) 01:22:51斉藤君に連絡とってみるかな。
個人的にはSSE2非対応CPU向けにMMX版くらいは欲しいんだが。
本人が動いてくれるくれないにかかわらず、SSE2版だけならVC8/ICC用の
クラスを作ってみようと思うが。どうせ俺が使うし。
0420デフォルトの名無しさん
2007/07/11(水) 01:28:040421・∀・)っ-○◎●
2007/07/11(水) 01:34:190422・∀・)っ-○◎●
2007/07/11(水) 01:59:55スレッド毎にインスタンス生成すればスレッドセーフうめぇwwww
0423デフォルトの名無しさん
2007/07/11(水) 02:17:060424・∀・)っ-○◎●
2007/07/11(水) 07:26:20BoostのRNGは全部クラス化してあって一時計算領域もインスタンス毎に生成するからスレッドセーフなのよ
0425デフォルトの名無しさん
2007/07/11(水) 07:55:000426デフォルトの名無しさん
2007/07/12(木) 08:19:100427デフォルトの名無しさん
2007/07/12(木) 21:44:580428デフォルトの名無しさん
2007/07/12(木) 22:28:420429デフォルトの名無しさん
2007/07/12(木) 22:36:080430デフォルトの名無しさん
2007/07/12(木) 23:29:54Transport Layer Security
Thread Local Storage
True Love Story
いろいろあるんだな……
0431デフォルトの名無しさん
2007/07/13(金) 02:11:06確かに複数スレッドからの同時アクセスの点では良いのだが
例えばよく使われるsrand()はどうするのか。
スレッド毎にsrand()を呼ぶのか
あるいはsrand()の内部でスレッドを数え上げるのか
srand(time(NULL))の後にスレッドを作成したらどうなるのか
↑を最初に一度だけ呼んである過去のコードの扱いはどうなるのか
等々、面倒くさいことがありすぎるよ。
まともなコードで、srand()を呼ばずにrand()を使っているものがあるとは思えないし。
もちろん、「標準のrand()」を置き換えるのではなく
「自分で使う乱数生成器」をどうするか、という話なら
好きなようにどうぞ、というだけだけど。
0432・∀・)っ-○◎●
2007/07/13(金) 03:11:46種は現在時間+スレッドID+GUID/UUID+HDDシークタイムからとった自然乱数もどき+・・・・
見たいな感じでいろいろ組み合わせればよくね?
最近のMTの派生実装は種を配列で与えることができるんで、ユニークな乱数列になるように
なるべく多くのパラメータを与えるといい。
MTは種さえ被らせなきゃそこそこうまくバラけてくれる。
0433デフォルトの名無しさん
2007/07/13(金) 08:20:030434デフォルトの名無しさん
2007/07/13(金) 09:29:570435デフォルトの名無しさん
2007/07/13(金) 12:42:16プロセスを分ければいいと言われると返す言葉がないがね。
0436デフォルトの名無しさん
2007/07/13(金) 22:15:41double win_rand2(HCRYPTPROV hProv){BYTE b[4];CryptGenRandom(hProv, 4, b);
return (double)(b[0]+(b[1]<<8)+(b[2]<<16)+((b[3]&127)<<24))/2147483648;}
n=0.0;t=clock();HCRYPTPROV hProv;CryptAcquireContext(&hProv, NULL, NULL, PROV_RSA_FULL, 0);
for(i=0;i<kaisu;i++){x=win_rand2(hProv);y=win_rand2(hProv);if(x*x+y*y<=1.0)n+=1;}
CryptReleaseContext(hProv, 0);
printf(" winのrandの精度(値が小さいほど良い) %1.9f 生成速度%f秒\n",fabs(4*n/kaisu-PI),(double)(clock()-t)/1000);
0437デフォルトの名無しさん
2007/07/16(月) 21:40:05GetRandomじゃないのか?
0438デフォルトの名無しさん
2007/07/17(火) 19:01:44おじいちゃんがゆってた。
0439デフォルトの名無しさん
2007/07/18(水) 00:24:49すなわち「おじいちゃんの名前(ゲンじいちゃん)」
え?ちがう?
0440デフォルトの名無しさん
2007/07/18(水) 00:29:360441デフォルトの名無しさん
2007/07/18(水) 14:32:340442デフォルトの名無しさん
2007/07/19(木) 22:22:22擬似乱数として性能がいいのか調べる方法はある?1から10までの分布は
それらしくなっているんだけどな。
0443・∀・)っ-○◎●
2007/07/19(木) 23:57:250444デフォルトの名無しさん
2007/07/20(金) 13:54:110445デフォルトの名無しさん
2007/07/21(土) 07:35:38どっかに基準とはる判定方法があったかも
0446デフォルトの名無しさん
2007/07/21(土) 09:09:19DieHarder: A Random Number Test Suite
Robert G. Brown's General Tools Page
http://www.phy.duke.edu/~rgb/General/dieharder.php
0447デフォルトの名無しさん
2007/07/21(土) 19:11:11乱数検定の定番だな
0448デフォルトの名無しさん
2007/08/15(水) 00:44:29圧縮率を見るのってどうなの?
邪道?
0449デフォルトの名無しさん
2007/08/16(木) 05:35:50zipで圧縮して50%になる乱数とかはそもそも論外だし。
はっきりした規則性があるのに圧縮率は低い、といった
データを作るのは簡単だから。
0450デフォルトの名無しさん
2007/08/21(火) 10:53:40擬似乱数のテストは、あとはWELLの設計者たちによるtestU01くらいか。
0451デフォルトの名無しさん
2007/08/26(日) 21:01:21http://www.trickpalace.net/column/random.htm
0452デフォルトの名無しさん
2007/08/27(月) 12:58:390453デフォルトの名無しさん
2007/08/27(月) 13:56:24再現性があるから疑似乱数だよ。
0454デフォルトの名無しさん
2007/08/27(月) 17:41:510455デフォルトの名無しさん
2007/08/27(月) 18:06:37( ´∀`)
0456デフォルトの名無しさん
2007/08/27(月) 20:00:31PCで見た時と携帯で見た時で番号がずれてるぞ。
0457デフォルトの名無しさん
2007/08/27(月) 20:35:390458デフォルトの名無しさん
2007/08/27(月) 23:13:25初期化以外の部分ってどこのこと?
0459デフォルトの名無しさん
2007/08/28(火) 06:44:04その中に >>451 みたいな思想のヤツってないの?
0460デフォルトの名無しさん
2007/08/28(火) 09:15:37なんかよく分からんがテーブルの中からいくつかの要素を取り出して
XORして出力してるのかな?
テーブルの状態次第でビットの出現比に偏りがでそうな気がするんだが。
0462デフォルトの名無しさん
2007/08/28(火) 11:08:48101 * 103 * 107 * 109 * 113 * 127 = 1741209542339 ≒ 10^12 ≒ 2^36
0463デフォルトの名無しさん
2007/08/28(火) 11:50:34現状では出現比を特定できないほど巨大なテープルを用意できると
考えるのが妥当じゃないか?
気がするレベルではなく、偏りが計測できなければ、微小の偏りなど
有効誤差の範囲でしょう。
乱数であるかぎり特定の位置と周期でみれば偏りは常に存在する。
言語に付属するライブラリーが吐く擬似乱数が余りにも周期が短く
偏るためにいろいろ別の方法を試す奴が多いが、目的ごとにその方法論は
変わってくる。例えば組み込みの4KB以下のROMしかないマイコン用の
擬似乱数と考えれば偏りの無い性能より超コンパクトで一様に出るほうが
無難である。大量の計算を必要とする模擬計算などでは応答性の速度が
重要だったりする。あまりにも複雑な計算をして結果を生むより、適度に
妥協するのが擬似乱数の役割で、何が一番良いというのはありえないと思うが。
0464デフォルトの名無しさん
2007/08/28(火) 17:21:17巨大なテーブルにエントロピーを満たすのがえらい大変だと思う
>>462
かけ算だから細かく分けた方が周期が長くなる
MTと同程度のメモリとすると2番目の素数から20番目の素数までぐらい
Sum[Prime[i],{i,2, 20}]
637
最大周期は十進数の桁で
N[Log[10, Product[Prime[i],{i,2, 20}]], 5]
26.446
二進数の桁で、
N[Log[2, Product[Prime[i],{i,2, 20}]], 5]
87.850
最低周期は,エントロピープールから持って来ている以上、
全部おんなじ値という可能性が否定出来ない。よって1
0465デフォルトの名無しさん
2007/08/28(火) 18:46:39これイイな。
ちょっと乱数が欲しい時にちょうどいい。
MT使う程でもないけど線形合同法は気分的に嫌なんだよな。
下位ビットになるほど周期が短くなるのがな。
こういうの他にないのかな?
2^64 - 2^128位の周期で速くてメモリ使わないやつ。
0466デフォルトの名無しさん
2007/08/28(火) 20:54:06>>460
アルゴリズム的に意図的に用意したエントロピープールでも使わない限り、
変な偏りがでることはまずないです。
>>461
擬似乱数関数に第一に求められるのは周期でも速度でもフットプリントのサイズでもなく
その出力される乱数列上に相関性が表れないことだと考えて作りましたですよ。極端な話、
相関性がどれだけ現れようが容認できるのであれば乱数なんて使わずにカウンタでも
使ってればいいわけですから。
MTが周期の為にメモリを消費してるのに対してこの乱数アルゴリズムは品質の為に
メモリを消費してるんで、メモリ消費に対する周期効率は悪くて当然で、気にしとらんです。
0467デフォルトの名無しさん
2007/08/28(火) 21:01:260468デフォルトの名無しさん
2007/08/28(火) 21:03:55そこまではいらないです。この乱数アルゴリズムで生成された乱数列も、
一応、建前上は相関性のない乱数列なんで、例えば 2^32 なインスタンス
を二つ組み合わせて(4294967279x4294967291) 2^63 な周期を実現で
きるですよ。その分、乱数の生成速度にも影響はでちゃいますけど。
この手のものはいろんな批判に耐えることができてなんぼって面もあるんで
いろんな批判もウェルカムですけど、この乱数アルゴリズムは本当に優れた
ばらつきの乱数列を出力できるんで、是非とも皆様、他とは異なるこの上品質
の乱数列を一度ご賞味くだされ。
0469デフォルトの名無しさん
2007/08/28(火) 21:04:59これとMT組み合わせれば最強
0470デフォルトの名無しさん
2007/08/28(火) 21:07:42論文はちょっと・・・
でも、仕事で付き合いのある情報セキュリティ関係の数学者に
今度会う機会があったら見てもらおうかなとは思ってます。
0471デフォルトの名無しさん
2007/08/28(火) 21:11:48水と油というかうまく組み合わせるのは難しいんで、
なんかいいアイデアがあったら教えてください。
0472デフォルトの名無しさん
2007/08/28(火) 22:33:520473デフォルトの名無しさん
2007/08/29(水) 00:24:41本題と関係ないけど、コードの突っ込み。
環境(私が確認したのは2000と2003)によるけどCryptGenRandomしか使用しない場合は、
CryptAcquireContextのdwFlagsにCRYPT_VERIFYCONTEXTも指定したほうがいいよ。
0474デフォルトの名無しさん
2007/08/29(水) 07:58:40そもそも MT で奇数と偶数が交互だったり、プロットで特定の形に集中したり、
過去の結果から予測できることなんてあるの?
それがないなら MT でいいじゃんってことになると思うんだけど。
0475デフォルトの名無しさん
2007/08/29(水) 08:03:11いや、これって質の良いエントロピー源が存在することを前提として、
それを少し引き延ばしているだけなんだよ。
でも、質のよいエントロピーを得るのは結構難しくて、
多くのビットを捨てることによってなんとか質を上げているのが現状。
濃縮スープがあれば、薄めてスープが作れますという感じ。
0476デフォルトの名無しさん
2007/08/29(水) 08:19:05MTの長周期を考えたら出力をプールしてxorすれば良さそうに思える。
0477デフォルトの名無しさん
2007/08/29(水) 09:44:16よう考えてつかぁさい。
ランダム情報源じゃぁ、それまでに出現した数とこれから出現する数との
間にゃぁ関係がないっちゅうなぁほんまじゃ。例えてゆぅたら、サイコロ
を二回振った時に、1回目に出る目と2回目に出る目の間にゃぁ関係がなぁ
のぉ。
ほぃじゃが、それと、ある特定の取り出した値の間に関係がないことたぁ
別なんよ。サイコロを二回振りゃぁ、例えてゆぅたら(1,1)が出るか
もしれんわけで、普通の人はこの二つん目の間にゃぁ関係があるとみなす
わけじゃ。
まあ、実際にプログラムを書いて実験してごらんさい。
ほいで結果をMTと比較してどこが違うんかを表なりグラフなりにしてみ
たらどうじゃろうか。
論文を書いてみるんも、参考文献を読まんにゃぁいけんっちゅう点じゃぁ、
よいゆぅて思いますけぇの。
0478デフォルトの名無しさん
2007/08/29(水) 10:10:340479デフォルトの名無しさん
2007/08/29(水) 13:01:58アロケータを自作しちゃうのと同じ感じがする。
0480デフォルトの名無しさん
2007/08/29(水) 14:56:40動作するプラットホーム、CPU等に激しく依存するので何が正しいかは
動作させなければ判断は難しい。
0481デフォルトの名無しさん
2007/08/29(水) 18:16:13おれはできなかった。>>111 は MT の使い方を間違えたんじゃないかな。
#include <stdio.h>
#include <stdlib.h>
#define main dummy
#include "mt19937ar.c"
#undef main
long buf[262144];
int main(void) {
int i; FILE*fp=fopen("test.dat","wb");
for (i=0;i<262144;i++) buf[i]=genrand_int32();
fwrite(buf,4,262144,fp);
fclose(fp);
system("zip test test.dat");
system("lha32 a test.lzh test.dat");
return 0;
}
0482デフォルトの名無しさん
2007/08/29(水) 18:33:420483デフォルトの名無しさん
2007/08/29(水) 20:00:29>動作させなければ判断は難しい。
だが、動作させなくてもわかるほど確実に悪いものも、たくさん存在する。
0484デフォルトの名無しさん
2007/08/29(水) 23:22:10情報�d。ちなみに今の trickrng.h のそのまわりの実装は MS の knowleg base から
パクってきたモノです。Crypt API まわりは下手に弄るとマシンによって動いたり動か
なかったりが出やすいんでよく調査した上で検討させて頂きますです。
>>474
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
「暗号用の乱数として使いたい」のところ。
>>475
正に仰る通りで、おいしいスープができたんで是非ともご賞味ください。
>>477
3行でお願い。
>>479
そうでなければ喜ばしいんですけどね。
0485デフォルトの名無しさん
2007/08/29(水) 23:27:320486デフォルトの名無しさん
2007/08/30(木) 00:25:18古典だがLFSRは?
0487デフォルトの名無しさん
2007/08/30(木) 02:12:36「nビットの真性乱数からmビット(m>n)の真性乱数を演算で生成する」ってのを
しようとしてる? ...わけじゃないよね。それは原理的に無理。
# 昔圧縮で同じようなことを主張した会社があったっけか
「nビットの入力列からmビットの乱数っぽい数値を演算で生成する」のが
疑似乱数アルゴリズムなわけで、入力列に真性乱数を与えるとみなすなら、
入力エントロピーを引き伸ばして使ってるって意味ではみな同じでは。
線形合同法とMTが五十歩百歩なら、何を持ってきても五十歩百歩な気がする。
まあそれはさておき、入力エントロピーを薄め過ぎない方向に振るってのは、
発想としては面白いかもね。
ただ、既存の疑似乱数や暗号論的演算のコンボに実用性の観点で勝ち目があるものを
さくっと作れるのかというと、正直厳しい気がする。
0488デフォルトの名無しさん
2007/08/30(木) 02:19:24統計的な検査はよく分からんので置いておくとして、遅すぎ。
インデックス決めるためだけに呼び出す毎に整数除算8回もしてる。
試しにVC++(ver.7)で1億回呼び出すコード書いたら(releaseビルド)
0.578 (>>18のやつ)
1.000 (VC++のrandたぶん線形合同法)
1.672 (MT19937)
156.016 (>>451)
だった。(単位は秒、CPUはAthlonX2 3800+,WinXP SP2)
0489デフォルトの名無しさん
2007/08/30(木) 03:15:220490488
2007/08/30(木) 03:51:05やりなおし
0.516 (>>18のやつ)
1.078 (VC++のrandたぶん線形合同法)
1.766 (MT19937)
17.015 (>>451)
0491デフォルトの名無しさん
2007/08/30(木) 03:53:42> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
> 「暗号用の乱数として使いたい」のところ。
MT に対する優位性が暗号論的な安全性にしかないってこと?
その用途ならそもそも >>451 の種にできるようなエントロピーを
直接ぶっこむべきなんじゃないの?
何か >>451 を使うのが最適(MTでもOSの乱数でもダメ)っていう
現実的な例が欲しいかな。
0492デフォルトの名無しさん
2007/08/30(木) 04:09:13同感。得意な領域でもいいから、優位性があるところをデータで示してほしい
0493デフォルトの名無しさん
2007/08/30(木) 04:10:39>>451
assert(0 != master_list[master_list_size -1]);
これ意味あるか?
1/2^32の確率で正しいテーブルがエラーになっちまうよ。
0494デフォルトの名無しさん
2007/08/30(木) 04:17:370495デフォルトの名無しさん
2007/08/30(木) 07:43:19ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/CRYPTMT/index-jp.html
0496デフォルトの名無しさん
2007/08/30(木) 09:08:14> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
> 「暗号用の乱数として使いたい」のところ。
予測できるのが嫌なら、そこに書いてあるとおりハッシュを噛ませれば良いんじゃないの?
そういう意味ではなくて?
0497デフォルトの名無しさん
2007/08/30(木) 15:00:320498デフォルトの名無しさん
2007/08/30(木) 22:35:04>>487
>「nビットの真性乱数からmビット(m>n)の真性乱数を演算で生成する」ってのを
>しようとしてる? ...わけじゃないよね。それは原理的に無理。
先述の数学者の先生にそのへんのことはいろいろ教えて頂いているおかげで知ってるですよ。
あと、真性乱数だと今度は逆に偏りが出やすくばらつきが悪いって欠点もありますし、
あくまで目指したのは良質な擬似乱数でするよ。
>入力エントロピーを引き伸ばして使ってるって意味ではみな同じでは。
このへん、私の考えが変なのかも知れませんが、MT は本質的にはカウンタであると
同時に本質的には 1 bit もエントロピーを持ち合わせていないとすら思ってます。
( 別にそれ自体は悪いことだとは思いませんけど。 )
実際 MT は多倍精度高速カウンタとして非常に強力ですよ、あのアルゴリズムは。
# 実際に多倍精度高速カウンタとして使うにはデコーダを用意する必要がありますけど。
# →で、そのデコーダがあれば 623 個の出力から MT のその後出力が全部わかるです。
>ただ、既存の疑似乱数や暗号論的演算のコンボに実用性の観点で勝ち目があるものを
>さくっと作れるのかというと、正直厳しい気がする。
出力される乱数列の優位性をできれば数値で測定・証明したいとは思ってます。
仰る通り、厳しいでしょうけど。
0499デフォルトの名無しさん
2007/08/30(木) 22:37:32重鈍なのはよく承知してます。恐らく一番ネックになってんのは剰余算やXORを
何度もやってることじゃなくてテーブル参照だと思います。最適化が綺麗に働けば
>>18 のヤツなんて全部レジスタに収まっちゃうんで、メモリ参照が必要な prime
spiral では絶対に敵いません。
prime spiral にあるのは「上質な乱数列」、ただそれだけです。
>>491
ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。
>>493
例えば自前で csv を用意した際にデータが足りてないと致命的なんですが、
乱数であるが故にそれが非常に分かりにくいという問題があるんで過剰な
assert であることを承知の上でミスを検出できることを優先しました。
>>495
それはそれ、これはこれ。それは MT の仲間ではあるかも知れませんが、MT
そのものではなく、必然的に特性も MT とはいろいろ違うでしょうし、わけて
考える必要があると思います。実情はどうか知りませんが、情報セキュリティ
向けの対策を施されているということは一般的に考えて素の MT よりは処理が
重く、また乱数列としてのばらつきは悪くなっていることなどが予想されます。
0500デフォルトの名無しさん
2007/08/30(木) 22:39:32予想できること自体は私は問題視していないのですが、それは乱数列上に
問題を起こしかねない相関性を含んでいる証左なので。
>>497
それ自体はあまり気にしていないのですが、私は乱数列上に現れる相関性を
擬似乱数のバグのようなものだと捉えていて、その延長線で、多くの擬似乱数
アルゴリズムはそのバグを根本的に解決しようとするのではなく、バグの
再現率を下げて分かりにくくし誤魔化せればそれでよしとしているように
解釈してしまい、どうにも私にはそれが受け入れ難いのです。
0501デフォルトの名無しさん
2007/08/30(木) 22:42:07>>499
>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。
これは、prime spiral じゃなくて MT の話です。
0502デフォルトの名無しさん
2007/08/30(木) 22:48:12MTは高次元(623次元)に均等分布することが証明されている。
このことは出力中の連続する値間の相関性が無視できる程度しかないということを意味する。
MTで問題があるというのは結構ですが、
貴方が作ろうとしているものは、それ以上の高次元に均等分布し、
数学的にちゃんと証明できるんですか。
0503デフォルトの名無しさん
2007/08/30(木) 22:53:13とりあえず
>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。
なんて問題はないです。
0504デフォルトの名無しさん
2007/08/30(木) 22:57:41均等分布の意味を私が取り違えてなければ prime spiral は 2^32 次元を超えてます。
0505デフォルトの名無しさん
2007/08/30(木) 22:59:46んで、周期はどうなるの?そっちのほうが問題だと思うが。
0506デフォルトの名無しさん
2007/08/30(木) 23:00:31根拠は?
0507デフォルトの名無しさん
2007/08/30(木) 23:08:26>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。
ないだろ。出鱈目書くなよ。
0508デフォルトの名無しさん
2007/08/30(木) 23:32:48あ、ごめん、やっぱり多分勘違いしてた。
MTで言ってる均等分布 623 次元空間を隙間なく且つ重ならずに埋め尽くすって意味ね。
だとしたら、prime spiral は 2^4800 パターンで 2^32 を超える次元に広がるんで隙間が現れます。
>>505
バグを直さずに周期もなにも・・・てな考えなんでごめんなさい。
>>507
ソースでも読んで。・・・と思ったけど、このへんはすでに改善されてる?
0509デフォルトの名無しさん
2007/08/30(木) 23:44:13数年ぶりに mt のソース見て、思いっきり記憶違いしてることに気づいた。
俺の mt に対するコメントはいったん忘れてくれ。
検証し直したあとでまた mt に対する見解を述べます。大変、申し訳ない。
0510デフォルトの名無しさん
2007/08/31(金) 00:39:560511デフォルトの名無しさん
2007/08/31(金) 07:41:59そして、32次元均等分布もウソだろう。
0512デフォルトの名無しさん
2007/08/31(金) 08:38:550513デフォルトの名無しさん
2007/08/31(金) 11:39:19http://tricklib.com/cxx/dagger/trickrng.h
見たが、周期はどんなに良くても10^10ぐらいしかない。
初期ベクトル(エントロピープールという恥ずかしい名前が付いているようだが)の状態によっては、
悲惨な結果が待ってるな。
正直ゴミだと思う。MT叩く前に数学の世界を舐めるのを止めたほうがいい。
0514デフォルトの名無しさん
2007/08/31(金) 13:16:37追加。
ちなみにこれを、10000以下のすべての素数を使って実装しても、MTの周期に及ばない。
0515デフォルトの名無しさん
2007/08/31(金) 17:36:34http://lucille.atso-net.jp/blog/?p=9
0516デフォルトの名無しさん
2007/08/31(金) 17:53:17M系列乱数の方が明らかに速いし、無理にMTを使うメリットが見えてこないんだけど。
0517デフォルトの名無しさん
2007/08/31(金) 18:15:20生成速度だけが擬似乱数に求められる性能ではないし、要は適材適所だよ。
0518デフォルトの名無しさん
2007/08/31(金) 18:22:16というか、MTで速度が不満ってどういうこと?
全体の負荷の何パーセントをMTに持ってかれるの?
そういうところを無視して、速度を語っても意味がないぞ。数パーセントならマシン買いかえればいいんだし。
0519デフォルトの名無しさん
2007/08/31(金) 18:24:28えー
0520デフォルトの名無しさん
2007/08/31(金) 18:29:200521デフォルトの名無しさん
2007/08/31(金) 19:53:12>>18で超既出
0522デフォルトの名無しさん
2007/08/31(金) 19:53:49そこらへんはSIMDでなんとかならんかなあ
0523デフォルトの名無しさん
2007/08/31(金) 20:15:28俺が乱数ルーチンを作ったんだ!と主張したいんだろうけど、
たかが乱数ごときで、毎回書かなきゃならんのもなんだかな。
0524デフォルトの名無しさん
2007/08/31(金) 20:26:52修正BSDライセンスかなんかだったような
0525デフォルトの名無しさん
2007/08/31(金) 20:27:23アルゴリズムに著作権はないよ。サンプル実装のソースコードを、
そのまま使ってるなら、ソースコードには著作権が発生するけど。
0526デフォルトの名無しさん
2007/08/31(金) 21:03:29敵を知り、己を知れば…
そう、つまり最初にすべきは敵をちゃんと知っておくことなんだよね。
0527デフォルトの名無しさん
2007/08/31(金) 21:10:24> だとしたら、prime spiral は 2^4800 パターンで 2^32 を超える次元に広がるんで隙間が現れます。
周期 2^32 以下なのに、どうやって 2^32 次元に均等分布するのか謎だが…
0528デフォルトの名無しさん
2007/08/31(金) 21:43:43やあ、あんた少しはわかってる人だね。
>>516
M系列の方が明らかに周期が短いだろ
>>515
XORSHIFTはMTの周期や均等分布次元が必要でない時には、
実際に有力な選択肢だ。SFMTの速度比較でも速いと出てるしな。
0529デフォルトの名無しさん
2007/08/31(金) 23:32:302^20 回試行して集計かけたところ、こんな感じ。
1度しか現れない数値 30.9%
出現回数が多い数値
0 (2656回)
8 (2637回)
32759 (2452回)
…
ちなみに MT だと、こうなる。
1度しか現れない数値 99.9%
出現回数が多い数値
113個の数字が2回出現
他はすべて1回出現
周期とかは見てないが、この時点で、すでにまともに解析する気なしってことで。
0530デフォルトの名無しさん
2007/09/01(土) 00:17:17というか、それ以前に敵ではないものを敵と勘違いしていると思われ。
0531デフォルトの名無しさん
2007/09/01(土) 00:26:30そして、想像上の何者かと想像上の「己」が、
何かを戦っているつもりになっている。
これを妄想という。
0532デフォルトの名無しさん
2007/09/01(土) 00:32:590533デフォルトの名無しさん
2007/09/01(土) 02:58:550534デフォルトの名無しさん
2007/09/01(土) 11:35:52周期が短い場合はそのとおり、周期がとてつもなく長い場合は
偏りも乱数であり正しい性能である。
後者であれば、長い周期を測定できない評価ソフトの性能が悪いことになる。
0535デフォルトの名無しさん
2007/09/01(土) 11:40:530536デフォルトの名無しさん
2007/09/01(土) 12:12:39周期以前にprime spiralは乱数になっていないのが問題。線形合同法にも劣る。ゴミだ。
2^20の試行で、0が2^11も出ている時点で正常な分布ではなく、2^32までチェックすることもなく明らかだ。
0537デフォルトの名無しさん
2007/09/01(土) 12:23:13> 周期が短い場合
prime spiral は内部状態が 32bit 符号なし整数1つだけなので、周期は最大 2^32 だよ。
初期ベクトルとしてもう少しマトモなものを選べば改善されるかもしれんが、いずれにしろ
やる気ないです。はい。
0538デフォルトの名無しさん
2007/09/01(土) 13:09:20どこか間違ってない?
別に擁護するわけじゃないけど、
俺も実験してみた結果、
100万回(2^20)出力して同じ値が出たのは
133 (>>18 xorshift)
146 (mt19937)
105 (>>451 prime spiral)
だったよ。
出力は全部unsigned int(32bit)。
ちなみに俺は>>488,490の人。
個人的には今のところ、周期が短すぎ、遅すぎというのを除けば
テーブルの初期化が適切であると言う前提ならそこそこの品質には思える。
でもテーブルに完全に依存しているから、
mtのような多次元均等分布は不可能なんじゃないかな?
テーブルを大きくすればするほど遅くなっていくし。(指数関数的に)
唯一のいいところはテーブルの状態が分かっていてもカウンタが
分からない限り過去の出力からは次が読めないところかな?
0539デフォルトの名無しさん
2007/09/01(土) 13:15:39初期化の問題は(MTもそうだけど)
どこかからエントロピー持ってくるAPI(CryptGenRondom)やら
物理乱数生成チップやらでどうにかならないか?
0540デフォルトの名無しさん
2007/09/01(土) 13:17:33ソース出せ。こっちでも実験&分析してやるから。
prime spiralが如何にゴミであるか証明してやるよ。
0541デフォルトの名無しさん
2007/09/01(土) 13:21:25>唯一のいいところはテーブルの状態が分かっていてもカウンタが
>分からない限り過去の出力からは次が読めないところかな?
お前本人じゃねーの?
あれが「過去の出力からは次が読めない」って本気で思っているのか?
簡単にわかるぞ。あんなもの暗号に使ったら大変なことになる。
そんなボケかますのは本人以外ないと思うが、馬鹿がもう一人いるのかもしれんな。
予測不可能にするなら、MTにハッシュ(SHA)付ければ十分だ。
0542デフォルトの名無しさん
2007/09/01(土) 13:28:210543529
2007/09/01(土) 13:29:55#include <iostream>
#include "trickrng.h"
int
main()
{
tricklib::prime_spiral_entropy_pool g1;
unsigned const LOOP_MAX = 1 << 20;
for (unsigned i = 0; i < LOOP_MAX; ++i)
std::cout << g1.shuffle(i) << "\n";
}
できたテキストファイルを DB に取り込んで、グループ化かけて集計した。
0544デフォルトの名無しさん
2007/09/01(土) 13:32:33> なるほど、次を予測しにくい乱数アルゴリズムなわけか。
んなわけない。
内部状態が 32bit しかないので、周期は必然的に 2^32 以下。brute force でも
2^32 回の出力を見て記録していおいたら確実に次は予測可能なので、賢い
解析アルゴリズムを考えるまでもない。
0545538
2007/09/01(土) 13:47:30#define uint unsigned int
uint *buf = (uint *)malloc( X * sizeof(uint) );
if ( buf == NULL ) return;
tricklib::prime_spiral_dice dice( 100 );
for (uint i=X; i--; ) buf[ i ] = dice.roll();
sort( buf, X );//なんでもいい。シェルソート使った。
uint cnt[ 32 ], same = 0, p = buf[ X - 1 ];
for (uint i=X-1; i--; ) {
uint t = buf[ i ];
if ( t == p ) {
same++;
} else {
if ( same > 31 ) same = 31;//オーバーフロー対策
cnt[ same ]++;
same = 0;
}
p = t;
}
メモリに全部書き出してソートして前と同じならカウンタをインクリメント。
>>529
それ多分使い方違う。
テーブルが初期化されてない。
まあ、テーブル次第で悲惨な結果になるという見本ではある。
分かると思うけど作者じゃないよ。
アルゴリズム的に穴が多いから自分は使う気はないし。
0546538
2007/09/01(土) 13:51:19cnt[ 32 ]はstaticつけて0で初期化してね。
0547デフォルトの名無しさん
2007/09/01(土) 14:02:26最大の残したりできないから、上書きされるんじゃないか。
0548538
2007/09/01(土) 14:10:32上書き?はされないと思うけど。
最多31でカンストするようにはしたけど。
よく読んでおくれ。
同じのが3回以上出ることはなかったよ。
0549デフォルトの名無しさん
2007/09/01(土) 14:19:22いいから、出力結果をテキストファイルに出して、目で読んでみろ。
0550538
2007/09/01(土) 14:27:59あんたはなんで俺にからんでんの?
>>529,543のコードはどういうわけか
構造体のインスタンスを生成して実験してるから
テーブルが初期化されてなくてゴミが詰まった状態なんだっての。
テーブル次第で2^20の試行で、0が2^11も出たりすることもあるけど、
デフォルトのテーブルではそんなことはなかったって話だよ。
落ち着きなよ。
0551デフォルトの名無しさん
2007/09/01(土) 14:31:39だったら、この発言を取り下げろ。
↓
唯一のいいところはテーブルの状態が分かっていてもカウンタが
分からない限り過去の出力からは次が読めないところかな?
0552デフォルトの名無しさん
2007/09/01(土) 14:33:29いいところゼロのゴミであることに同意するんだな?
0555デフォルトの名無しさん
2007/09/01(土) 14:41:47テーブルダンプしてみたら、確かに初期化されてなさげ。
00000000 00000000 00509146 00000008 00000000 00000000 005271a0 00000008
ffffe630 00007fff 00000000 00000000 00000001 00000000 078e530f 00000000
004004d1 00000000 00509270 00000008 00000001 00000000 00528600 00000008
ffffe628 00007fff 00000000 00000000 ffffe670 00007fff 00000000 00000000
00000001 00000000 078e530f 00000000 004004d1 00000000 00509369 00000008
00528000 00000008 00528200 00000008 00528400 00000008 00528600 00000008
00528000 00000008 00528200 00000008 00528400 00000008 00528600 00000008
00528800 00000008 00528600 00000008 00503a88 01000008 ffffe690 00007fff
00528000 00000008 00528600 00000008 ffffe5c0 00007fff 00000005 00000004
00528000 00000008 00000000 00000000 00000013 00000000 00000001 00000000
004003e0 00000000 004004d1 00000000 00528000 00000008 0050964a 00000008
00400368 00000000 ffffe6d8 00007fff 00528600 00000008 00528000 00000008
00500e40 00000000 00000001 00000000 00000000 00000000 0050bae9 00000008
00950880 00000008 005097bb 00000008 00000000 00000000 00528600 00000008
00000001 00000000 ffffe7d8 00007fff ffffe7c8 00007fff 0050747d 00000008
00000246 00000000 ffffffff 00000000 ffffe4e8 00007fff 00000000 00000000
00500b08 00000000 00500ea0 00000000 00c61910 00000008 00000001 00000000
00400764 00000000 00000206 00000000 00000000 00000000 00528000 00000008
00000001 00000000 0040088d 00000000 00000001 00000000
0556538
2007/09/01(土) 14:44:19あ、やっぱそうでしょ?
でもテーブルがこんなことになってしまう可能性もあるわけで
アルゴリズム的には問題ありなのは事実ですな。
統計的にも不安だし。
0557529 (=555)
2007/09/01(土) 14:44:34そういや作者の人は MT のコード読み終わったの?
0558デフォルトの名無しさん
2007/09/01(土) 14:45:15でも唯一のいいところもないってことだね。
0559デフォルトの名無しさん
2007/09/01(土) 14:47:52唯一のいいところ=自己満足
で良いじゃないの? 俺言語とか俺DBとか俺ステートマシンとか、いろいろ HDD に
眠ってるぜ orz
0560デフォルトの名無しさん
2007/09/01(土) 14:50:36それは構わないけど、それは作った本人にとってであって、
第三者として利用するのに、自己満足も糞もないんだが。
0561デフォルトの名無しさん
2007/09/01(土) 14:53:12まぁねぇ。俺も使う気ないし。
ML で延々やられるよりは、2ch で自己満足に浸ってくれてた方が害が少ないので、
ここに閉じ込めておくのが吉かと。
0562デフォルトの名無しさん
2007/09/01(土) 15:08:30最初のバージョンは結構素直だが、
今のは微妙に最適化されてたり
そのくせ古いバージョンの名残の変数名が使われてたりしてちょっと読みにくい。
0563デフォルトの名無しさん
2007/09/01(土) 15:10:16下手すると第三者の最適化版とかのほうが読みやすくなってたりする。
(ダンゴが同じようなことを上の方で言ってた気がする)
0564デフォルトの名無しさん
2007/09/01(土) 15:35:57prime_spiral_entropy_pool ではなく prime_spiral_dice を使うのが正しいんじゃ?
って550にもう書いてあるか。
つか、環境依存マクロで内部実装が何ヶ所か切り替わってしまうんで
同条件での比較ができてないんじゃないかという気もする。
そのせいで偏ったとか偏ってないとか話がすれ違ってるんでは。
次のコードでやってみた。環境はx86-linux、コンパイラはgcc-4.2.1。
#include <iomanip>
#include <iostream>
#include <ostream>
#include "trickrng.h"
int main(void)
{
using namespace std;
tricklib::prime_spiral_dice prng;
const unsigned int n = 1 << 20;
for (unsigned int i = 0; i < n; ++i) cout << prng.roll() << endl;
}
$ ./a.out | sort | uniq -c | awk '{print $1}' | sort | uniq -c
1048342 1
117 2
てことで、漏れの手元ではダメな偏りは観測されず。
0565564
2007/09/01(土) 16:13:00最終結果の数値は、
「1回出現した値が1048342個、2回出現した値が117個。他はなし」って意味。
もちっとましな検定とその結果を見てみたいが、
漏れは乱数素人なんで方法がわからず。
まあでも、prime_spiral_diceクラスのインスタンスの「更新される内部状態」は
uint32_t型のメンバ変数"index"だけなんで、
疑似乱数の周期は>>544の指摘通り2^32以下。
あまりがんばる気にならんかも。
ソースには dynamic_prime_spiral_dice ってのもあるけど、誰か追った?
0567538
2007/09/01(土) 16:27:04定期的に別の乱数でテーブルを書き換えた方がいいと思うんだ。
全部とは言わないけど一部だけでもね。
自身の出力を使って書き換えると意味がないから
別の系列の乱数でってことになるんだけど、
そこまでやるならやっぱMTとかをハッシュにかけたらいいじゃんて話なんだな。
0568564
2007/09/01(土) 18:22:56thx。インスタンスごとに別々のテーブルを持ってるだけで、
初期化後はテーブルを書き換えないって点では prime_spiral_dice と同じか。
疑似乱数アルゴリズムの評価って意味では見なくていいね。
>>567
単に乱数を得るって意味では、時々 secure_dice_type を振って混ぜればいいかと。
疑似乱数とは呼べなくなるんだろうけど、うまくすれば使えるようになるか?
もっとも、テーブル更新をしない間の出力の性質がよくないとダメだけど。
自身の出力または内部状態を使って書き換える方法で性質がよくなるなら、
そっちの方がいいんだが。
0569デフォルトの名無しさん
2007/09/01(土) 18:31:00> 単に乱数を得るって意味では、時々 secure_dice_type を振って混ぜればいいかと。
secure_dice_type の出力によってはテーブルが悲惨な状態になりかねんぞ。
統計的に不安定なアルゴリズムはいやん。
0570538
2007/09/01(土) 19:20:21互いに疎な周期を持った二つの異なる系列の乱数をXORしたら
理論的な出力はどうなるんだろう?
周期が2^32と2^31とかなら間違いなく2^63になるはずだけど(互いに疎だから)、
予言可能性とかはどうなるのか?
0571デフォルトの名無しさん
2007/09/01(土) 19:28:29> 周期が2^32と2^31
それ、互いに疎じゃない。GCD=2^31。
0572538
2007/09/01(土) 19:32:082^19937-1はメルセンヌ数でしょ?
普通は2^19937の周期でって書くじゃん。
実際には1少なくても。
0573デフォルトの名無しさん
2007/09/01(土) 19:43:58>>446
PDFだけど↓みたいなものも見つけた
ttp://www.fdk.co.jp/cyber-j/pdf/HM-RAJ103.pdf
0574・∀・)っ-<コ:彡-
2007/09/01(土) 19:44:45可読性に関しては言及してないよ。C++&マルチスレッドで使うには不便すぎますよねー、て感じ。
定数定義周りはマクロじゃなくてテンプレートでなんとかなりそうだが。boostみたいに。
0575デフォルトの名無しさん
2007/09/01(土) 19:48:04既知の周期 m, n の二つの系列の乱数があった場合、m + n だけ XOR された
乱数を見れば、元の乱数列が計算可能だと思う。
周期 m の乱数 x(0), x(1), ..., x(m - 1)
周期 n の乱数 y(0), y(1), ..., y(n - 1)
XORされた乱数 z(0), z(1), ..., z(mn - 1)
これで最初の m+n 個の乱数が取得できれば
x(i mod m) ^ y(i mod n) = zi
という方程式が m + n 個作れる。右辺は全部既知なので、未知数 m + n 個に対して
方程式 m + n 個あるので、あとは計算すりゃ出るでしょ。
周期が未知の場合には、もう一捻りいるかも。
0576538
2007/09/01(土) 20:43:52なるほどなるほど。
確かにそうだ。m+nまで分かれば残りが完全に予言できるね。
でもこれってx,yを特定するのは無理だよね。
一つだけでも分かれば後は芋づる式だけど。
0577デフォルトの名無しさん
2007/09/01(土) 20:58:42周期3と周期5だったら
12312312312312312312..
12345123451234512345...
-----------------------------
246564356635468246...
XORじゃなくて足してるだけだけど普通に3*5=15の周期になるよね。
2^32の線形合同法を4つ組み合わせたら、普通に2^128周期になるんじゃないかな?
乱数性はともかく。
0578・∀・)っ-<コ:彡-
2007/09/01(土) 21:28:570579538
2007/09/01(土) 21:42:52全ての系列の周期が分かってれば大きい方から2つの周期を加算した
ところまでみれば残りが全部予言できそう。
違うかな?
>>578
出力の周期のことだよ。
0580・∀・)っ-<コ:彡-
2007/09/01(土) 21:46:180581・∀・)っ-<コ:彡-
2007/09/01(土) 21:47:31その付近の周期の乱数も。
0582デフォルトの名無しさん
2007/09/01(土) 21:51:59> でもこれってx,yを特定するのは無理だよね。
特定する意味はないな。
x, y すべてに対してある数 n を xor しても、出力がまったく変わらんから、
出力を満たす x, y の組み合わせは無数にある。
0583538
2007/09/01(土) 21:54:56ごめん両方素数の意味ね。
数学の知識が高1くらいで止まってるから訳分からん事言ってるな。
すまん。
0585・∀・)っ-<コ:彡-
2007/09/01(土) 21:57:26最大公約数=1
最小公倍数=積
0586・∀・)っ-<コ:彡-
2007/09/01(土) 21:57:550587538
2007/09/01(土) 22:57:52ちょっと違うかな。
周期3,5,7の乱数があったら3と5を組み合わせて
周期15と7の乱数があることになるから
この場合は15+7=22まで見ればいいんだな。
3,5,7,11なら(3*11)+(5*7)=68かな?
もっと短く出来るのかな?
0588デフォルトの名無しさん
2007/09/01(土) 23:11:563+5+7 = 15 で良いと思うが。
0589538
2007/09/01(土) 23:59:55周期3,5,7の場合はそのまま3+5+7=15
16番目の数字は2 3 4 7 8 10 11 14 15番目を全部XORすると出てくる。
以下ソース
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define uint unsigned int
int main( int argc, char *argv[] )
{
srand( (uint)time(NULL) );
uint a[ 3 ], b[ 5 ], c[ 7 ], x[ 3 * 5 * 7 ];
for (uint i=0; i<3; i++) a[ i ] = (uint)rand();
for (uint i=0; i<5; i++) b[ i ] = (uint)rand();
for (uint i=0; i<7; i++) c[ i ] = (uint)rand();
for (uint i=0; i<3*5*7; i++) {
x[ i ] = a[ i % 3 ] ^ b[ i % 5 ] ^ c[ i % 7 ];
}
uint x15 = x[ 1 ] ^ x[ 2 ] ^ x[ 3 ] ^ x[ 6 ] ^ x[ 7 ] ^ x[ 9 ] ^
x[ 10 ] ^ x[ 13 ] ^ x[ 14 ];
printf("%d\n%d\n", x[ 15 ], x15);
return 0;
}
0591538
2007/09/02(日) 00:40:4715個まで分かれば次の数字が分かるということで
逆に直前の15個が分かっていれば残りも全部同じ式でいける。
というか一般項に出来る。
なんか面白かったんでもう一度ソース。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define uint unsigned int
int main( int argc, char *argv[] )
{
srand( (uint)time(NULL) );
uint a[ 3 ], b[ 5 ], c[ 7 ], x[ 3 * 5 * 7 ];
for (uint i=0; i<3; i++) a[ i ] = (uint)rand();
for (uint i=0; i<5; i++) b[ i ] = (uint)rand();
for (uint i=0; i<7; i++) c[ i ] = (uint)rand();
for (uint i=0; i<3*5*7; i++) {
x[ i ] = a[ i % 3 ] ^ b[ i % 5 ] ^ c[ i % 7 ];
}
for (uint i=15; i<3*5*7; i++) {
uint z = x[ i - 1 ] ^ x[ i - 2 ] ^ x[ i - 5 ] ^
x[ i - 6 ] ^ x[ i - 8 ] ^ x[ i - 9 ] ^
x[ i - 12 ] ^ x[ i - 13 ] ^ x[ i - 14 ];
printf("%3d: %10d %10d\n", i, x[ i ], z);
}
return 0;
}
0592538
2007/09/02(日) 08:50:11一般項の一番最後はi-14なんで実は15個でなくて14個目の時点で分かるようだ。
周期を足して分かるのは最悪でもここまで見ればという上限に過ぎないらしい。
どうやら単純なものではないみたいだ。
さらに系列が二つの場合、数列Xは周期をa,b(ともに素数)として
Xa+b = X0 ^ Xa ^ Xbと出来る(たぶん)
系列が三つ以上ある場合はそれほど簡単でもないらしい。
さらにこの漸化式表現だと合成後の周期までは分からないようだ。
3 * 5と2 * 3 * 5は同じ漸化式に出来るけど周期は違う。
ともにXi = Xi-3 ^ Xi-5 ^ Xi-8と書ける。
もう少し調査を続けるかも。
0593デフォルトの名無しさん
2007/09/02(日) 13:50:40いろいろ考えてるとMTの理屈そのものになんか辻褄の合わないところが見えてきたです。
多分、論文をちゃんと見ればその矛盾に対する但し書きがあるんじゃないかと思うです。
# 例えば MT の周期じゃ 623次元で均等分布するのは不可能。厳密な意味で 623次元
# で均等分布する為には周期が n^623 の倍数である必要があるけど MT の周期は
# そうではない。
0594デフォルトの名無しさん
2007/09/02(日) 13:51:36"素数の積算値(6685349671)"次元のデータに変換するアルゴリズムと言え、
また prime spiral で 2^32 周期を実現する為には 2^32を超える 次元の
データ(への変換)が必要となるですよ。余った分は単に捨ててます。
で、150次元から6685349671次元への座標変換を行うんでその結果は当然スカスカ
で MT で言う均等分布にはなりません(先述の隙間が現れるってはこの意味)。
0595デフォルトの名無しさん
2007/09/02(日) 13:53:11・あり得ないような確率の元データが発生したのを受け忠実に
そのあり得ない様を出力しているだけ。
・そもそも悲惨と感じるのは人間の主観の問題であって数学的
には特別な意味を持たない。
...という見解ではあるんですが、そもそもの prime spiral の作成目的から
すると放置するべき問題じゃないと考えますので対策しておきます。
# 次回更新時に 2^63 周期版も追加しておきます。2^32 周期版よりもさらに
# 倍ちょっと重いようなしろものですが。
0596デフォルトの名無しさん
2007/09/02(日) 13:54:46タブーでここを崩すと prime spiral の存在理由も崩れちゃいます。
あと、"得意分野があれば"って話がありましたけど、よくよく考えてみたら
乱数列に対して簡単にランダムアクセスができるって利点があるですね。
0597デフォルトの名無しさん
2007/09/02(日) 14:21:49http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E3%83%BB%E3%83%84%E3%82%A4%E3%82%B9%E3%82%BF
>メルセンヌ・ツイスタでは、状態空間が長方形から1ビットだけ突き出した(あるいは31ビット欠けた)形をしている点に特徴がある
これのことかな。他にもまだ数字の辻褄があってないとこがあるんで論文読みます。
0598デフォルトの名無しさん
2007/09/02(日) 14:35:53N次元ベクトルについて行って特に偏りが無いってことだよね?
全部の組み合わせを埋め尽くすって意味じゃないでしょ。そういう意味なら
均等に分布なんて言葉使わないはずだし。
0599デフォルトの名無しさん
2007/09/02(日) 16:16:43最小公倍数
0600・∀・)っ-<コ:彡-
2007/09/02(日) 19:56:270601デフォルトの名無しさん
2007/09/02(日) 21:29:08まず、調査対象の乱数をファイルに落とす。フォーマットはこんな感じ。
type: u
count: 10 ←要素数
numbit: 32
1663584611 ←1乱数につき1行。符号なし10進数。要素数分だけ列挙
1565230341
674637926
...
で、dieharderに食わせる。
dieharder -a -g 65 -f ファイル名
`-a'は「一通りテストしろ」、`-g 65'は「ファイルから読め」の意。
65って数字はdieharderのバージョンによって違ったりするっぽいので、
`dieharder -g -1'で "file_input" がどの番号かを確認。
必要な要素数はテストによって異なるけど、1,000,000個ぐらいでいいらしい。
0602601
2007/09/02(日) 21:39:10検定内容は ttp://www.phy.duke.edu/~rgb/General/dieharder.php の後半の
"DieHarder Test Suite" あたりに列挙されている。ただし名前だけ。
で、識者に質問。この検定って質はどうなの?
各々、名の通った乱数検定を実装したものなのか、単にオレオレ検定なのかとか。
入力が少なくていいんで、周期は検定対象外ってことぐらいはわかるけど。
0603デフォルトの名無しさん
2007/09/02(日) 22:32:15辻褄が合わないのは貴方の頭の中のでしょう。
変な書き込みを匿名でするくらいなら、数学を学びなおした方がいいですよ。
prime spiralでは、MTの足元にも及びません。
0604・∀・)っ-<コ:彡-
2007/09/02(日) 22:34:15松本教授の論文いっぺん読んでこないとね
0605デフォルトの名無しさん
2007/09/02(日) 23:43:01自己流の変なものを作ってしまい、あとからMTの問題が勘違いだと発覚。
でも、MTに問題がないと困るから今になって必死に粗探ししているようなものだろ。
人間性から腐っているよコイツは。
MTがいったいどれだけの年月と人によって検証されてきたものか理解していないんだろな。
自分が上に立てるとでも思っているのかこの馬鹿は。
0606デフォルトの名無しさん
2007/09/03(月) 08:10:51数学以前に英語で挫折するであろう。
でも、斎藤さんのページにこんなんあったよ。これで勉強すれば?
ttp://home.hiroshima-u.ac.jp/d073872/random/5bitmt.html
0607デフォルトの名無しさん
2007/09/03(月) 21:45:19誰でも一度は通る道だから、そこまで言わんでも。まぁ、ふつーは中二ぐらいで済ませるが。
0608デフォルトの名無しさん
2007/09/03(月) 21:56:59これを回避する上手い方法ってないもんでしょうかね?
ハッシュとか以外で。
0609デフォルトの名無しさん
2007/09/04(火) 02:14:48よくはわからんが、MTみたいに調律すればいいんかな。
でも適当じゃダメか。
0610デフォルトの名無しさん
2007/09/04(火) 07:57:05単なるオレオレ検定ではない。
ところで、入力が少ないんで周期は検定対象外だろうって書いてるけど
どんだけ入力したら、周期が検定できると思っている?
0611デフォルトの名無しさん
2007/09/04(火) 13:32:24自分がすごいもの作れると有頂天になるだけか、
既存のものに疑問を持って批判するだけか、どちらかならそれほど問題はない。
それなら理解もできる。
だが、自分が上に立ちたいとか、自分の存在意義のために、
間違っていないものを間違っているとしてでっちあげるのは最低だろ。
こいつが警官だったら、自分の評価を上げるために、
自分の勘違いで逮捕してしまっても、罪をでっちあげて犯罪者に仕立て上げかねん。
社員であれば、他人の足を引っ張ったり、失敗をかぶせたり、
浅はかな考えで周囲を振り回したりする、有害な存在であろう。
0612デフォルトの名無しさん
2007/09/04(火) 19:24:430613デフォルトの名無しさん
2007/09/04(火) 21:58:29実社会で迷惑をかける代わりに、ここで落書きして気が済むなら、それで良いじゃん。
日本の治安向上に役立ってるなw >2ch
で、MT は理解できたのかな?
0614デフォルトの名無しさん
2007/09/04(火) 22:18:05>多倍精度高速カウンタ
→多倍精度高速カウンタとしては高速ではない。
># →で、そのデコーダがあれば 623 個の出力から MT のその後出力が全部わかるです。
→内部状態が全部 0 になっている場合を除き 623 個じゃ足りない。もう少し必要。
>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。
→そんなことはない。
以上の点については私の記憶違いを端に発してる勘違いです。
大変、お騒がせしました。
0615デフォルトの名無しさん
2007/09/04(火) 22:18:50求められる条件を理想的な形で体現しているというのはよく理解できましたです。
が、それでもというか、だからこそやっぱり MT は少なくとも私が特別な前提
条件がない状態で求める擬似乱数とは違うですよ。
別のところでも述べましたけど prime spiral 自体はそのロジックが瓦解
しちゃっても全然構わないと考えてます。prime spiral に問題がないことが
より確実な形で検証されればそれに越したことはありませんが、私が大事
だと考えているのは prime spiral のエントロピーを引き延ばすアルゴリズム
なんかじゃなくて、エントロピーを大切にし、問題を引き起こしかねない
相関性を乱数列上から根本的に排除しようという思想です。
0616デフォルトの名無しさん
2007/09/04(火) 22:19:320617デフォルトの名無しさん
2007/09/04(火) 22:19:46>恐らく一番ネックになってんのは剰余算やXORを
>何度もやってることじゃなくてテーブル参照だと思います。
あと、これ、間違ってました。ご指摘通り剰余算が一番ネックになってます。
パフォーマンス改善の為に試しにMODテーブルを用意して剰余算を行わず
に処理したらどうなるか試してみましたけども、パフォーマンス上特に有効な
差異は認められませんでした。
概ね、prime spiral に関するご意見等も一通り出尽くしたみたいですので
ここらで一度、ご意見を下さった方々、速度や出力される乱数列について
検証してくださった方々に改めてお礼申し上げますです。
0618デフォルトの名無しさん
2007/09/04(火) 22:21:26アイディア倒れになると良くないから、
ちゃんと数学の勉強をしてみたほうがいいと思うよ。
0619デフォルトの名無しさん
2007/09/04(火) 23:17:19君は相関性もまともにわかってないから今のままだと無理だよ。
MT以上に相関性無くすのは大変だから。
prime spiralは相関性ありまくりだし。
0620デフォルトの名無しさん
2007/09/04(火) 23:19:22ちょっと読み返してみた。
>>593 のことなら、確かに言葉が悪かった。
暗号なんかを含め、この手の分野の厳密さはよく知ってるから、
評価されてる論文の絶大さも理解はしてるですよ。
>>618
いいものを自分の手で作ることができればいいなぁとは思ってますけど、
この分野を専攻していこうというまでの気概はありませんのでw
# 数学系の厳密さはいい加減な自分には肌が合わんとですよ。
0621デフォルトの名無しさん
2007/09/04(火) 23:27:51今回、勉強させてもらったおかげでよく理解しましたけど、MT は本質的には相関性の塊ですよ。
ただ、MTの場合その周期やパターンの関係上、相関性が(少)ないように見えるってだけで。
prime spiral の相関性も知ってます。というか、ぶっちゃけ意図的に問題が
発生し得ないような方向に相関性をコントロールしてます。
0622デフォルトの名無しさん
2007/09/04(火) 23:28:52真面目に数学もやる気がないなら、
変なライブラリは自己満足にして、公開するのはやめてくれんか?
正直、これ以上君のような馬鹿が増えると迷惑なんだが。
>暗号なんかを含め、この手の分野の厳密さはよく知ってるから、
理解していないから、MTに文句たれて、ゴミのprime spiralを公開してるんだろ。
まあ、やめろって言ってもやるだろうけど、そのうち、もっと恥をかくことになるよ。
0623デフォルトの名無しさん
2007/09/04(火) 23:32:040624デフォルトの名無しさん
2007/09/04(火) 23:32:07>今回、勉強させてもらったおかげでよく理解しましたけど、
まだ理解できていないと思われ。
理解しているなら試しにより周期の長いMTを作ってみてごらん。
>MT は本質的には相関性の塊ですよ。
>ただ、MTの場合その周期やパターンの関係上、相関性が(少)ないように見えるってだけで。
違うよ。疑似乱数だから相関性があるのは当然だが、
prime spiralのような劣悪な相関性はないのは君は理解していないだろ。
>というか、ぶっちゃけ意図的に問題が
>発生し得ないような方向に相関性をコントロールしてます。
できていませんが?どこでコントロールした気になってるの?
0625デフォルトの名無しさん
2007/09/04(火) 23:34:270626デフォルトの名無しさん
2007/09/04(火) 23:36:05どうぞ。失せてくれ。
煽りでも何でもなく、欠陥の指摘をされても理解できないようだから。
0627デフォルトの名無しさん
2007/09/04(火) 23:36:37相関性って何?周期って何?
というのはトモカクだ、
本質的って何のこと?
パターンって何のこと?
問題って何のこと?
方向って何のこと?
を書いてくれないと議論できない。今更だけど。
0628デフォルトの名無しさん
2007/09/04(火) 23:38:13prime spiralが相関性ありまくりで最悪であることを証明して投稿してやるよ。
数学の世界を舐めてもらったら困るので。
0629デフォルトの名無しさん
2007/09/04(火) 23:39:07MTFSは長いのやら短いのやら選択できたっけ。
0630デフォルトの名無しさん
2007/09/04(火) 23:40:25>prime spiralが相関性ありまくりで最悪であることを証明して投稿してやるよ。
ごめん、これはぜひ、お願い。
検証にご協力頂けるのは助かります。
0631デフォルトの名無しさん
2007/09/04(火) 23:42:47できる
0632デフォルトの名無しさん
2007/09/04(火) 23:44:01> 検証にご協力頂けるのは助かります。
ふつーは専門家に検証を頼むなら、論文ぐらい書くもんだぞ…
言葉も明確に定義せず、参照論文や related work も示さずに、あまつさえ
タダで評価してもらおうなんて、虫がよすぎるとは思わんか?
0633デフォルトの名無しさん
2007/09/04(火) 23:44:26>>625のように真面目に答える気がないなら、今はやだね。
君が自信もって発表して、恥をかくタイミングまでまってやるよ。
ちゃんと説明する気があるなら、協力してやらないこともないけど。
0634デフォルトの名無しさん
2007/09/04(火) 23:44:38それは俺も楽しみにしてるわ
0635デフォルトの名無しさん
2007/09/04(火) 23:46:16もう発表してるんだから、早く早く!
0636デフォルトの名無しさん
2007/09/04(火) 23:47:28返す言葉もございません。m(_ _)m
0637デフォルトの名無しさん
2007/09/04(火) 23:48:09うーん、本来は逆だよな。
prime spiralがある切り口で最高であることを作者自身が証明する
のが筋じゃない? それなしで検証とか言われてもなー。悪魔の証明
を思い出した。
折角作ったのに叩いて悪いんだけどさ。
プログラマは数学から距離を置く方がいい仕事ができると
ポールグレアムも言ってるだろ。。。
0638デフォルトの名無しさん
2007/09/04(火) 23:49:16斬新なアイデアでもなんでもないのに。
0639デフォルトの名無しさん
2007/09/04(火) 23:49:39重ね重ね、返す言葉もございません。
0640デフォルトの名無しさん
2007/09/04(火) 23:50:01例外に Knuth っつー巨人がいるから、みんな目を奪われちゃうんだよな。
0641デフォルトの名無しさん
2007/09/04(火) 23:50:280642デフォルトの名無しさん
2007/09/04(火) 23:50:560643デフォルトの名無しさん
2007/09/04(火) 23:51:10ノイマンも
0644デフォルトの名無しさん
2007/09/04(火) 23:52:18アイデアとして別に真新しいものじゃないのはわかってる。
ただ自分の欲しいモノを求めてそれが見つからなかったから自作してみただけ。
同じような思想のモノでいろいろとちゃんと検証済みのヤツがあったらそれを採用したい。
0645デフォルトの名無しさん
2007/09/04(火) 23:53:10俺はノイマン型コンピュータは、エッカートとモックリーの業績だと思ってるので。
0646デフォルトの名無しさん
2007/09/04(火) 23:54:16プログラマではないな
0647デフォルトの名無しさん
2007/09/04(火) 23:54:28いままでの乱数の何が問題で、何を今回のは解決したのか、
定義不明な言葉を使わずに説明してよ。
0648デフォルトの名無しさん
2007/09/04(火) 23:54:49いや、君が作ったものは君の欲しいものになってないから。
欲しいものと、実装できたものを、一度表にでもまとめてごらん。
0649デフォルトの名無しさん
2007/09/04(火) 23:56:190650デフォルトの名無しさん
2007/09/04(火) 23:57:19懐かしいなあ)
0651デフォルトの名無しさん
2007/09/04(火) 23:59:16>>451 で説明してる以上にはそれをちゃんとそれを説明できてないってのがまず問題だよね。
ちょっと今回はもう興がだいぶ削がれちゃってるからやらないけど、
また、こっち方面でうずうずしてきたら今度はちゃんと問題定義からやり直すように致します。
0652デフォルトの名無しさん
2007/09/05(水) 00:00:410653デフォルトの名無しさん
2007/09/05(水) 00:04:12しばらく続いたことだし、>>628 は悪魔の証明がんばってねw
0654デフォルトの名無しさん
2007/09/05(水) 00:07:07>>451って何も説明していないし、根本的に間違ってるよ。
MT以上に相関性をなくすために、
いったいどれだけのプールが必要かわかってないみたいだし。
0655デフォルトの名無しさん
2007/09/05(水) 00:08:59相関性あることに気が付いていない無いの?本人か?
出力値から簡単に逆算できるぞ、あれ。
0656デフォルトの名無しさん
2007/09/05(水) 00:11:21算出式書いて。
0657デフォルトの名無しさん
2007/09/05(水) 00:12:52数列とアルゴリズム書いたら逆算してやる。
アルゴリズムが同じだったら、数列だけでいいぞ。
0658デフォルトの名無しさん
2007/09/05(水) 00:13:10>>628は相関性がある事の一点を指摘すればいいわけだから別に悪魔の証明じゃないんだよ
http://ja.wikipedia.org/wiki/%E6%82%AA%E9%AD%94%E3%81%AE%E8%A8%BC%E6%98%8E
既に気づいてるそうだし
0659デフォルトの名無しさん
2007/09/05(水) 00:15:27公開されてるんだから、自分で全部用意できるだろ?
0660デフォルトの名無しさん
2007/09/05(水) 00:16:07>>637は、>>630の依頼の仕方が酷いといっているだけです。
0661デフォルトの名無しさん
2007/09/05(水) 00:16:13相関性がちゃんと定義されてないから無駄。
0662デフォルトの名無しさん
2007/09/05(水) 00:19:20628の定義・基準では相関性があるって事なんだろ
だから628がそういう定義も込みで証明を出してくるのを待つだけ
0663デフォルトの名無しさん
2007/09/05(水) 00:23:280664デフォルトの名無しさん
2007/09/05(水) 00:24:19逆算プログラムとアルゴリズムは教えるつもりはない。
そうすると、少し修正しただけのものを作ってくるだろうから。
ただ、逆算できることを証明してほしいならその手伝いをしてあげてもいい。
こっちが初期値を聞かずに、出力値から当てれば、その証明になるだろ。
0665デフォルトの名無しさん
2007/09/05(水) 00:24:48正解
0666デフォルトの名無しさん
2007/09/05(水) 00:25:350667デフォルトの名無しさん
2007/09/05(水) 00:30:19はい、じゃ、アルゴリズムは prime spiral で
出力は↓
8A1579636B2EC55D39F006AA24CC75860E20D48
B428C34B0E38C6C538F3EE4A1239889FCDBD459
8D80B40EF3EF1F0A5DB8B581D8F85497945E5FD
1C2BDC83C6FE1FB759C5EFB0CD83BCDA8E48BC0
172226BE2615F284C7C66DC6E9D07D4DF1203D2
0D27C584C79B99C79BAB7AAEA7C6AB6782DAB5F
FD586FCA9308922BAEC087A04F732D86E49880D
CC70BBCF3BACBCD4E212FA7FE5D7DAB81EE56D5
4EC7A0522645C6912D5E33F1A80C701B481DF86
2F3C587F2D49E2D10CE7D591A5E9209F72444FB
1FD8899C3F48749640924127B735FF79525C78E
226887745DAF96F3099E776724ACE45DED7B9B6
FA841B3433A0E6EDFB130F5D6D8F0270D4B80A3
028C1040FB5D2D2AD7D8916B93D2B1457E1D13A
C3B886870D16030DD2BA2973ECFE05A7425CAE5
0668デフォルトの名無しさん
2007/09/05(水) 00:31:43それで足りるのか? まぁ、いくつ必要なのか 664 が書いてないから
分からんが。
0669デフォルトの名無しさん
2007/09/05(水) 00:35:43初期値がわかるのか。次に出る値がわかるのかとおもったよ。
まぁ、次に出る値を当てることはMTでも可能か。
0670デフォルトの名無しさん
2007/09/05(水) 00:37:0032ビットずつちゃんと区切れよ。検証してもらう態度じゃないぞそれは。
それからデータはお前のサイトにおけ。本人以外に協力してやる気もないから。
数列の量はMTに文句言ったのだから、620個用意しとけ。
0671デフォルトの名無しさん
2007/09/05(水) 00:37:500672デフォルトの名無しさん
2007/09/05(水) 00:37:560673デフォルトの名無しさん
2007/09/05(水) 00:38:360674デフォルトの名無しさん
2007/09/05(水) 00:38:46ワラタw
0675デフォルトの名無しさん
2007/09/05(水) 00:38:480676デフォルトの名無しさん
2007/09/05(水) 00:39:20どっちが先にくたばるかな
0677デフォルトの名無しさん
2007/09/05(水) 00:39:48ところで合ってたかどうかの証明はどうやるんだ?
0678デフォルトの名無しさん
2007/09/05(水) 00:41:05こっちが逆算した数列見れば本人にはわかるだろ。
0679デフォルトの名無しさん
2007/09/05(水) 00:41:05その初期値で、同じ出力が得られることを確認すれば良いんじゃね?
0680デフォルトの名無しさん
2007/09/05(水) 00:41:19初期値使って自分で乱数生成してみりゃ自明
どんだけ生成すればでてくるのかは知らんが..
0681・∀・)っ-<コ:彡-
2007/09/05(水) 00:41:450682デフォルトの名無しさん
2007/09/05(水) 00:42:07あ、そうか。だから本人のサイトにアップするなりして
確証を持たせる必要があるからか。
2chトリップを利用するのはどうだ?
トリ解析器を使われると一方向性がちょっと怪しいけど
0683デフォルトの名無しさん
2007/09/05(水) 00:43:280684デフォルトの名無しさん
2007/09/05(水) 00:45:05ほんとだよw
もう夏休みも終ったというのに…
あ、大学生はまだしばらく休みだな。
さて、社会人の俺はもう寝る。
明日どうなっているのか楽しみだ……
0685デフォルトの名無しさん
2007/09/05(水) 00:46:16それじゃ証明にならんぞ。ある一定部分が同じでもその後の出力は異なるパターンがいくつもあるし。
ん? てか、だとしたらそうならない量のデータが必要なわけだが、620で本当に足りるんか?
0686デフォルトの名無しさん
2007/09/05(水) 00:49:250687・∀・)っ-<コ:彡-
2007/09/05(水) 01:21:52確かに乱数生成ルーチンにもなるよな。あんまり効率よくないが。
0688デフォルトの名無しさん
2007/09/05(水) 01:35:580689688@・∀・)っ-<コ:彡-
2007/09/05(水) 01:38:400690デフォルトの名無しさん
2007/09/05(水) 02:00:250691デフォルトの名無しさん
2007/09/05(水) 02:46:300692デフォルトの名無しさん
2007/09/05(水) 03:41:290693デフォルトの名無しさん
2007/09/05(水) 04:15:22あと何万年ー?
0694デフォルトの名無しさん
2007/09/05(水) 07:06:540695デフォルトの名無しさん
2007/09/05(水) 08:01:33好きよ貴方が楽園〜〜
0696デフォルトの名無しさん
2007/09/05(水) 08:11:510697デフォルトの名無しさん
2007/09/05(水) 14:42:28釣り宣言マダー?
0698デフォルトの名無しさん
2007/09/05(水) 15:02:21釣りじゃないよ。
なんつーか、本人以外は逆算できることに気が付いている奴が多いんじゃないの?
前の方のレス読んだら、ヒントが書き込まれているし。
初期値がわかると言っても、正確には同じ結果を出す、初期値のうちの一つの解になるんだけどね。
次に出る値も当然わかるよ。
あと、620個も本当はいらないんだけどね。
未知数の数がいくつか考えれば、必要なデータ数が遙かに少ないことは、わかるやつにはわかると思う。
ちなみに、XOR演算であるという点以外は、中学レベルの数学で十分求まるよ。
0699デフォルトの名無しさん
2007/09/05(水) 15:22:170700デフォルトの名無しさん
2007/09/05(水) 15:25:150701デフォルトの名無しさん
2007/09/05(水) 15:42:51そこまで簡単ということはただの連立方程式
さらに恐らく1ビットずつ独立して計算できるとかかな。
0702デフォルトの名無しさん
2007/09/05(水) 16:07:51当たり
0703デフォルトの名無しさん
2007/09/05(水) 21:56:36>釣りじゃないよ。
じゃぁ、素で言ってるの? どっちにしろ、お前にはガッカリだ。
エントロピープールがほとんどゼロで初期化されちゃったとかの極端なケースを除けば
その後の出力予測云々の話以前に、そもそもその程度の数じゃ、その後の出力が
1パターンに収束しないし、1パターンに収束するには何桁も出力が足りない。
いくらなんでも prime spiral の特性を理解してなさすぎ。
0704デフォルトの名無しさん
2007/09/05(水) 21:58:020705デフォルトの名無しさん
2007/09/05(水) 22:05:570706デフォルトの名無しさん
2007/09/05(水) 23:46:35収束するよ。
嘘だと思うなら、収束しない例を一例でいいから書いてごらん。
0707デフォルトの名無しさん
2007/09/05(水) 23:51:060708デフォルトの名無しさん
2007/09/05(水) 23:51:57というかさ、お前本人だろ。
本人以外に、prime spiralに興味を持ち、特性を理解して、
かつ問題も見えず、収束していないことに気が付かない奴っているの?
知能が道化師レベルの癖に、問題点も見えずに特性を理解した気になって
過大評価できる奴なんて、あり得ないだろ。
0709デフォルトの名無しさん
2007/09/05(水) 23:52:40そろそろ隔離スレ作るか?
0710デフォルトの名無しさん
2007/09/05(水) 23:53:21指示したものをサイトにアップしたらやるよ。
0711デフォルトの名無しさん
2007/09/06(木) 00:02:11お前にはいい加減うんざりだし、他の人にも迷惑だから
お前がそれで引き下がるならお前がいうデータをサイトにアップしても構わんが、
その前にお前が俺じゃないことを、証明する方法を考えてくれんか?
お前のことだから、予測ができなかったことを今度は俺の自作自演だって騒ぐんだろ?
構ってちゃんみたいだから、こいつが俺じゃないことを証明する方法を明示しない限り
俺だけでも、このスレから去ることにするわ。
0712デフォルトの名無しさん
2007/09/06(木) 00:10:54ん、少なくとも俺は迷惑じゃないぞ。
wktkして二人のやり取りを見てる。
0713デフォルトの名無しさん
2007/09/06(木) 00:11:01> 他の人にも迷惑だから
迷惑な人の数 <<<<<<< ニヤニヤしながら展開を見守ってる人の数
0714デフォルトの名無しさん
2007/09/06(木) 00:12:110715デフォルトの名無しさん
2007/09/06(木) 00:17:14どうせ他に話題が無くて過疎ってたのだからお気になさらずに^^
0716デフォルトの名無しさん
2007/09/06(木) 00:42:09>お前にはいい加減うんざりだし、他の人にも迷惑だから
根拠もなく勘違いでMTを批判したり、その一方で危険なライブラリを
配布しようとしている方が遙かに世の中に対して迷惑であろう。
>その前にお前が俺じゃないことを、証明する方法を考えてくれんか?
なんでそんなものが必要なんだ?
別に俺の存在とは関係なくやればいいだろう。
お前が自分のサイトで、prime spiral が安全か検証してくれる人を募集する形で、
出力例をアップすればいいだろ。
そもそも乱数のアルゴリズムを発表するときは、
ライブラリを使用する人のためにチェック用に正規の出力例をつけるものだ。
それにプラスして、エントロピープールを秘密にしてある出力例を追加して、
乱数の予測や逆算の評価をお願いするというだけでいいだろう。
そうすれば、俺はお前に協力してやると言っているのだ。
口は悪いし、本気で馬鹿にしているが、いいか、これはお前のための善意だ。
下手をするとお前の一生の恥になり、信用を失う。
0717・∀・)っ━━━┓
2007/09/06(木) 00:45:060718デフォルトの名無しさん
2007/09/06(木) 02:25:46>>451のは結局のところGFSR(Generalized Feedback Shift Register)そのもの。
これはM系列の一種でつまるところ普通の線形漸化式。
indexというカウンタがindex_maskという変数でxorされてるので
具体的には分かりかねるが大きな多項式になっとる。
index_mask == list_a[ 0 ]のようなのでここを変えると多項式が変わる。
で、本人は勘違いしているようなのだけど、
適当に多項式を作っても原始多項式でないと周期は保証されないし、
場合によっては出現する組み合わせもかなり少なくなる可能性アリ。
つまり素数を全部掛けたものがそのまま周期になるわけじゃないので注意。
X^31 + X^29 + X^11 + 1とか適当に作っても実際に判定してみないとダメ。
上の方に書いてあったけど選んでxorしたものも最終的には漸化式の形になるよ。
ただ>>451のちょっと面白いところはランダムに多項式を作ってるってところかな。
でも動的に作ってるから何が出来るか分からんのが問題だが。
たまたま長周期になるかもしれんし全然ダメなのも出来るかもしれん。
多項式をどうするかは重要な問題だからな。
結局>>451のはGFSRというシンプルなものを難しく複雑に作っただけ。
index_mask==list_a[0]以外の配列を0と1で初期化すれば普通にW=1bitの線形漸化式になるよ。
MTはTGFSR(Twisted GFSR)といってこのWが32bitになってさらに
縦と横のベクトルが組み合わさって長周期を実現しててえらいこっちゃ。
さらに調律が加わって(これはいらない気もするが)分布も良くなってる。
>>451のは32bitの配列を使ってるけど結局GFSRのままなんで
縦と横が独立してるから周期も分布もいまいち。
勉強しましょう。
0719デフォルトの名無しさん
2007/09/06(木) 08:35:44MTの調律は、分布じゃなくて
ビット毎の相関を減らすためのくふうで、
そこまでイラネって場合は調律しなくてもいい。
(高速化するにも邪魔だし)
0720デフォルトの名無しさん
2007/09/06(木) 09:39:07> 多項式をどうするかは重要な問題だからな。
もっともな意見なんだが、作者は >595 とか本気で返事してくるからなぁ
0721デフォルトの名無しさん
2007/09/06(木) 09:55:190722デフォルトの名無しさん
2007/09/06(木) 10:17:39貴方の言うことはもっともだけど、彼の場合は多項式以前の問題。
その説明だって理解できているのか正直怪しい。
>>703
>そもそもその程度の数じゃ、その後の出力が
>1パターンに収束しないし、1パターンに収束するには何桁も出力が足りない。
理解できたなら、こういう間違った発言に気がつくと思うけど…
>いくらなんでも prime spiral の特性を理解してなさすぎ。
作者が一番特性を理解していないんだから困ったもんだ。
0723デフォルトの名無しさん
2007/09/06(木) 12:30:090725デフォルトの名無しさん
2007/09/06(木) 13:06:030726デフォルトの名無しさん
2007/09/06(木) 13:24:120727デフォルトの名無しさん
2007/09/06(木) 16:19:130728デフォルトの名無しさん
2007/09/06(木) 17:24:470729デフォルトの名無しさん
2007/09/06(木) 18:01:13ついに誰かれ構わず本人認定しだしたな。
末期症状。
ちなみに俺はもちろん作者なんかではない、ただの野次馬。
0730デフォルトの名無しさん
2007/09/06(木) 18:12:40別に認定はしてないよ。
自分がするべきことをしないでそういうことを言いそうなやつだから、疑いがあったから聞いただけ。
気を悪くしたのならスマン。
それから、prime spiral の特性を理解していれば、
出力値から、同じ乱数列を出す初期値のうちの一つの解を求めることができるのはわかる。
0731デフォルトの名無しさん
2007/09/06(木) 18:19:48sageてない奴は同一人物。
0732デフォルトの名無しさん
2007/09/06(木) 18:26:21聞くは一時の恥、聞かぬは一生の恥。
0733デフォルトの名無しさん
2007/09/06(木) 22:20:030734デフォルトの名無しさん
2007/09/06(木) 22:55:33あーあ。
0735デフォルトの名無しさん
2007/09/06(木) 23:23:200736デフォルトの名無しさん
2007/09/07(金) 01:03:070737デフォルトの名無しさん
2007/09/07(金) 01:07:550738デフォルトの名無しさん
2007/09/07(金) 01:10:05ML アーカイブは残り続けるけどな。Webも魚拓とっとく?
0739デフォルトの名無しさん
2007/09/07(金) 02:26:390740デフォルトの名無しさん
2007/09/07(金) 02:43:09どこまで追い込むつもりだよ。
0741デフォルトの名無しさん
2007/09/07(金) 02:48:190742デフォルトの名無しさん
2007/09/07(金) 03:58:09危険なライブラリを気がつかずに配布していることは作者も望まないだろ。
間違いを証明するのは、作者も望んでいるはず。
468 名前:デフォルトの名無しさん 投稿日:2007/08/28(火) 21:03:55
この手のものはいろんな批判に耐えることができてなんぼって面もあるんで
いろんな批判もウェルカムですけど、この乱数アルゴリズムは本当に優れた
ばらつきの乱数列を出力できるんで、是非とも皆様、他とは異なるこの上品質
の乱数列を一度ご賞味くだされ。
499 名前:デフォルトの名無しさん 投稿日:2007/08/30(木) 22:37:32
prime spiral にあるのは「上質な乱数列」、ただそれだけです。
630 名前:デフォルトの名無しさん 投稿日:2007/09/04(火) 23:40:25
>>628
>prime spiralが相関性ありまくりで最悪であることを証明して投稿してやるよ。
ごめん、これはぜひ、お願い。
検証にご協力頂けるのは助かります。
0743デフォルトの名無しさん
2007/09/07(金) 04:25:580744デフォルトの名無しさん
2007/09/07(金) 05:27:210745デフォルトの名無しさん
2007/09/07(金) 05:29:51危険ってここではどういう意味?
暗号用途に使えないのはMTも一緒だと思ったので。
0746デフォルトの名無しさん
2007/09/07(金) 07:44:44MTより「良い」乱数だと宣伝しているけど、実際は周期などの点で低品質。
信じて使うとろくなことにならないってことでしょ。
0747デフォルトの名無しさん
2007/09/07(金) 08:09:27十分に引き付けてから撃つ。
0748デフォルトの名無しさん
2007/09/07(金) 08:27:27ここの内容が訂正されるまでじゃない?
ttp://www.trickpalace.net/column/random.htm
> この prime spiral のように問題を引き起こしかねない相関性を全て排除した擬似乱数アルゴリズムを無相関性擬似乱数アルゴリズム
> 「MTも所詮、線形合同法と五十歩百歩」
0749デフォルトの名無しさん
2007/09/07(金) 10:50:30ほとんど証明に近い指摘はたくさんあるし、解き方のヒントも提示してきた。
これでわからないレベルなら、初期値の例を示して証明するしかないだろ。
そのためには、作者の協力も必要。だって作者にわからせるんだから。
>>745
作者自体が理解していないアルゴリズムで、品質に根拠がないばかりか、
まともな検証すらされていなく、問題点に気がつかず「良い」と宣伝され、
使った人間が騙されて被害を被るプログラムだから。
俺は作者のやっていることはテロに等しいと思っている。
本当に世のために公開しようとしているのなら、
無責任な宣伝をする前に、やるべきことがたくさんあるはず。
0750デフォルトの名無しさん
2007/09/07(金) 18:36:48本当によい疑似乱数が必要なら自分でチェックするもんだろ。
0751デフォルトの名無しさん
2007/09/07(金) 18:38:14つ スルー力
0752デフォルトの名無しさん
2007/09/07(金) 19:00:140753デフォルトの名無しさん
2007/09/07(金) 19:02:22作者に間違いを認めさせることと、
間違っていることを世間に証明することのどちらがゴールなのか判然と
しないな。落ち着け。
0754デフォルトの名無しさん
2007/09/07(金) 19:03:39俺は元ネタのあれについては一貫してスルーしてるよ。
「君もスルーしてくれると良いな」と思ってるんだよ。
0755デフォルトの名無しさん
2007/09/07(金) 19:05:240756デフォルトの名無しさん
2007/09/07(金) 19:22:54君、腐れ女子以下w
07571
2007/09/07(金) 19:37:27なんだか随分と盛り上がっているようで。
しかし、もっとましな方向で盛り上がってくれと思う。
MTFSとか、もっと美味しそうな話題がいくらでもあると思うんだがよ?
0758デフォルトの名無しさん
2007/09/07(金) 19:40:56まあいいや
0759デフォルトの名無しさん
2007/09/07(金) 19:47:06両方
0760デフォルトの名無しさん
2007/09/07(金) 19:49:09気持はわかるが、MTに問題があるからもっといいものをといって出されたものが糞だったんだが。
で、その糞をサイトやMLでばら撒いている馬鹿がいるわけだが。
0761デフォルトの名無しさん
2007/09/08(土) 00:06:00そこまで口汚く罵れる精神構造がよくわからん。
別に作者に使うことを強要されているわけでもないし、
スルーしておけばよいだけのこと。
新しいものを出そうとする人間をたたいてばかりいると、
そのうち国が滅びるよ。
(あなたがMTの作者ならともかく)
0762デフォルトの名無しさん
2007/09/08(土) 00:35:040763デフォルトの名無しさん
2007/09/08(土) 00:51:43>新しいものを出そうとする人間をたたいてばかりいると、
そういう方向性なら歓迎するところだが、
MTに対する勘違いした間違った批判を行い、【同時に】、劣悪なものをそれよりも優れていると
主張する態度に問題を感じている。
彼はそこそこ手広い活動をしているのだから、わかっていない他人を間違った方向に進ませてしまう恐れもある。
それに、本当に新しく、良いものを作り出す人間は、彼のように思いあがってはいないよ。
ほとんどの優秀な人は、彼と全く正反対で、非常に謙虚で、慎重で、真摯だ。
俺は今回のことで彼が深く反省し、学問や技術に対する態度を改めることを祈っているよ。
0764デフォルトの名無しさん
2007/09/08(土) 00:54:13> 新しいものを出そうとする人間
w
>> 「MTも所詮、線形合同法と五十歩百歩」
0765デフォルトの名無しさん
2007/09/08(土) 01:08:490766デフォルトの名無しさん
2007/09/08(土) 01:11:38作者の批判の方が酷いってことだろ。
線形合同法と五十歩百歩なのは、prime spiralの方であり、MTはレベルが全く違う。
0767デフォルトの名無しさん
2007/09/08(土) 01:51:44技術的な議論から逃げているのだから仕方ない
0768デフォルトの名無しさん
2007/09/08(土) 05:43:28ここでつついても技術的な議論にならないのなら
ここでつつく意味もない
0769デフォルトの名無しさん
2007/09/08(土) 05:45:030770デフォルトの名無しさん
2007/09/08(土) 09:52:21%を除去すればゲームに使うのにはよさそうだ
0771デフォルトの名無しさん
2007/09/08(土) 10:20:56xorshift で良いじゃん。
0772デフォルトの名無しさん
2007/09/08(土) 12:03:29どうすればいいの
0773デフォルトの名無しさん
2007/09/08(土) 12:09:28全部0じゃなきゃいいんだ。
適当に線形合同法でも使え。
0774デフォルトの名無しさん
2007/09/08(土) 12:34:02そうなんだ
1と0の数が同じほうがいいとかあるのかな
0775デフォルトの名無しさん
2007/09/08(土) 12:42:51出来るだけ均等な方が望ましい。
でも自分が調べた限り偏ってても大した問題は出てない。
0776デフォルトの名無しさん
2007/09/08(土) 15:26:44mtでいいじゃん
0777デフォルトの名無しさん
2007/09/08(土) 16:51:29xorshiftで十分?
0778デフォルトの名無しさん
2007/09/08(土) 16:58:13トランプ、麻雀なんかは階乗のオーダーなので
それなりにでかい周期がいる。
あと分布もよくないと。
mtなんかうってつけだな。
アクションとかは応答性が求められるからxorshiftみたいなのが良い。
レジスタに全部おさまるくらい小さくて速いやつ。
0779デフォルトの名無しさん
2007/09/08(土) 19:47:25乱数の使用頻度はゲームのジャンルより、実はエフェクト出す数に
よらんか? 特にパーティクルを適当に飛び散らす系。
0780デフォルトの名無しさん
2007/09/08(土) 23:40:57ダメだって。分布も周期も最悪に近い。
無駄に遅い分一般的な線形合同法よりも酷い。
0781デフォルトの名無しさん
2007/09/09(日) 00:07:19中の人、結局、これを多少なりともマトモな体裁で書き直す気無いのかねぇ。
ttp://www.trickpalace.net/column/random.htm
まっとうに議論するためには、言葉の定義と評価基準を示して、これこれこういう点で
優れてると証明つきで出すのが最低ラインなんだが。
0782デフォルトの名無しさん
2007/09/09(日) 11:20:070783デフォルトの名無しさん
2007/09/09(日) 13:03:270784デフォルトの名無しさん
2007/09/09(日) 13:06:32作者は多分そう思ってる。
しかし、作者を批判してる人の方が、
作者が土俵に上がるまで手の内は見せないというか
わざと隙があるように振舞ってて
かなりえげつない。
0785デフォルトの名無しさん
2007/09/09(日) 13:09:41思ってる時点ですでに負けじゃんw
0786・∀・)っ━━━┓
2007/09/09(日) 18:34:44ここの連中は評価しようがないから。
牟板発祥のソフトって何があったっけ?
DGCAくらいしか知らん。
0787デフォルトの名無しさん
2007/09/09(日) 18:37:420788デフォルトの名無しさん
2007/09/09(日) 20:05:200789・∀・)っ━━━┓
2007/09/09(日) 20:15:050790デフォルトの名無しさん
2007/09/09(日) 20:48:56確かにそうだな。
見る人間が見れば、詰んでいることはわかる筈だし。
0791デフォルトの名無しさん
2007/09/10(月) 06:38:43同意。さっさと証明出してほしい。
0792デフォルトの名無しさん
2007/09/10(月) 10:05:02でもその前に作者がやることをやらないとね。
0793デフォルトの名無しさん
2007/09/10(月) 23:53:23作者の介在なし証明は書けるだろ。それだけで十分社会の役に立つから
よろ。
0794デフォルトの名無しさん
2007/09/11(火) 00:12:48作者の態度が
気に食わない
0795デフォルトの名無しさん
2007/09/11(火) 00:40:08少しでもよくなる可能性があるなら情報を出した方が良いんじゃないか
0796デフォルトの名無しさん
2007/09/11(火) 00:44:13そんなことをしてもMTには勝てないから全くの無駄。
本人にとっては修行になるだろうが、第三者的には練習ライブラリなどいらないので。
利用者のことをまともに考えていない作者はプログラマ失格だと思う。
0797デフォルトの名無しさん
2007/09/11(火) 03:59:300798デフォルトの名無しさん
2007/09/11(火) 04:36:24証明に対して、相関性の言葉の定義が違う、とか悪あがきをしだすに 3 ガノッサ。
0799デフォルトの名無しさん
2007/09/11(火) 08:32:18できないとは思わんけど、もう作者もいないだろうし黙ったら。
0800デフォルトの名無しさん
2007/09/11(火) 08:47:04ってかやめさせたければ何か他のネタ提供すれば
ただ過疎らせたいのなら別だけど
0801デフォルトの名無しさん
2007/09/11(火) 09:23:17これで続けるなら落としたほうがまだ良いよ。
0802デフォルトの名無しさん
2007/09/11(火) 10:23:46どうどうとサイトで酷いプログラム公開していて、黙れというのは筋が通らない。
ここで続けるのが反対なら、俺が別のスレ立てる。だが、その前に、作者には選択肢をやろう。
・prime spiralの説明で使われている言葉の定義と評価基準を明確に示してサイトを修正する。
・検証のためのデータを提供する。
・MTに対する中傷を取り下げ、サイトとMLに謝罪文を載せ、prime spiralは間違いとして公開やめる。
以上のどれかが実行されないなら、今まで同様、ここで話題の一つとするか、
「問題のあるプログラムを載せているサイトとその議論」というようなスレを立てて、
第一弾といてprime spiralを紹介する。
選択の期限は9月15日とする。
0803デフォルトの名無しさん
2007/09/11(火) 10:24:370804デフォルトの名無しさん
2007/09/11(火) 10:28:32作者が動いたらやる、で止まってバッシングだけになってるのも別にいいけど、口だけにも見えちゃうお。
0805デフォルトの名無しさん
2007/09/11(火) 10:33:34作者か?
さっさと>>802に応じろよ。
0806デフォルトの名無しさん
2007/09/11(火) 10:39:53違うって言っても信憑性無いのでROMるね。
でももうスレ違いだしID出る板でやらない?
作者のブログにTB送っとけば伝わるでしょ。
0807デフォルトの名無しさん
2007/09/11(火) 10:41:33ワロスw
0808デフォルトの名無しさん
2007/09/11(火) 10:44:33802だが、俺は(君が作者だとは)思ってないよ。
>でももうスレ違いだしID出る板でやらない?
これは俺も賛成。でもいきなり行動に移す前に、まず作者の出方を待ち、
その間にやり方を検討したりしようと思っている。
0809デフォルトの名無しさん
2007/09/11(火) 10:45:320810デフォルトの名無しさん
2007/09/11(火) 10:52:560811デフォルトの名無しさん
2007/09/11(火) 11:02:26>>808
そうですね、乱数スレなんでこのアルゴリズムに対する駄目だしができれば、別にここでもいいとは思うんですけど。
作者が何もしなくてもこれが駄目だって言う根拠を人の目に着くとこに置いとければ>>763で危惧してることも起きないだろうし。
まあ間違いがあるなら本人に認めてもらうってのも大事だとは思うんだけど、でも本人ここもう見てない可能性もあるので、
何かしらの手段で存在伝えた方がいいような。
>>809
よろ
0812デフォルトの名無しさん
2007/09/11(火) 11:09:49prime spiralを使う人はほとんどいないだろう。
(使おうと思う人がいるなら、その程度も気にしないのレベルということ)
とりあえず>>802も含めてウザイのでとっとと別スレにでもいってほしいね
0813デフォルトの名無しさん
2007/09/11(火) 11:21:21了解。一応、他の人の意見も聞いて、ここで技術的な議論ができないようなら、別スレ立てて誘導することにする。
0814デフォルトの名無しさん
2007/09/11(火) 18:31:32趣旨なんてあったっけ。
専用スレに隔離は同意
0815デフォルトの名無しさん
2007/09/11(火) 18:39:17mersenee twisterを意識しすぎてワタラ。
0816デフォルトの名無しさん
2007/09/11(火) 20:00:45よくもまぁブラフでここまで引っ張るもんだ。
僅かな出力でその後の出力が予測可能ってのがブフラだってことを証明するコードやるからいい加減大人しくなれ。
#include <stdio.h>
#include "trickrng.h"
using namespace tricklib;
0817デフォルトの名無しさん
2007/09/11(火) 20:01:33{
// *a の初期化状態が極端に酷い場合には同じ値が sync_length を大幅に上回る回数出力されます。
// *a の初期化状態が極端に酷くない場合でも、1/2^32の確率で同じ値が sync_length を上回る回数出力されます。
assert(0 < sync_length);
assert(sync_length < 0x80000000);
// sync_mask の算出。
uint32_t sync_mask = 1;
while(sync_mask < sync_length)
{
sync_mask <<= 1;
}
// sync_length を精確に反映させる為に index を調整。
*(((uint32_t*)(a +1)) -1) = sync_mask -sync_length;
// ↑この行は a->index = sync_mask -sync_length; の意。private なので本来はアクセスしちゃいけない所。
// *a を sync_mask で XOR したものを *b とする。
for(int i = 0; i < sizeof(*a)/ sizeof(uint32_t); ++i)
{
((uint32_t*)b)[i] = ((uint32_t*)a)[i] ^sync_mask;
}
}
0818デフォルトの名無しさん
2007/09/11(火) 20:02:27{
if (2 <= argc)
{
dynamic_prime_spiral_dice dice_a, dice_b;
tune_dice(atoi(args[1]), &dice_a, &dice_b);
uint32_t i = 0, a, b;
do
{
a = dice_a.roll();
b = dice_b.roll();
printf("\r0x%08.8X:0x%08.8X:%010d\n", a, b, i++);
}
while(a == b);
}
return EXIT_SUCCESS;
}
0819デフォルトの名無しさん
2007/09/11(火) 20:02:53(´A`)
0820デフォルトの名無しさん
2007/09/11(火) 20:03:18・乱数列にランダムアクセスが可能。
・出力の難収束性。
・tune_dice()みたいな処理が可能。
当初は"乱数列の品質"だと思ってたけど、これだけ売りがあれば出力品質が
悪いなんてことが多少証明されたところで、prime spiral はもうすでにひとつの
擬似乱数アルゴリズムとしてありだと思うですよ。(もちろん、それでは無相関性
擬似乱数アルゴリズムとは言えないんですけど。)
出力品質がよいということが証明されればさらに素晴らしいことなんでまた今度
dieharder でのテストぐらいはやっとこうと思うです。
じゃぁね。
0821デフォルトの名無しさん
2007/09/11(火) 20:08:02×当初は"乱数列の品質"だと思ってたけど、
○当初は"乱数列の品質"だけだと思ってたけど、
0822デフォルトの名無しさん
2007/09/11(火) 20:12:360823デフォルトの名無しさん
2007/09/11(火) 20:33:54保守頼んだ。
0824デフォルトの名無しさん
2007/09/11(火) 21:14:24>よくもまぁブラフでここまで引っ張るもんだ。
>僅かな出力でその後の出力が予測可能ってのがブフラだってことを証明するコードやるからいい加減大人しくなれ。
どう証明になっているか説明してくれんか。
もし僅かな出力でその後の出力の予測が不可能なら、
例えば、最初の600個が一致して、601個目が一致しない例を示せばいい。
しかし、現実にはそういう例は出せない。これは予測可能であることのヒントだ。
0825デフォルトの名無しさん
2007/09/11(火) 21:22:32「思うです」とか変な書いている馬鹿は本人か。
0826デフォルトの名無しさん
2007/09/11(火) 21:22:56「思うです」とか変な日本語を書いている馬鹿は本人か。
0827デフォルトの名無しさん
2007/09/11(火) 21:27:54そこのコードをコンパイルしてコマンドライン引数に600を指定してみw
0828デフォルトの名無しさん
2007/09/11(火) 21:29:32> 乱数列にランダムアクセスが可能。
(擬似)乱数列にランダムアクセスできることの意義を見出せないんだが……。
0829デフォルトの名無しさん
2007/09/11(火) 22:07:35> 無相関性擬似乱数アルゴリズム
超古典だが、LFSR で特性多項式が原始多項式(因数分解不可)の場合が
無相関と証明されてなかったっけ?
0830デフォルトの名無しさん
2007/09/11(火) 22:15:54それは入力に対して出力に相関性があらわれないことだから、意味が違うんじゃね?
0831デフォルトの名無しさん
2007/09/11(火) 22:34:37膨大なデータを扱うシミュレーションなんかで
乱数を元に作成した一時的にいらないデータを破棄して
後で必要になったときには再計算することができるとかそんな利点があると思うけど。
0832デフォルトの名無しさん
2007/09/11(火) 22:43:07何かおかしいと思ったら、indexを後からいじってるじゃん。
0833デフォルトの名無しさん
2007/09/11(火) 22:44:12初期ベクトル持っていれば再計算できる。
0834デフォルトの名無しさん
2007/09/11(火) 22:49:02乱数が無相関という場合に、それ以外の意味があるの? 独立性を議論してる
わけじゃないよね。
0835デフォルトの名無しさん
2007/09/11(火) 22:49:58それがなにか問題なのか?
0836デフォルトの名無しさん
2007/09/11(火) 22:52:40可能か不可能かで言えばそうだけど、必要な計算量に雲泥の差がでるぞw
0837デフォルトの名無しさん
2007/09/11(火) 22:56:47初期ベクトルではなく状態ベクトルじゃね?
0838デフォルトの名無しさん
2007/09/11(火) 23:23:56再現ポイントの初期ベクトルなら同じだろ。
0839デフォルトの名無しさん
2007/09/11(火) 23:58:00初期ベクトルではなく状態ベクトルじゃね?
0840デフォルトの名無しさん
2007/09/12(水) 01:49:43index_maskとindexの組み合わせを同時に変えていいなら、そりゃ簡単に一部が一致する系列を作れる。index_mask^indexが同じ範囲は同じになるからな。
実際のところindex_maskは、各ビット位置が表す周期で系列を入れ替えているだけ。
だから、エントロピープールとindex_maskの組み合わせと、indexと出力系列の組み合わせは一対一に対応する。
だからindexと最低限の出力系列(各素数の和)が得られれば、逆算ができるわけだ。
ただ、indexがどこから始まっているからわからないなら、最小の出力系列で、その後が完全にわかるわけではない。
ただ、ランダムアクセス可ということでindexが0から始まるものなら最低限の出力系列から、すべてがわかる。
また、indexの開始が不明でも、その後に出てくる数列は入れ替わっているだけで同じものが同じ分布で出現する。
例えば、コマンドライン引数に2を指定して出力するとこうなる。●は同じところ、△はずれているだけのところ
0x331EE257:0x331EE257:0000000000 ●
0xAC31D68A:0xAC31D68A:0000000001 ●
0xCA4DAAEF:0x0A4D250D:0000000002 △
0x2CEE50F2:0xDD950B6E:0000000003 △
0x91448FED:0x91448FED:0000000004 ●
0x11C949BE:0x11C949BE:0000000005 ●
0x0A4D250D:0x563953EE:0000000006 △
0xDD950B6E:0x9C9C9179:0000000007 △
0x36D2A9DB:0x36D2A9DB:0000000008 ●
0x8B051CF8:0x8B051CF8:0000000009 ●
0x563953EE:0x9D3900E1:0000000010 △
0x9C9C9179:0x206E7721:0000000011 △
0xDC87B479:0xDC87B479:0000000012 ●
0x20D18FD0:0x20D18FD0:0000000013 ●
0x9D3900E1:0x7B1CC024:0000000014 △
0x206E7721:0x3F4B54FE:0000000015 △
0x1B94729E:0x1B94729E:0000000016 ●
0841デフォルトの名無しさん
2007/09/12(水) 01:53:51MTの場合、初期ベクトルと状態ベクトルの違いなんてないだろ。
0842デフォルトの名無しさん
2007/09/12(水) 01:59:47ないから、敢えて初期ベクトルとは呼ばずに状態ベクトルと呼ぶでしょ。
リファレンス実装でも state vector となってるし。
いずれにせよ、それ保存しとけば全然問題ないって主張には同意。
0843・∀・)っ━━━┓
2007/09/12(水) 02:04:210844デフォルトの名無しさん
2007/09/12(水) 02:21:32つまりindex_maskは何の役にも立っていないな。
0845デフォルトの名無しさん
2007/09/12(水) 02:28:24/* Tempering */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
/* 逆変換 */
y ^= y >> 18;
y ^= y << 15 & 0xefc60000UL & (1L << 15*2) - 1;
y ^= y << 15 & 0xefc60000UL & - (1L << 15*2);
y ^= y << 7 & 0x9d2c5680UL & (1L << 7*2) - 1;
y ^= y << 7 & 0x9d2c5680UL & - (1L << 7*2) & (1L << 7*3) - 1;
y ^= y << 7 & 0x9d2c5680UL & - (1L << 7*3) & (1L << 7*4) - 1;
y ^= y << 7 & 0x9d2c5680UL & - (1L << 7*4);
y ^= y >> 11 & - (1L << (32 - 11*2));
y ^= y >> 11 & (1L << (32 - 11*2)) - 1;
0846・∀・)っ━━━┓
2007/09/12(水) 02:30:570847デフォルトの名無しさん
2007/09/12(水) 06:26:54なに言ってんだ、おまえ?
>例えば、最初の600個が一致して、601個目が一致しない例を示せばいい。
こんなことを言ってたのはお前自身だぞ、アホかw
0848デフォルトの名無しさん
2007/09/12(水) 06:40:19>>816-818を見てちょっと安心したんだろうな。
0849デフォルトの名無しさん
2007/09/12(水) 06:59:01>だからindexと最低限の出力系列(各素数の和)が得られれば、逆算ができるわけだ。
>>816-818 のコードで1000000とか指定して1000001個目を予測してみてw
逆算できるんだろ?1000000もあれば十分すぎるだろ?
0850デフォルトの名無しさん
2007/09/12(水) 07:46:31>index_maskとindexの組み合わせを同時に変えていいなら、そりゃ簡単に一部が一致する系列を作れる。index_mask^indexが同じ範囲は同じになるからな。
だからになにがいけないんだ?
どのみちそれは prime spiral の初期状態として存在するパターンだろ?
0851デフォルトの名無しさん
2007/09/12(水) 08:03:140852デフォルトの名無しさん
2007/09/12(水) 08:21:25あっちの乱数スレは落ちてるみたいだが
0853デフォルトの名無しさん
2007/09/12(水) 08:32:39> どのみちそれは prime spiral の初期状態として存在するパターンだろ?
agree
ただ暗号の評価基準として「ある程度の長さの出力を見たときに、その内部状態が
ユニークに特定できる」というのは、かなり珍しい気がする。完全に特定できなくとも
範囲を絞り込めるなら、それで十分に辛い。
あとほかの品質基準として分布の良し悪しとかもあるんだが、その辺は統計的に
どうなんだろうな。独立性検定とかやってみた?
0854デフォルトの名無しさん
2007/09/12(水) 08:52:590855デフォルトの名無しさん
2007/09/12(水) 09:50:270856デフォルトの名無しさん
2007/09/12(水) 10:20:33最初というのはindexで0からという意味だった。
書き方が足りないのは悪かった。
0857デフォルトの名無しさん
2007/09/12(水) 10:26:01indexが0から始まるとう前提でOK?
0858デフォルトの名無しさん
2007/09/12(水) 10:33:08最低限の出力系列で、全パターンに出現する値がわかってしまうから。
indexが不明なら、順番まではわからないかもしれないが、何が2回以上出て、
何が全く出ないかは、簡単にわかってしまう。indexが確定すれば、全部が分かる。
どういうことかというと、相関性が非常に高いってことだ。
0859デフォルトの名無しさん
2007/09/12(水) 10:36:29実際のところ、出ない値が確定した時点で、乱数とはもはや呼べない。
0860デフォルトの名無しさん
2007/09/12(水) 10:47:480861デフォルトの名無しさん
2007/09/12(水) 10:48:43理由になってないし、順番がシャッフルされている状態で本当に特定できるのか?
0862デフォルトの名無しさん
2007/09/12(水) 11:04:450863デフォルトの名無しさん
2007/09/12(水) 11:14:45indexとindex_maskが、系列の入れ替えだけで、分布を変えているわけではないことはわかるよな?
次に考えることは、index_mask=0で、indexが0から始まる場合。
この系列が、indexとindex_maskのあらゆる組み合わせの入れ替えと同じということから
分布だけに関しては、index_maskがないアルゴリズムに置き換えることができる。
あとは未知数(素数の和)の数の出力から連立方程式を解けばわかる。
0864デフォルトの名無しさん
2007/09/12(水) 11:52:360865デフォルトの名無しさん
2007/09/12(水) 12:04:17多くのものは、特定するまでに必要な情報量の差があり、
また、アルゴリズムの種類によっては、特定できないものもある。ググればわかると思うが。
0866デフォルトの名無しさん
2007/09/12(水) 18:19:450867デフォルトの名無しさん
2007/09/12(水) 20:42:480868デフォルトの名無しさん
2007/09/13(木) 01:51:33ワラタ
0869デフォルトの名無しさん
2007/09/13(木) 06:00:590870デフォルトの名無しさん
2007/09/13(木) 12:07:02それって種の一部が分かればってことだろ?
出力だけから分かるってのと種の一部も必要ってのじゃ次元の違う話だ。
いくらなんでも見苦しすぎw
0871デフォルトの名無しさん
2007/09/13(木) 12:41:400872デフォルトの名無しさん
2007/09/13(木) 12:44:25インデックスの初期値にシードを使っていたのは盲点だった。
そこは俺が悪いから謝る。俺は作者と違い、自分の間違いは認めるからな。
でも、目的は俺の評価ではなくprime spiralの評価であることを忘れてもらったら困る。
で、今回、
最低限の出力系列で、全パターンに出現する値がわかってしまうこと。
出ない値が確定した時点で、乱数とはもはや呼べない。
という問題点が明らかになったと思うが、そのことについてはどう思うの?
また、
MTが駄目って話が全くでなくなったけど、撤回するの?
とも言われているが、こういう都合の悪い点は見ないのか?
0873デフォルトの名無しさん
2007/09/13(木) 12:56:26出力以前に周期が短すぎて話にならん。
素数で割ってるから周期を伸ばすのにとんでもなく苦労するぞ。
次元分布がどうこう言ってたがn次元で均等分布するためには
最低でもnビットの状態空間が必要だからな。
0874デフォルトの名無しさん
2007/09/13(木) 13:48:54>>870が作者かどうかに疑問を感じるのだが
0875デフォルトの名無しさん
2007/09/13(木) 13:59:22どっちでもいいだろ?
もうこんなぐだぐだな話、どっか他所でやれば?
0876デフォルトの名無しさん
2007/09/13(木) 14:05:08別に他に話すネタがあるわけじゃないし、ぐだぐだでも誰も困らんだろ。作者以外はw
他にまともな議論があって、それが阻害されているのでないなら、続けて問題なし。
0877デフォルトの名無しさん
2007/09/13(木) 14:24:46見たくないなら見なくてもいいんだよ?
0878デフォルトの名無しさん
2007/09/13(木) 16:43:200879デフォルトの名無しさん
2007/09/13(木) 22:26:330880デフォルトの名無しさん
2007/09/14(金) 10:03:370881デフォルトの名無しさん
2007/09/14(金) 14:05:140882デフォルトの名無しさん
2007/09/14(金) 14:24:19記述するようなシトとよく対話する気になるな・・・
ネットウォッチ板のネタじゃないのかこれは。
0883デフォルトの名無しさん
2007/09/14(金) 15:24:20マジメな乱数アルゴリズム。
周期2^521-1で16次元に均等分布します。
class MLS521
{
private:
unsigned long st[ 16 ], x, y, p;
public:
MLS521( unsigned long seed ) {
x = 0x41C64E6D * seed + 0x3039, p = 0, y = 0;
for (unsigned long i=0, s=x, t=~x, u; i<16; i++) {
u = t, t = s, s = ( u << 1 ) ^ ( t >> 31 );
st[ i ] = s ^= ( u << 6 ) ^ ( t >> 26 );
}
for (unsigned long i=1; i<16; i++) {
y ^= st[ i ];
y = ( y << 2 ) ^ ( y >> 30 );
y ^= y >> 12;
}
y ^= x;
}
unsigned long next( void ) {
unsigned long r = y, s = r ^ ( r >> 21 );
unsigned long u = st[ p ], v = st[ ( p + 1 ) & 15 ];
st[ p ] = x, ++p &= 15;
x ^= ( u << 23 ) ^ ( v >> 9 );
r = ( r << 2 ) ^ ( r >> 30 );
y = r ^ ( r >> 12 ) ^ x ^ v;
return s ^ ( s << 6 ) ^ ( s << 13 );
}
};
0884デフォルトの名無しさん
2007/09/14(金) 15:28:37その割には、MTがダメというのを取り下げていないし、サイトもそのままだし、
prime spiralの問題点も認めようとしないね。
0885デフォルトの名無しさん
2007/09/14(金) 15:44:530886デフォルトの名無しさん
2007/09/14(金) 16:02:100887デフォルトの名無しさん
2007/09/14(金) 19:15:11x と y も状態空間なのかな?
どっちか片方だけ状態空間で十分のような気がするが。
ソースだけざっと見ても周期はわかんないけど、
2ベキ長の配列に変数を合わせてメルセンヌ指数ビットの状態空間を
実現しつつインデックスの更新を高速にしているのはわかった。
そこに工夫がある。
少なくともprimeなんちゃらよりはずっといい。
0888デフォルトの名無しさん
2007/09/15(土) 00:51:04XorShiftに似てるね。
というか>>18の変数が4個なのを16個に拡大したような感じなのかな。
こういうのって周期は変数を減らして増やしていけば予想できそうなんだけど
均等分布、というのはどうやって分かるの?
0889デフォルトの名無しさん
2007/09/15(土) 17:41:13なんかこのスレってバカが多いみたいだし
0890デフォルトの名無しさん
2007/09/15(土) 17:48:570891デフォルトの名無しさん
2007/09/15(土) 20:16:470892デフォルトの名無しさん
2007/09/15(土) 21:05:07見ていると思うよ。作者ほどのバカもいなかったと思うけど。
0893デフォルトの名無しさん
2007/09/15(土) 21:52:230894デフォルトの名無しさん
2007/09/17(月) 09:44:01mt19937ar.cは初期状態を線形合同法(の変形?)で与えていて、
>>38なんかにあるように「初期化が悪い」と言われていますが、
実際のところどうなんでしょう。根拠のある情報を見つけられないでいます。
SFMTやWELLの論文は、MT19937の0超過状態からの回復が遅いことを指摘してます
(実装ではなくMT19937のアルゴリズム・パラメータに対する指摘)。
が、mt19937ar.cでの初期状態は0超過ではないようで、
これらの論文はmt19937ar.cの初期化が悪いことを示してはいないようです。
0-1の出現確率については問題がないけど、別のどこかの分布が悪く、
それが解消されるまで結構時間がかかるとか、そういう話なんでしょうか。
当方計算機屋なんで数学はサパーリでして...
0895デフォルトの名無しさん
2007/09/17(月) 10:55:57mt19937ar.cは初期化問題に対応したバージョンだから問題ないそうだ。
その前のコードは見たことないから分からんが。
>SFMTやWELLの論文は、MT19937の0超過状態からの回復が遅いことを指摘してます
こりゃ全くその通り。
三項式だし、マトリックスの掛け方の都合でそうなる。
でも現実的には超長周期だから意図的な初期ベクトルを与えない限りは
0超過の状態は出ない。
mt19937ar.cに関しては普通に使う限りは問題は全くないよ。
0896デフォルトの名無しさん
2007/09/17(月) 11:09:27これが笑える(笑えない)ことに、
「アセンブラでMT高速化しますた!」
みたいな第三者のライブラリでたまに古い初期化コードが残ってたりするんだわ。
最適化MTライブラリを使うなら、おとなしくSFMT使え。
0898デフォルトの名無しさん
2007/09/18(火) 13:28:04作者から反応がないようなので、そろそろMLへの突入と、スレ立てを実行する。
0899デフォルトの名無しさん
2007/09/18(火) 13:45:19wktk
0900デフォルトの名無しさん
2007/09/18(火) 17:33:15MLは入りたくないから内容ここで晒して欲しい
0901デフォルトの名無しさん
2007/09/18(火) 17:43:010902デフォルトの名無しさん
2007/09/18(火) 17:50:42心配するなw両方で晒すからw
0903デフォルトの名無しさん
2007/09/18(火) 21:00:590904デフォルトの名無しさん
2007/09/18(火) 21:37:160905デフォルトの名無しさん
2007/09/18(火) 22:39:24今のうちさっさと祭り専用スレたててくれ>>898
0906デフォルトの名無しさん
2007/09/18(火) 22:53:55反応してくれることに期待
0907デフォルトの名無しさん
2007/09/22(土) 15:31:520908デフォルトの名無しさん
2007/09/22(土) 22:07:440909デフォルトの名無しさん
2007/09/22(土) 22:10:340910デフォルトの名無しさん
2007/09/25(火) 17:25:29一様乱数から正しくNの剰余を求める場合は
RAND_MAXからのNの剰余以下の数字は棄却しましょう。
unsigned int rand0toNminus1( unsigned int n )
{
unsigned int m, r;
if ( n == 0 ) return 0;
m = RAND_MAX % n;
do {
r = rand();
} while ( r <= m ) ;
return r % n;
}
0911デフォルトの名無しさん
2007/09/25(火) 17:38:460912デフォルトの名無しさん
2007/09/25(火) 18:00:21どうすればいいの?
0913デフォルトの名無しさん
2007/09/25(火) 21:32:44n=3のときを考えればどこを修正すればいいかわかるな
unsigned int rand0toNminus1( unsigned int n )
{
unsigned int m, r;
if ( n == 0 ) return 0;
m = RAND_MAX - RAND_MAX % n;
do
{
r = rand();
} while ( r <= m ) ;
return r % n;
}
0914デフォルトの名無しさん
2007/09/25(火) 22:08:27え?
RAND_MAXから剰余を引いても結果は同じだと思いますが。
今、仮にRAND_MAXが255でNが10だとした時に、
0-255が均等に1回ずつ出現したとした場合、
m=0-5が26回、m=6-9が25回出てしまうので
r=0-5の場合はやり直しにしようという考えなのですが…
こうするとm=0-9が均等に25回ずつ出ますよね?
0915デフォルトの名無しさん
2007/09/25(火) 22:18:56ちょっと考え直してみます。
0916デフォルトの名無しさん
2007/09/25(火) 22:19:20m = RAND_MAX % n;//nが小さいとき、ここでmの値が小さくなるのでまずい(計算量がO(RAND_MAX / n))
m = RAND_MAX - RAND_MAX % n//こちらだとnが小さくても、大きくても大丈夫(計算量は定数オーダー)
0917デフォルトの名無しさん
2007/09/25(火) 22:20:03ちょwループ回数多すぎw
0918デフォルトの名無しさん
2007/09/25(火) 22:22:58本当だ。不等号勘違いしてたやw
913は無視してくれ
0919デフォルトの名無しさん
2007/09/25(火) 22:28:09{
unsigned int m, r;
if ( n == 0 ) return 0;
m = ( RAND_MAX % n ) * n;
do {
r = rand();
} while ( r >= m ) ;
return r % n;
}
これでいいですか?
これなら間違いないですよね。
なんか眠くて頭が回らなくなってきました。
0920デフォルトの名無しさん
2007/09/25(火) 22:29:32m = ( RAND_MAX / n ) * n;
ですね。
0921デフォルトの名無しさん
2007/09/25(火) 22:30:36>>911 がボケかましてるだけで元のコードのままでいいと思うんだが。
0922デフォルトの名無しさん
2007/09/25(火) 22:37:09そうですよね、間違ってないですよね。
RAND_MAXが2^n-1である必要もないですね。
最初に考えたときにRAND_MAXがいくつでも問題なかったのを忘れてました。
0923デフォルトの名無しさん
2007/09/25(火) 22:58:49unsigned int rand0toNminus1( unsigned int n )
{
unsigned int m, r;
if ( n == 0 || n > RAND_MAX ) return 0;
m = RAND_MAX % n;
do {
r = rand();
} while ( r <= m ) ;
return r % n;
}
0924デフォルトの名無しさん
2007/09/25(火) 23:30:26>if ( n == 0 || n > RAND_MAX ) return 0;
if ( n == 0 ) return 0;
if ( n > RAND_MAX ) return (unsigned int)(rand() *(double)n /(double)RAND_MAX);
とかのほうがよくね?
0925デフォルトの名無しさん
2007/09/25(火) 23:40:35確かに n == RAND_MAX も除外しないと無限ループになるけど、
n == RAND_MAX は正常な値を返すべき値域だろ。
0926デフォルトの名無しさん
2007/09/26(水) 04:56:20rand() を使うなら return r % n; はまずい。
線形合同法だと下位ビットの質が低いからだ。
>>923 は、n が 2 なら、VC++ で周期は 131072 しかない。
古いCコンパイラなら周期が 2 になることもある。
例えば、RAND_MAX が 32767 で n が 100 なら、
下のようにできるだけ上位ビットを使うべきだ。
unsigned rand0to99(void)
{
unsigned r;
for (;;) {
r = rand();
if ( r < 25600 ) return r >> 8;
if ( r < 32000 ) return ( r - 25600 ) >> 6;
if ( r < 32400 ) return ( r - 32000 ) >> 2;
if ( r < 32600 ) return ( r - 32400 ) >> 1;
if ( r < 32700 ) return r - 32600;
}
}
0927デフォルトの名無しさん
2007/09/26(水) 08:35:040928デフォルトの名無しさん
2007/09/26(水) 09:33:52線形合同法の下位ビットの周期が短いことくらい皆知ってるだろ。
どう考えても論点はそこじゃない。
つか、RAND_MAXやNを固定してどうする。
0929デフォルトの名無しさん
2007/09/27(木) 02:37:17if ( n == 0 || n == RAND_MAX + 1 ) return rand();
if ( n > RAND_MAX + 1 ) return RAND_MAX + 1;
このコードRAND_MAXが0xffffffffの場合おかしくなるんで
マクロで分けるべきかもしれません。
もう誰も見てないかな。
0930デフォルトの名無しさん
2007/09/27(木) 12:51:04rand() % n;
で、実用上ほとんど問題ないと思うんだが。
つか、おまいら、上にあげたような面倒なことしてないだろ?!
正直に吐いてごらん。
0931デフォルトの名無しさん
2007/09/27(木) 13:26:38実用上ほとんど問題ないから
0932デフォルトの名無しさん
2007/09/27(木) 18:48:22偏り関係の問題もおおむね解消されるからそれぐらいはやったほうが
いいよなぁと思いつつ、マンドクセ('A`)んで、いつもやってません。
0933デフォルトの名無しさん
2007/09/27(木) 18:56:04( ゚д゚ )
0934デフォルトの名無しさん
2007/09/27(木) 19:27:35乱数なんてrand()で95%以上問題ないし、統計的にやばそうなら
XorShiftとかで十分。はっきりいってMTなんていらんでしょ。
>>933
errno_t rand_s( unsigned int* randomValue);
rand_s 関数は、0 〜 UINT_MAX の範囲の整数の擬似乱数を入力ポインタに書き込みます。
rand_s 関数は、オペレーティング システムを使用して、暗号化によりセキュリティが強化された乱数を生成します。
乱数にまでセキュリティがいるのか。。。?
中身はなんだろ。
0935デフォルトの名無しさん
2007/09/27(木) 19:40:58説明文上は擬似乱数ってなってるけど、実質的には真性乱数じゃね?
0936デフォルトの名無しさん
2007/09/27(木) 19:59:53中身が何なのかわからないけど、
類似の API の解説を見ると乱数APIにおけるセキュリティとは
・(下手なシードの選定によるリスクを回避するため)シードはユーザ毎にOSが管理する
・シードは呼び出しプロセスのユーザイベント(キーボード、マウス操作等)その他物理的状態
も用いて更新(算出)される
・当然他のユーザのシード値は見えない
とシード推測による攻撃を無効化することとMSは考えている模様。
0937デフォルトの名無しさん
2007/09/27(木) 20:53:17C FAQの方法を使ってる
ttp://www.kouno.jp/home/c_faq/c13.html#16
0938デフォルトの名無しさん
2007/09/27(木) 21:37:51私も>937と同じ。実は、剰余を使うよりも(整数除算は整数乗算に置き換えられるため)処理速度も速い罠。
# いや、速度を求めちゃいないが。
0939デフォルトの名無しさん
2007/09/28(金) 02:53:56じゃ、なんでダメなの? 掛け算のビット幅が足りると仮定しての話だけど。
0940デフォルトの名無しさん
2007/09/28(金) 07:06:47rand() * n
ここでintを超えちゃう面倒なバグが出そうだから、>>937になってるじゃない?
0941デフォルトの名無しさん
2007/09/28(金) 08:14:25いいえ、全部につけるなんて阿呆なことをする必要はありません。
0942デフォルトの名無しさん
2007/10/01(月) 12:08:030943デフォルトの名無しさん
2007/10/02(火) 02:16:560944デフォルトの名無しさん
2007/10/02(火) 13:12:39せっかく付けるんだから意味あるとこに付けろよw
0945デフォルトの名無しさん
2007/10/02(火) 13:43:350946デフォルトの名無しさん
2007/10/02(火) 13:48:130947デフォルトの名無しさん
2007/10/02(火) 17:30:04RAND_MAX+1が0になってマズーだな
0948デフォルトの名無しさん
2007/10/03(水) 04:04:260949デフォルトの名無しさん
2007/10/03(水) 06:31:400950デフォルトの名無しさん
2007/10/07(日) 21:36:530951デフォルトの名無しさん
2007/10/07(日) 21:41:240952デフォルトの名無しさん
2007/10/08(月) 00:17:04本当にやっていいならやる。作者がちゃんと対応を取ればしない。
無視しづけるなら、明日にでも立てるわ。
0953デフォルトの名無しさん
2007/10/08(月) 01:33:14飽きた
0954デフォルトの名無しさん
2007/10/08(月) 01:40:17よろしく
0956デフォルトの名無しさん
2007/10/08(月) 01:50:16よろしく
0957デフォルトの名無しさん
2007/10/08(月) 18:22:47うだうだ言ってないで早く早くゥ
0958デフォルトの名無しさん
2007/10/09(火) 01:15:49http://pc11.2ch.net/test/read.cgi/tech/1191860116/
0959デフォルトの名無しさん
2007/10/09(火) 22:15:000960デフォルトの名無しさん
2007/10/11(木) 20:26:030961デフォルトの名無しさん
2007/10/12(金) 09:05:43そもそも黙ってやれよ……。
0962デフォルトの名無しさん
2007/10/12(金) 09:59:190963デフォルトの名無しさん
2007/10/12(金) 20:57:150964デフォルトの名無しさん
2007/10/12(金) 21:55:050965デフォルトの名無しさん
2007/10/12(金) 22:12:39やるやる言ってほとんど何もしていないじゃないか。
まず最初に非難する前に根拠を示せよ。
0966デフォルトの名無しさん
2007/10/12(金) 22:56:13もしくは独自乱数ネタを禁止する
0967デフォルトの名無しさん
2007/10/12(金) 23:10:46いならないならお前が見なければいい。俺は立てるからな。
0968デフォルトの名無しさん
2007/10/12(金) 23:11:37キミは、何の根拠を聞いているの?
0969デフォルトの名無しさん
2007/10/12(金) 23:15:500970デフォルトの名無しさん
2007/10/12(金) 23:16:07自治厨乙
0971デフォルトの名無しさん
2007/10/12(金) 23:17:42,,、,、,,, / \〇ノゝ∩ < \\1000取り合戦、いくぞゴルァ!! ,,、,、,,,
/三√ ゚Д゚) / \____________ ,,、,、,,,
/三/| ゚U゚|\ ,,、,、,,, ,,、,、,,,
,,、,、,,, U (:::::::::::) ,,、,、,,, \オーーーーーーーッ!!/
//三/|三|\ ∧_∧∧_∧ ∧_∧∧_∧∧_∧∧_∧
∪ ∪ ( ) ( ) ( ) )
,,、,、,,, ,,、,、,,, ∧_∧∧_∧∧_∧ ∧_∧∧_∧∧_∧∧_∧
,,、,、,,, ( ) ( ) ( ) (
0972デフォルトの名無しさん
2007/10/12(金) 23:18:370973デフォルトの名無しさん
2007/10/12(金) 23:58:50http://news22.2ch.net/test/read.cgi/newsplus/1192193946/
0974デフォルトの名無しさん
2007/10/13(土) 00:35:040975デフォルトの名無しさん
2007/10/13(土) 01:42:06カメと命名された種類があるらしいな。
Come hereがカメに聞こえたらしい。
0976デフォルトの名無しさん
2007/10/13(土) 07:59:270977デフォルトの名無しさん
2007/10/13(土) 10:39:040978デフォルトの名無しさん
2007/10/13(土) 11:05:490979デフォルトの名無しさん
2007/10/13(土) 16:30:27なにその文明開化
0980デフォルトの名無しさん
2007/10/15(月) 00:51:20http://news22.2ch.net/test/read.cgi/newsplus/1192193946/
0981デフォルトの名無しさん
2007/10/15(月) 03:14:120982デフォルトの名無しさん
2007/10/15(月) 08:30:400983デフォルトの名無しさん
2007/10/15(月) 09:15:21^^;
0984デフォルトの名無しさん
2007/10/15(月) 09:17:44http://news22.2ch.net/test/read.cgi/newsplus/1192193946/
0985デフォルトの名無しさん
2007/10/16(火) 15:03:280986デフォルトの名無しさん
2007/10/16(火) 22:17:200987デフォルトの名無しさん
2007/10/16(火) 22:55:45ギジラン・スー
わろた
0988デフォルトの名無しさん
2007/10/16(火) 23:54:210989デフォルトの名無しさん
2007/10/17(水) 08:36:340990デフォルトの名無しさん
2007/10/17(水) 12:53:18趣味・特技:チンチロリン
0991デフォルトの名無しさん
2007/10/17(水) 20:29:240992デフォルトの名無しさん
2007/10/17(水) 22:21:090993デフォルトの名無しさん
2007/10/17(水) 22:35:35疑似乱数2
http://pc11.2ch.net/test/read.cgi/tech/1192628099/
0994デフォルトの名無しさん
2007/10/17(水) 22:36:030995デフォルトの名無しさん
2007/10/17(水) 23:00:280996デフォルトの名無しさん
2007/10/17(水) 23:05:320997デフォルトの名無しさん
2007/10/17(水) 23:10:320998デフォルトの名無しさん
2007/10/17(水) 23:13:140999デフォルトの名無しさん
2007/10/17(水) 23:14:071000デフォルトの名無しさん
2007/10/17(水) 23:14:4510011001
Over 1000Threadもう書けないので、新しいスレッドを立ててくださいです。。。
レス数が1000を超えています。これ以上書き込みはできません。