擬似乱数

1 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:19:35 ] 擬似乱数発生器について語ろうか。 2 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:21:19 ] n * 1103515245 + 12345 mod 2147483647 3 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:26:29 ] LD A, R 4 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:35:58 ] >>2は n * 1103515245 + 12345 mod 2147483648 の間違い 5 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:39:25 ] *(char *)(0xFFBC0161) 6 名前：デフォルトの名無しさん [2006/04/27(木) 03:00:43 ] MT 7 名前：デフォルトの名無しさん [2006/04/27(木) 05:52:27 ] では手始めに、メルセンヌツイスタの荒探しの話題から頼む。 8 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 06:28:13 ] 数学板 乱数スレ science4.2ch.net/test/read.cgi/math/1126350979/ 電気電子板 【疑似】乱数をつくる【本物】 science4.2ch.net/test/read.cgi/denki/1074867250/ シミュ板 乱数 science4.2ch.net/test/read.cgi/sim/1100375806/ 9 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 14:29:10 ] ここはム板らしく、あら捜しよりも高速化とか考えた方がいいんじゃない？ 10 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 15:42:25 ] 暗号通信用に擬似乱数生成専用チップがあるようだが 11 名前：デフォルトの名無しさん [2006/04/28(金) 11:56:29 ] ではその仕組みについて講義してくれ 12 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 14:01:30 ] 擬似乱数ではないが www.toshiba.co.jp/about/press/2004_08/pr_j0901.htm www.internix.co.jp/publish/newsletter/nl85_pdf/nl85fdk.pdf www.hmi-jp.com/hmi/security/clutterbox.html 13 名前：デフォルトの名無しさん [2006/04/28(金) 18:28:56 ] >>7 アルゴリズムじゃなくて、その実装(mt19937ar.c)のアラでよければ。 MTは内部状態として624個のベクトルを持ち、そこから乱数をひねり出す。 つまりはMTは624*32=19968ビットの乱数生成器で、 その19968ビットの乱数表から32ビットずつ取り出すのがgenrand_int32()関数ということができる。 で、genrand_int32()を624回呼ぶごとに内部のベクトルを一度に「えいや」と更新するようになっている。 大量の乱数が必要な場合は並列処理が効くのでこれでよいのだが、 中程度数の乱数がリアルタイムで必要となる場合、これはいただけない。 例えばゲームでMTを使うとすると、624回乱数を生成するごとにフレーム落ちが発生、ということもありうる。 genrand_int32()を1回呼び出すごとに1つのベクトルを更新するようにすれば いつでも同じ時間で乱数が得られる。 14 名前：デフォルトの名無しさん [2006/04/28(金) 18:39:05 ] ゲーム用ライブラリとかで、mt19937.cがほとんどそのまま使われているのを見ると 「お前本当に分かっててその乱数発生器を薦めているのか？」と言いたくなる。 15 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 23:12:59 ] >>7 >では手始めに、メルセンヌツイスタの荒探しの話題から頼む。  でかい、重い。 大体、普通の用途でここまで乱数性に拘る場面はそうそうない （だから喧嘩を売られた knuth もスルーした）。 16 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 23:42:09 ] でかいは同意だが、そんな重いか？ 17 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 23:47:00 ] あーでも初期化は重いかな。ほとんどハッシュ関数だよね、あれ。 まあ周期長いから頻繁に初期化するような使い方はしないが。 18 名前：デフォルトの名無しさん [2006/04/28(金) 23:53:29 ] 軽さで言えばXorShiftとか。 unsigned 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)) ); } 19 名前：デフォルトの名無しさん [2006/04/29(土) 00:09:50 ] つか、速くてランダムなやつとなると やっぱりどれもハッシュ関数みたくなるのな。 20 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 00:10:17 ] パチンコで勝つためはどのような乱数をシミュレートすればいいのですか 21 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 00:12:53 ] 脳内乱数 22 名前：デフォルトの名無しさん [2006/04/29(土) 01:01:05 ] ゲーム用途なら、そこそこ均等に出てくれれば精度自体は8ビットぐらいでも問題ないよな。 23 名前：デフォルトの名無しさん [2006/04/29(土) 01:02:49 ] つうかMTは本家サイト自身が「モンテカルロ法シミュレーションのための擬似乱数」って言ってなかったか？ 均等な乱数が超大量に必要な場合に使う、みたいな。 24 名前：デフォルトの名無しさん [2006/04/29(土) 01:43:55 ] ここはまあまあ有意義なスレですね 25 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 04:20:02 ] ゲームで言えば、１フレームに数百から数万（雨とかパーティクル）なら線形合同法で十分だろう。 プログラマーには見えても、ユーザーには周期性は見えないよ。 １フレーム数回以下なら、必要なら重くても高品質なほうがいいんじゃない？ AI とか、 ランダムダンジョンとか。 26 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 07:30:18 ] >>18それ、まともにM系列のが 27 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 20:33:09 ] でも、正直な話、現実での MT の用途の割合なんて 　1.ゲームプログラマの自己満足の為：86% 　2.汎用のライブラリが乱数生成関数として 　MT を採用しているから、いつの間にか使っている：10% 　3.本来のシミュレーション用に使用:3% 　4.その他：1% 位だと思う。 28 名前：デフォルトの名無しさん [2006/04/30(日) 15:17:30 ] WELLについて調べようとおもったんだけど…… ぐぐっても"well"なんて単語としてありきたりすぎて 関係ないページがヒットしまくりなんだが。 作者的には「より良い」と語呂合わせしたつもりなんだろうが、 いまや情報化社会。物にはなるべく一般的な語とかぶらないような名称をつけて頂きたい。 29 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 22:18:10 ] ゲーム用で再現性無くていいなら、時間とユーザーの入力 （その時しかありえないようなPCの状態）を混ぜりゃほぼ ランダムになる。 30 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 22:23:18 ] >>29 その必要も無いのに、 テスト項目に「時間」と「ユーザーの入力」の要素が 入るような実装は、極力避けるべき。 テストの自動化が出来ない。  31 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 22:31:53 ] SSL の証明書作るときのシードにキー入力使ってたな。 32 名前：デフォルトの名無しさん mailto:sage [2006/05/03(水) 15:09:15 ] インターネットを利用したランダム関数できないかな？ 33 名前：デフォルトの名無しさん [2006/05/03(水) 18:20:08 ] >>32 パケットが通過する間隔はポアソン分布に従う、とかそういうのを利用するのか？ 34 名前：デフォルトの名無しさん mailto:sage [2006/05/03(水) 18:58:42 ] ２ちゃんねるを利用したランダム関数欲しい 35 名前：デフォルトの名無しさん [2006/05/03(水) 21:02:28 ] >>18 これ確かに早いけど、種を選ぶのが難点だね。 128ビットで、そこそこ0と1が混じってないと駄目ってのが。 種用に物理乱数とか、遅くても質のいい乱数発生器を別個に使う必要があるなあ 36 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 00:41:36 ] >>13 あと、初期化が糞だよねぇ。そのせいでかなり癖のある乱数列が生成される。理論台無し。 37 名前：デフォルトの名無しさん [2006/05/04(木) 08:02:03 ] まあ初期化ルーチンに関しては他の乱数生成関数とかハッシュ関数とか組み込めばええんでない？ xorgensでもMTでもどの擬似乱数でも言えることだけど。 38 名前：デフォルトの名無しさん [2006/05/04(木) 08:09:30 ] MTの初期化ルーチンをそのまま使うときは最初の100万個ぐらいは読み飛ばしたほうがいいらしい。 39 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 08:14:57 ] 100万の根拠は？ 40 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 08:26:44 ] 統計的としか言いようが無い。 50万とか70万とかいうデータもあるが 41 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 08:37:49 ] 正確には681,1573個だ。 42 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 08:51:13 ] 要するにマンコ 43 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 09:36:18 ] >>30 再現性がなくなるだけで、時間を加味していればテストは自動化できるだろ。 話それるがユーザー入力だって、ある程度自動化するし。 >>32>>33>34 全部ユーザー入力と一緒じゃね 44 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 10:57:54 ] >>38 はつみみなのでソースおせーて 45 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 12:31:25 ] 初期化が糞な場合、MTみたいに周期がアホみたいに長い疑似乱数はその程度 読み飛ばすだけで癖が抜けるとは思えんのだが。 46 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 12:51:05 ] >>40 その統計の在処をぜひ 47 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 14:23:52 ] じゃあみんなで初期化関数考えようぜ。 （新しい擬似乱数考えるのと同じになりそうだが） 48 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 14:37:16 ] >>47 そんなの Windows なら CryptGenRandom 、Unix系なら /dev/urandom を使う・・・てのが常識では？ 49 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 15:30:21 ] MD5だっけ？ まあ暗号用に使うんじゃなくてあくまで擬似乱数用の種だからCRCとかでもいいような希ガス 50 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 16:47:54 ] どうでもいいならシステムタイマー使えばいいし 厳密にやりたきゃ>>48の使えばいいし。 51 名前：デフォルトの名無しさん mailto:sage [2006/05/04(木) 19:56:01 ] 結局、MT 厨は、そのネームバリューを闇雲に信じるだけで、 自分で乱数性の検証はしていなかったんだな。 52 名前：デフォルトの名無しさん mailto:sage [2006/05/05(金) 18:18:49 ] >>51 当たり前だろｗ 偉い人が使えるって言えば使うだけ 53 名前：デフォルトの名無しさん mailto:sage [2006/05/05(金) 18:25:54 ] Ｍ系列乱数と、線形合同法の結果をXORして使えば Ｍ系列が2^127-1の周期で線形合同法が2^32の周期だから　合成周期は掛け算でいいんだよな？ 54 名前：デフォルトの名無しさん mailto:sage [2006/05/05(金) 19:59:17 ] >>51 それが厨の厨たる所以。 >>53 ヒント 指数は掛け算が足し算。 つまり合成周期は2^159弱ってこった。 55 名前：デフォルトの名無しさん mailto:sage [2006/05/05(金) 20:47:20 ] Ｍ系列乱数と、線形合同法の結果をXORした場合、 簡単に種を見つけるアルゴリズムはあるのだろうか？ 56 名前：デフォルトの名無しさん mailto:sage [2006/05/06(土) 15:07:25 ] 総当たりが一番簡単だ。 57 名前：デフォルトの名無しさん [2006/05/06(土) 18:27:20 ] >>55の言う「簡単」はそういう意味じゃないと思われ 58 名前：デフォルトの名無しさん mailto:sage [2006/05/06(土) 19:05:50 ] もし総当りしかないのなら暗号に使えないかな 59 名前：デフォルトの名無しさん [2006/05/06(土) 19:51:45 ] ワンタイムパッドとしてなら 60 名前：SOURCE ◆tAo.kQ2STk mailto:sage [2006/05/06(土) 20:53:53 ] >>55 両方の式を満たすような特殊な式があればいくらでも出来そうなｷｶﾞｽ。 線形合同法は離散対数とかの扱いが面倒だが？ >>56 総当りすればいつかは解けるけどさ、現実的な時間内で2^159弱ある鍵空間を全て試せるのか？ 2^159≒10^47*7.3 一秒間に10^39回強のスピードで当たれるとして23年ほどかかるぞよ。 >>58 それは正しいけど、総当り以外に破る方法が存在しない事を証明する事は難しいとオモフ。 61 名前：デフォルトの名無しさん mailto:sage [2006/05/07(日) 12:15:43 ] 証明されてなくても多分大丈夫だろうって使われてるのはあるな 62 名前：デフォルトの名無しさん mailto:sage [2006/05/07(日) 13:19:27 ] 証明できるくらいまで研究が進む頃には、 総当たりで簡単に種を探せるようなスペックのマシンが動いている気がする。 63 名前：デフォルトの名無しさん mailto:sage [2006/05/07(日) 13:38:43 ] >>62 光の速度を考えると、本当にそんなマシンが出来ると思う？ 64 名前：デフォルトの名無しさん mailto:sage [2006/05/07(日) 14:34:54 ] 量子論的重ねあわせがどうこう 65 名前：デフォルトの名無しさん mailto:sage [2006/05/07(日) 14:44:58 ] >>64 この場合、全部の組み合わせを検索しなければならないのだとしたら まず全部の組み合わせをどこかに入れておく必要があるんじゃないの？ そうすると物理的に不可能でしょ 66 名前：デフォルトの名無しさん mailto:sage [2006/05/09(火) 00:29:21 ] >>10 半導体中の熱電子の揺らぎを使った、 熱的乱数発生モジュールを売っているベンチャーもある。 もう数年前の話だけど。 67 名前：デフォルトの名無しさん mailto:sage [2006/05/11(木) 00:56:09 ] >>65 一つの量子に複数の状態を重ね合わせることが出来るので 理論上はあらゆる組み合わせを一箇所に保管できるようになる。 現在の技術では4状態で実験に成功したそうだｗ 先は長い…… 68 名前：1つ、二つ、おっぱい。 mailto:sage [2006/05/11(木) 22:14:09 ] > 一つの量子に複数の状態を重ね合わせることが出来るので 　〜〜〜〜〜〜〜〜 > 理論上はあらゆる組み合わせを一箇所に保管できるようになる。 　　　　　　　〜〜〜〜〜〜〜〜〜〜〜〜〜　 後半ダウト。 「複数＝あらゆる」って、おまいは大きな数を数えられない未開人ですか？ 69 名前：デフォルトの名無しさん mailto:sage [2006/05/12(金) 04:36:31 ] 別に間違っていないが。 70 名前：デフォルトの名無しさん mailto:sage [2006/05/13(土) 10:13:33 ] また開き直りか。 71 名前：デフォルトの名無しさん mailto:sage [2006/05/14(日) 08:48:58 ] 考える問題において可能なあらゆる状態数がＮのとき 一個の量子ビットにＮ個の状態を重ね合わせる量子アルゴリズムを使うなら 別におかしくないね 72 名前：デフォルトの名無しさん mailto:sage [2006/05/14(日) 10:29:03 ] 言い訳乙ｗ 頭悪すぎ 73 名前：デフォルトの名無しさん [2006/05/14(日) 10:34:05 ] おまぃの「理論」とやらでは、 量子と周囲とのインタラクションを完全遮断して、 かつ、その量子に任意個数の状態を保持可能なのかｗｗｗ ずいぶん貧弱な理論だなｗｗｗ想像力が足りないというかｗｗｗ基礎知識がない素人の発言は怖いというかｗｗｗ 74 名前：デフォルトの名無しさん mailto:sage [2006/05/14(日) 10:48:20 ] というより　 検索が高速だとしても、 1万なら1万通りの状態を一瞬で作る方法があるのか？ あるなら、既にその問題は解けてるわけじゃないのか？ 75 名前：71 [2006/05/14(日) 11:07:33 ] >>67でも>>69でもないですが、おいらはShorの素因数分解アルゴリズムのことを言ったんだけど ＞かつ、その量子に任意個数の状態を保持可能なのか 一体何の話？ 76 名前：71 mailto:sage [2006/05/14(日) 11:09:49 ] あ、>>62からの流れだったんですね すいません 77 名前：デフォルトの名無しさん [2006/05/14(日) 11:23:40 ] ＞考える問題において可能なあらゆる状態数がＮのとき ＞一個の量子ビットにＮ個の状態を重ね合わせる とか言ってる時点で素人モロバレ 78 名前：71 mailto:sage [2006/05/14(日) 11:31:16 ] >>77 あ、ほんとだ 一個のqubitに格納する状態の数はＮ個じゃなかった うろ覚えですいません 79 名前：デフォルトの名無しさん [2006/05/14(日) 17:12:03 ] >>66 それって周囲の温度によって乱数変わったりしない？ 80 名前：デフォルトの名無しさん [2006/05/14(日) 17:13:20 ] アメリカの暗号乱数発生チップには諜報機関の権限でバックドアが仕掛けられているという話だが… 81 名前：デフォルトの名無しさん mailto:sage [2006/05/14(日) 18:25:00 ] >>18これって普通にソースに組み込んで使ってもライセンスの問題無い？ 82 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 05:54:12 ] unsigned 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)) ); } x 11101011011 1100110100010101 y 10101100110100101010111100101 z 11111000100100011101110110101 w 10101001 0010001001100110011 tの初期値が種？ 83 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 07:51:37 ] >>82 よく見ろ、t の初期値は使われてないぞ。 84 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 08:14:36 ] unsigned long 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( w=(w^(w>>7))^(t^(t>>5)) ); } こんなのでもいいの？ 種(xyzw)の選び方やシフトするbit数の根拠がよう解らんのですわ。 85 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 12:12:56 ] ここには乱数に詳しい人はいない件 86 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 14:33:23 ] 飯の種だし こんなところにタダで書くわけにも 87 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 22:17:00 ] >>18 乱数全然わからんけど、 y,zはただのキャリアーでx,wの上下32bitを使うのね。 中間の64bitは使わなくてもいいの？ その方が出力が読みにくかったりする？ 88 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 05:19:45 ] そんな単純な問題じゃない 89 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 06:36:50 ] >>87 よく見れ、種として機能している。 90 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 17:02:00 ] 擬似乱数の種を得る方法には時刻以外にどんなものがある？ 91 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 18:20:51 ] 未初期化変数のゴミ値 92 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 20:48:26 ] マウスカーソルの座標 93 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 20:51:13 ] 俺の場合、セキュリティ関係の用途じゃない時のデフォは[時刻＋プロセスID]。 セキュリティ関係の用途の時には >>48 。 94 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 21:32:34 ] サウンドカードからの入力(ノイズ)値 95 名前：デフォルトの名無しさん [2006/05/17(水) 22:47:54 ] >>94 俺DTMやっててフルデジタル環境なのでサウンド入力は常時0になりますが…… もしかして俺の環境だとうまく乱数吐かないソフトあるんかな？ 96 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 23:28:26 ] >>91 それ、ほとんど毎回同じになるだろ。 97 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 00:42:15 ] 連続起動時間 CPU稼働率 メモリ使用率 メモリキャッシュ量 HD容量+使用率 98 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 01:46:47 ] 素直に>>48使おうよ… 99 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 17:28:17 ] CryptGenRandomは失敗する環境があるから 100 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 17:35:53 ] １００ 101 名前：デフォルトの名無しさん [2006/05/18(木) 18:28:39 ] >>94 そういやファミコンはアナログ信号ピンがあってカートリッジ側でそいつを読めたんだっけ？ それを乱数に使ったゲームは知らないが。 102 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 20:56:02 ] >>99 MSが標準で提供してるサービスプロバイダを選んでちゃんとした初期化をすれば、失敗する環境なんてないだろ？ ...俺も、以前はヘタレなコードを書いて環境よっては失敗するからなんでだろう？ と悩んでたけど初期化コードの問題だったぞ。(状態によって初期化方法を変える必要がある。) 103 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 21:01:00 ] >>90 そういえば、Z80のアセンブラとかではリフレッシュレジスタ(※)の値を利用するなんて話もあったなぁ。 ※昔のメモリシステムの名残で、メモリの内容が揮発しないように定期的にリフレッシュするのに 　使われたレジスタ。どこのメモリブロックをリフレッシュするべきかを指し示して高速にその値が循環する。 104 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 21:04:34 ] >>103 >>3 105 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 21:05:41 ] >>103 連続起動時間とそうたいして変わらんと思う 106 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 21:14:18 ] たしか3ビットだか4ビットぐらいしかなかったような気がする＞リフレッシュレジスタ 107 名前：デフォルトの名無しさん mailto:sage [2006/05/18(木) 23:11:51 ] >>106 7ビットだよ。 しかし互換CPUでは全く変化しないこともある罠。 108 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 18:47:53 ] ところで、乱数性を評価する方の話はどうなのよ csrc.nist.gov/rng/ とかさ 109 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 19:38:12 ] >>108 俺は乱数を自作したりその乱数性を評価するときにはその評価対象の乱数である程度のサイズの 乱数列を生成しそれをそのままファイルとして保存し、ファイルの圧縮プログラムを使ってその結果 の圧縮率が悪いほどエントロピーが高い良い乱数として評価してる。俺的にはこの方法はお手軽で 且つかなり有効なテストの方法だと思ってるんだけど、ちょっと他人の意見を聞いてみたい。 所謂「後出し」にならないように付け加えておくと、俺はこの評価方法は飽くまでエントロピーの高さを 計るものであって真性乱数性を計るものではないと自覚している。真性乱数性はその特性上 (まともな)評価方法は存在しないものと思ってる。( だって、ずっと同じ値を吐き続けたって真性乱数 の場合はアリってされるんだから、そんなもん評価のしようがない。 ) ちなみに俺はこのスレでMTに癖があるって言い出したヤツだけど、 それはこの方法による評価でMTで生成した乱数列の圧縮率がよかったから。 110 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 21:36:02 ] おいおい、エントロピーが高いってことはその範囲でのビットの出現回数に 偏りがないって事だろ。 MTほどの長い周期であれば部分的に偏りが生じる区間があるのは当然じゃない。 重要なのはその区間から次の区間を予測できないことな訳だ。 むしろ、いつどの区間を見ても偏りがないのなら短い周期しかもっていないことになる。 高々数MB、数GB程度のサイズじゃ乱数性は測れないよ。 試しに普通の線形合同法で乱数を生成してみれば分かる。 普通に圧縮できないから。 下位ビットは使うなよ。 111 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 21:48:45 ] >>110 おまい、ちゃんとわかってる？　ちゃんと実測した？ 俺はMTの理論に問題があるなんて言ってない。初期化が糞だって言っただけ。 MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、 線形合同法なんかだと下位ビット捨てても圧縮率はいいぞ。 112 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 21:50:44 ] >>111 > MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、 それって、 MT には何にも問題ないってことだよな？ 113 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 22:20:49 ] 圧縮についてなんか知っててそんなこと言ってるのか？ 圧縮ソフトが何やってるのか調べた方がいいぞ。 114 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 22:26:01 ] >>112 そだよ。だけど、極端な話すると100万回やっても同じ値を吐き続けるとってもあほみたいに周期の長い乱数と 100万回で一週しちゃうんだけどその間のエントロピーは文句なしの乱数のどっちが実用的だと思う？ 少なくともあの実装のMTではモンテカルロ法に利用すんのも止めといたほうがいいぞ。 115 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 22:27:42 ] >>113 そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。 だからこそ、他人の意見を聞きたい。 116 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 08:53:55 ] 辞書サイズよりも大きい周期で同じデータを吐き出しても圧縮率は変化しないよね 117 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 09:25:46 ] >>116 にも関わらず、MTや線形合同法では圧縮率がいいんですよ。 てか、他の優れた評価方法とかないの？ 俺も多少は乱数性の評価方法とか調べたけどあまりにもしょぼいしのか見つからなくてよー たとえ例えハックにも過ぎなくても、これじゃ圧縮を利用したほうが断然いいじゃん・・・て、今んとこ結論してるわけよ。 118 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 10:49:31 ] >>111 >おまい、ちゃんとわかってる？　ちゃんと実測した？ 実測データｷﾎﾞﾝﾇ 119 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 14:52:24 ] >>118 俺も記録をちゃんと残してたわけじゃないから、精確な情報じゃないけど 数十MB規模のデータでMTの場合、だいたい圧縮率が90%代後半で 線形合同法だと圧縮率が80%代後半だった。 ちなみに俺が自作したヤツやMTでも初期化をちゃんとしたヤツだと 圧縮率は100±1%ぐらいだった。 ↑これは記憶を元に書いたんで多少間違ってるかもしれん。 精確なデータが欲しかったら自分で実測すれ。 あと俺が試した圧縮アルゴリズムはLZHとZIP。この二つはアルゴリズムが かなり似てるから本当はもっといろんなアルゴリズムで比較したほうが いいんだろうけど俺はそこまではやってない。 # 当然だけど、LZHとZIPではほとんど圧縮率に差がでなかった。 120 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 15:33:55 ] 他の圧縮やってみたら全然結果が違ったらどうする。 121 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 15:39:52 ] >>120 別にどうもしないけど。圧縮アルゴリズムが違えば結果も異なるのは当たり前。 しいて言うなら評価をする為の圧縮アルゴリズムのひとつとして採用するだけ。 122 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 15:44:50 ] てか、ちゃんとした知識を持ってて、理論に基づいてどーこー言えるヤツはおらんのか？ 俺自身も知識よりは閃きの人間だから、知識のないヤツは黙ってろとかは思わないが、 できれば知識を持ってる人間の意見を聞きたい。 123 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 15:53:05 ] 断る 124 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 15:58:02 ] >>123 そんなこと言わないで、頼むよ〜 125 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 17:11:27 ] 1,2,3,・・・というデータはハフマン圧縮ではまったく圧縮できないがランダム性はない 126 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 17:32:09 ] >>125 そこまでテキトーなこと抜かすなよ。 ちょっとバイナリでの表現がどうなるか考えりゃ、圧縮できることぐらいわかんだろ。 せめてもうちゃっと考えてから書き込んでくれ、な？ 127 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 17:51:37 ] >>126 いや循環し続けるデータなら　ハフマンでは圧縮出来ないのは正しいだろ ただ、差分をとれば途端に圧縮出来るのだが 128 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 17:58:04 ] まずはランダム性を定義しろ 129 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 18:30:55 ] >>127 理論ベースで言えば確かに >>125 が言わんとすることもわからんでもないが 実装ベースで考えれば >>125 の言う理論は途端に破綻する。 >>125 があげたようなデータを 8bit 表記にすればたかだか256バイトで循環するデータになるし 32bit 表記にすれば上位bitが圧縮可能なデータ群と可す。 が、bit幅可変長表記にすれば、確かに少なくともbit幅固定表記に比べ圧縮し難いデータには なるだろう。しかし、それはランダム性がないデータと言えるか？　これをランダム性のないデータ だと言うヤツがいても、俺はそれを否定しないが、これがランダム性のないデータとするならあら ゆる疑似乱数もランダム性がないものと評価するべきだろう。 >>128 ランダム性の定義ではないが、 圧縮アルゴリズムによる評価目的はエントロピーの高さを測ること。 130 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 18:37:41 ] >>125 付け加えておくと、それはもっとも簡単な疑似乱数列だぞ。 131 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 18:43:47 ] >>129 1,2,3,・・・,2^32までのデータを使えば32bit表記では各ビットパターンは一回ずつ登場する事になるぞ 132 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 19:15:14 ] >>131 それでも圧縮は可能だろうが。 やっぱり、こんなとこでまともな意見を求めた俺がバカだったか。 こんなやりとり続けても時間の無駄だしもっと生産的なことに時間をつかうよ。じゃぁな。ﾉｼ 133 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 19:21:20 ] >>115 >そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。  それは唯のハックでは無いだろ？ むしろ、コルモゴロフの定義に忠実すぎるぐらいだ。 ちなみに俺も同じ方法で別のものを評価していたりする。 それはソースコード。 圧縮率が高いコードは間違いなく糞コードだったりする。 圧縮後のファイルサイズは、いわゆるステップ数なんかよりも、 ずっとよい指標になる。 134 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 19:30:37 ] >>133 基準はどれぐらい？ テキストなんでだいたい 20% ぐらいになるのも普通かと思うんだが。 135 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 19:36:20 ] ところで、折角 >>108 が NIST の乱数検定器を挙げているのに その実行結果について議論をするどころか、 >>117 >てか、他の優れた評価方法とかないの？  >俺も多少は乱数性の評価方法とか調べたけどあまりにもしょぼいしのか見つからなくてよー  とかぬかしている件について、どうよ？ 136 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 19:41:20 ] >>134 むしろ圧縮後のサイズがポイントだな。 圧縮した後のファイルサイズで、 「このアプリは、この程度の規模の複雑さを持っているんだな」 ってのが、意外に分かると思う。 137 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 20:01:01 ] >>132 圧縮云々を言うならせめて情報理論ぐらい勉強しろよ・・・ 138 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 20:06:51 ] >>136 コメントに日記が書かれていても複雑なプログラムなのかw 139 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 20:33:04 ] >138 で？何？ 140 名前：デフォルトの名無しさん mailto:sage [2006/05/21(日) 21:38:44 ] バカばっか 141 名前：デフォルトの名無しさん [2006/05/22(月) 00:21:49 ] データ列を圧縮してその圧縮率がどう、ってのはシャノン情報量を見てるんだよね？ >>114 >そだよ。だけど、極端な話すると100万回やっても同じ値を吐き続けるとってもあほみたいに周期の長い乱数と >100万回で一週しちゃうんだけどその間のエントロピーは文句なしの乱数のどっちが実用的だと思う？ 確かに。 「100万ビットでも同じ値が続いてくれることがありえないと困る」ような乱数の使用法をしてるか否か、ってことだよね。 ゲーム用途なら下位ビットが最悪のrand()の方が人間相手には『確実にランダムっぽく』見える分有利かもしれないな。 でもそれはつまるところ、人間の持つ「ランダムさ」の感覚が シャノン情報量の大小と一致していないところに問題があるわけだよね。 だから、マジで何万回も同じ値が出続けるかもしれないサイコロ振りより、例えばM系列の方が喜ばれたりする。 難しいねえ。 142 名前：・∀・）っ-○◎● ◆toBASh.... [2006/05/22(月) 00:31:35 BE:752619896-#] １００万回同じ値を吐くという状況を再現できんのだが、何が問題なのかサパーリ 俺はboost::random::mt19937使ってる 143 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 00:37:45 ] >>142 そりゃー32bitの乱数なら100万回同じ値になる確率は1/((2^32)^999999)なんだから そうそう簡単に再現されるわけ無いじゃん。 144 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 00:39:24 ] で、そうそう再現されない状況なんだから、 「はじめっからそんな値を吐かないアルゴリズムでも問題ないよな？」 という考え方で、もっと短周期の乱数アルゴリズムが『実用的』とみなされている。 ってこと。 145 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 00:42:00 ] boostのMTはあんまり速度でなかったと思われ。 同じ使うにしても本家サイトで公開されてる「高速化版」に差し替えた方がいいかも。 （乱数生成アルゴリズムを入れ替えできて、同じインターフェースを提供、ってのがboostのいいところだしな） 146 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 00:43:17 ] 池沼としか思えんｗ 147 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 00:46:42 ] いけぬまで悪かったな！ これでも頑張って勉強中の身なんだ…… 148 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 04:08:13 ] このスレ見てて思ったんだが、乱数がどういうものかっていう理解度が人によってかなりまちまちなんだけど、 理解度が低い側の人が自分自身の理解度が低いということすらが自覚してなさげだね。 最低限↓このページの最初に書かれていることぐらいは理解したうえで議論すべきだと思うけど。 ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0 149 名前：デフォルトの名無しさん [2006/05/23(火) 18:43:51 ] 「ｽﾚが急激に伸びる時は大抵、池沼が書き込んでいる」 150 名前：デフォルトの名無しさん mailto:sage [2006/05/23(火) 18:45:47 ] ↓↑ └┘　そうだね 151 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 21:30:16 ] また池沼が寄ってきた 152 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 21:42:01 ] おかえり池沼くんｗ 153 名前：デフォルトの名無しさん [2006/05/31(水) 02:33:35 ] なあMTよりもうちょっと周期短くていいからベクトル数すくない乱数ないの？ 154 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 21:39:14 ] AESやtwofish 等のブロック暗号の結果を使うと、エントロピーという面では良い？ ちなみに、暗号化した結果をさらに暗号化して、次の乱数を出していくような形だと、悪い性質が出てきたりするのかな？ 155 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 22:23:43 ] それOutput-FeedBackって奴じゃん。 じゃなくって、生成器Aで作った乱数列を鍵にして生成器Bで乱数列を作る、ってこと？ 156 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 22:50:20 ] XORすべき平文はないけれど、それも OFB って言っていいのかな？ そうであれば、たしかに OFBですね。 157 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 22:52:01 ] で、結局、まともなブロック暗号であれば、エントロピー的な意味では、 悪い性質が出てきたりはしない筈…ですかね？ 158 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 00:25:28 ] >>156 全0の数列とXORして結果を得ていると考えればOFBの一種だな 159 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 00:26:39 ] >>157 その「まともな暗号」を考えるのがﾑﾂｶｼｲ 160 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 10:58:08 ] >>159 154で書いた通り、前提として、AESやtwofishを想定していますけれど。 暗号の世界の死屍累々の歴史を見れば、よほどでなければ俺様暗号を作ろうなんて傲慢な気持ちにはなれないですよね。 AES 選考のときも、ドイツテレコムが採用していた暗号が 10秒で即死したり、笑い話に事欠かない世界…怖いですね。 h2np.net/bit/aes-rep.html 161 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 13:58:02 ] >>160 ﾊｧﾊｧ 読んでて興奮するね。 162 名前：デフォルトの名無しさん mailto:sage [2006/06/03(土) 04:14:33 ] >>160 ｶｺｲｲ!! 163 名前：デフォルトの名無しさん mailto:sage [2006/06/03(土) 05:16:05 ] >>160 最終的にAESに選ばれたのはそこで名前すら挙がっていなかったRijndaelだというのも おもしろいな 164 名前：デフォルトの名無しさん [2006/06/05(月) 00:58:00 ] 高速な乱数の基本はシフトとXORを使うことらしいが この二つってそんなに演算早いの？ 加減算やローテートは遅い部類なの？ 165 名前：デフォルトの名無しさん mailto:sage [2006/06/05(月) 01:32:04 ] シフトとローテイトはCPUレベルではそんな変わらんと思うが 加減算は変わりそう 166 名前：デフォルトの名無しさん mailto:sage [2006/06/05(月) 01:42:13 ] >>164 命令自体は別に変わらないよ。 M系列でググると分かるけど、 ある周期で全てのビットが0である場合を除いて、 全ての0と1の組み合わせが出現するアルゴリズムがある。 そんでそれはシフトとxorのみで実現する事が出来るというだけ。 これはなかなか自然的な乱数の性質に近くて、 しかもコンピューターに都合のいい形をしている。 で、よく使われる。 加減算やローテートでも実現出来るんじゃないかな。 ただ、周期を大きくするのが難しそうだ。 167 名前：デフォルトの名無しさん mailto:sage [2006/06/05(月) 01:53:02 ] Pen4なら加減算が倍速でローテートはアホみたく遅い。 使用する環境が決まってるならCPUに特化した乱数ルーチンもアリだと思う。 168 名前：デフォルトの名無しさん mailto:sage [2006/06/06(火) 17:33:17 ] >>167 そのために、RCなんとかコンテストで、PowerPC とかがクロックの割に健闘したりってことがあった気が。 そういえば、CPU自体が（熱雑音とかを使った？）乱数生成器を持っているやつって、あるのかな？ 169 名前：デフォルトの名無しさん [2006/06/06(火) 22:10:12 ] >>168 ぐぐったら出てきた ttp://journal.mycom.co.jp/news/2003/01/22/15.html 170 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 10:40:12 ] こんなのも。どうやって使うのか知らないけれども。 www.intel.co.jp/jp/intel/pr/press99/991116.htm インテル 820 チップセットは〜インテル(R) ランダム・ナンバ・ジェネレータ（乱数生成器）を搭載しています。 171 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 20:49:19 ] メルセンヌ・ツイスタをSSE2で高速に計算する方法を思いついた！！ でも…… ワーキングメモリが2.5倍強ほど必要になってしまう… ただでさえデカイと評判のMTがさらにでかく… くそっ、SSEに128ビットアライメント縛りなんてものがなければ…… せめて64ビット縛りならいいのに 172 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 21:37:59 ] PCで使うなら気にするこたねぇだろ 組み込みで使うならともかく 173 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 21:46:05 ] そだね。 SSE2使おうってCPUならキャッシュで収まるもんね。 気兼ねせず実装することにしますわ。 でもアライメント縛りって本当に鬱陶しいな。スレ違い愚痴ｽﾏｿ 174 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 23:20:13 ] ま、その前提で高速演算できますって機能だから仕方ない。 組み込み系だと日常茶飯事だけどｗ 175 名前：デフォルトの名無しさん [2006/06/11(日) 14:44:38 ] 「とってもごはん」のMMX版MTって、オリジナル版と出力違ってないか？ 176 名前：デフォルトの名無しさん [2006/06/11(日) 16:49:37 ] >>171 うｐはdvi形式でおｋ 177 名前：デフォルトの名無しさん [2006/06/11(日) 17:06:53 ] >>175 オリジナルのMTも32bit版と64bit版で出力違うから気にしなくていいと思う 178 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 06:13:17 ] で、初期化がどーのこーのに難癖つけてた件は結局うやむやのうちに終了しちゃったの？ 179 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 10:48:14 ] そもそも何で乱数に初期化が必要なんだ？ 種から生成するアプローチ以外の方法は無いのか？ 180 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 16:50:29 ] MT-32よりCM-64の方が面白いよ 181 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 18:19:34 ] ローランド音源かよｗ 182 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 18:21:24 ] >>178 心配なら暗号論的乱数で初期化汁、そこまで気にしないならどうでもいい、でFA出ちゃったからね。 183 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 18:57:12 ] 線形合同法で十分 場合によっては 184 名前：デフォルトの名無しさん mailto:sage [2006/06/13(火) 00:26:32 ] いけぬますれ 185 名前：デフォルトの名無しさん mailto:sage [2006/06/13(火) 00:48:08 ] >>184 そんなこと言ってないでなにか話題提供してくれよ 186 名前：デフォルトの名無しさん [2006/06/13(火) 03:09:15 ] 擬似乱数について素人ですが、教えて頂けないでしょうか？ (0,1)の擬似乱数をMT19937（作成者のHPからFortranソースを拾ってきた）で発生させて、 その平均値と標準偏差が0.5と0.25になるのを確認しようとしました。 （作者の作成したサンプルデータと同じ結果がでることを確認しました。） 平均値は0.5にかなり近づくんですが、標準偏差が0.28程度になります。 乱数の個数を増やしていくと、0.28程度で収束しているように見えます。 octave（実装されてる乱数生成器）でもやってみたんですが、0.25程度に収束しません。 よろしくお願いします。 187 名前：デフォルトの名無しさん mailto:sage [2006/06/13(火) 04:27:11 ] [0,1] の一様分布に従う擬似乱数の標準偏差が 1/sqrt(12) に収束するのは別に何もおかしいところが無いわけだが 乱数の話というよりか確率・統計の話だな 188 名前：デフォルトの名無しさん [2006/06/13(火) 13:49:37 ] 187さんへ 　ありがとうございます。 　たしかに、1/3-(1/2)**2でも0.288...になりました。 　0.25と思い込んでいました。 189 名前：デフォルトの名無しさん mailto:sage [2006/06/14(水) 01:07:11 ] >>175 それ以前に、メルセンヌツイスタはBSDライセンスのはずなのに ソースコード中にライセンスについて一切の記述がない事がまずいと思う。 SYN氏、忘れてんのか？ 190 名前：デフォルトの名無しさん [2006/06/14(水) 01:13:54 ] そーいや乱数発生器のライセンスってどうなってるんだ。 AESはフリーなんだっけ？ 191 名前：デフォルトの名無しさん mailto:sage [2006/06/14(水) 05:53:41 ] yes 192 名前：デフォルトの名無しさん mailto:sage [2006/06/14(水) 21:52:44 ] Rijndaelだけ？他のは？ 193 名前：デフォルトの名無しさん mailto:sage [2006/06/15(木) 10:46:52 ] 自分で調べろ 194 名前：デフォルトの名無しさん [2006/07/08(土) 19:10:20 ] 量子論的乱数発生器ってある？ 195 名前：デフォルトの名無しさん mailto:sage [2006/07/08(土) 22:27:59 ] Intelの最近のチップセットには内蔵されてるはず 196 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 02:16:37 ] 詳細規模んう 197 名前：デフォルトの名無しさん [2006/07/09(日) 08:39:00 ] なんでコンピュータは擬似乱数しか出せないの？ 198 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 09:45:09 ] 真性乱数も出せるだろ、専用のハードウェアがあれば。 199 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 12:52:06 ] >>197 決定性チューリングマシンだから。 ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか？ 200 名前：デフォルトの名無しさん [2006/07/09(日) 14:55:03 ] >>197 つ /dev/random 201 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 19:03:50 ] >>199 > ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか？ 真性乱数は無理。 というか、非決定性チューリングマシンができてしまうと、 今まで暗号論的擬似乱数と呼んでいたものの前提が全て崩れちまうな。 ttp://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0 202 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 01:33:58 ] >>201 えっと、そんなことはないです、オーダー的に。デタラメ言わないで。 203 名前：201 mailto:sage [2006/07/10(月) 02:36:50 ] >>202 え、なんでだ? 非決定性チューリングマシンとはNP完全な問題を多項式時間で解くマシン、 すなわち、単純な総当たりで解くしかない(=解くには指数時間かかる)と思われていた問題を 多項式時間で解いてしまうことのできるマシンであるから、 RC4などストリーム暗号で使われる暗号論的擬似乱数列も多項式時間で解けちゃうでしょ。 204 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 21:01:48 ] どうでもいいがWikipediaを参考文献として引き合いに出すのは勘弁してくれｗ 俺が書いた文章だったりするからｗｗｗ 205 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 21:13:30 ] >>204 嘘書いたの？ 206 名前：デフォルトの名無しさん mailto:sage [2006/07/11(火) 06:52:21 ] 自分の使ってる狭い専門用語を広めるのには便利かもしれないな。 207 名前：デフォルトの名無しさん mailto:sage [2006/07/11(火) 13:35:06 ] >>109の方法をやってみたら どの乱数列データもまったく圧縮できないorz 208 名前：デフォルトの名無しさん mailto:sage [2006/07/11(火) 18:56:18 ] >>205 いやそういう意味じゃないが、非常に照れくさい…… 209 名前：デフォルトの名無しさん [2006/07/19(水) 03:02:36 ] ま、素人はそう考えるわな。 210 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 03:07:16 ] 間違ってるけど 211 名前：デフォルトの名無しさん [2006/07/19(水) 12:52:58 ] 一様な乱数のお薦めを見繕ってくれ 212 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 13:08:01 ] MT 213 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 18:00:52 ] C99のrand()関数は「ラグ付きフィボナッチ」だと聞いたけど、 どんなアルゴリズムなの？ 214 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 18:12:33 ] アルゴリズムまで規定してたっけ？？＜C99 215 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 20:30:32 ] x_i = a * x_(i-p) + b * x_(i-q) (mod M) 狭義のlagged Fibonacciだとa = b = 1. 216 名前：デフォルトの名無しさん [2006/08/26(土) 01:43:17 ] 線形合同法と似てない？ 217 名前：デフォルトの名無しさん [2006/10/08(日) 06:58:26 ] >>211 一様では乱数とは言わない。 特定の周波数幅に対するホワイトノイズ乱数というのなら可能。 この場合は特徴があるが、目的に使う限り特徴は現れにくい。 218 名前：デフォルトの名無しさん mailto:sage [2006/10/08(日) 07:16:59 ] >>217 フィルタ使わずそんなもん発生する事できるのか 是非教えてくれ 219 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 18:00:37 ] ちょークロックの早いPCM合成チップで生成 220 名前：デフォルトの名無しさん [2006/10/09(月) 18:54:49 ] ブラム・ブラム・シャブって乱度高そうだな シャブ打ってラリってそうな響きだ 221 名前：デフォルトの名無しさん [2006/10/09(月) 23:00:54 ] >>218 例えば想像する対象をサイコロの目としてみる。 １から６まで均等にでる乱数なら可能だろ その種類だけ格納するテーブルを作って 確立が高い部分か低い部分を再度乱数を求め補正するだけ 原始的な方法で昔から使われている。 記憶容量に依存するが、多重評価することで要求に対するバランスが測定 可能であれば、それを元に補正するだけでいい。 この方法だと周期はでるが、結果として分かっている周期を補正するのは 容易だろう。 任意の偏りがでるかスペクトルを測定し再評価すればいいだけの話だね。 222 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 00:38:32 ] 統計を取って補正すると、乱数じゃなくなるけど？ 時系列で見ると偏ってるからね。 223 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 00:45:37 ] もともと偏った確率で目が出る疑似乱数に、統計情報を加えて一様乱数にしようとすると、必ず波が出来るよ。 パチンコやスロット台で波が出来るのもこのせい。 224 名前：デフォルトの名無しさん [2006/10/10(火) 01:20:57 ] >>222 １０年間同じ値が続いても乱数。無限に長い時間からすれば確率的には存在する。 そのぐらい理解しておけ 225 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 01:23:04 ] >>223 元の擬似乱数にある偏りが表にでただけで偏りがすくないものなら 測定できるような波はでない。 それに波がでたとしてもそれをフィードバックさせるだけで補正は可能。 226 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 01:25:25 ] まあ、224と225が別人で、まったく逆の方向を指してるのだけはわかった。 227 名前：222 mailto:sage [2006/10/10(火) 01:39:12 ] >>224 統計を取って補正しちゃうと、それが不可能になるって言ってるんだけど？ 228 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 19:31:09 ] バカな俺に「一様では乱数とは言わない」の意味を教えて下さい。 一様乱数は一様ではないの？ 229 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 19:40:53 ] ja.wikipedia.org/wiki/%E4%B9%B1%E6%95%B0%E5%88%97 230 名前：デフォルトの名無しさん [2006/10/10(火) 23:18:00 ] 一応乱数 231 名前：デフォルトの名無しさん mailto:age [2006/10/13(金) 14:21:51 ] >>228 一様だと周期があるということになるのは理解できない？ 一様乱数とは有限の範囲内では周期がないが、それ以上だと 周期がある乱数を言う。 >>224 それは自然乱数の本質だな >>225 これは正規乱数の類だな。上のwikiに解説してあるからしっかり読んでおけ。 232 名前：228 mailto:sage [2006/10/13(金) 17:44:49 ] >>231 >一様だと周期があるということになるのは理解できない？ はい。 「一様であること」とは「偏りがないこと」と理解しています。なので、 >それ以上だと >周期がある乱数を言う。 「一様であること」と「周期があること」の関係が解らないでいるのです。 233 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 01:15:08 ] 数学出来なそうなニオイ… 234 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 02:45:28 ] 横レスで済まんが、俺もわからないんで、デキるあなたが解説してよ>>233 暗号と情報セキュリティのお勉強はしたけど、正直乱数はよくわからん 235 名前：デフォルトの名無しさん [2006/10/14(土) 03:09:53 ] >>231が何言ってるのかは全く不明だけど、 特定の有限回の試行での一様性が担保されているなら、 それは全く乱数ではない、というのは自明だと思う。 ところで、疑似乱数は内部状態を有限量のデジタルデータで 持つという仕組み上、有限の周期をもつこともまた自明。 なわけで、一様な疑似乱数＝乱数ではない、ということになる。 のか？ 一様だろうがそうでなかろうが、所詮周期があるという点で 「疑似」乱数でしかないわけだけど、一様性が担保されている 場合は、そうでない（一様かどうか不明な）場合と違って、 周期の終わりの方では次にでる数字を推定しやすくなる。 ギャンブルには使いにくい。 236 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 08:34:34 ] 普通のrandじゃいけない理由は？ 237 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 09:57:42 ] >>236 その「理由」を君が知りたい理由は？ 238 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 10:04:34 ] >>237日本語でおｋ 239 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 13:11:10 ] ところで、 ttp://www.optoscience.com/maker/id/id.html の真性乱数発生器ってのはホンモノなの？ 熱雑音を利用したチップやボードはよく見かけるけど、 量子乱数ってのはあまり見かけないような気がするッス どういう仕組みになってるんだろうか… 240 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 13:58:00 ] 周期が終わったら初期化すればいいじゃない 241 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 14:48:04 ] >>236 いまどき普通のrandを使う理由は？ 242 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 14:50:22 ] >>241 いまどきじゃないrandが存在する理由は？ 243 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 17:37:21 ] >>242 いまどきじゃない方が便利だから 244 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 17:40:53 ] 便利かどうかで言えば、便利さは「同じ」だと思うな。 重要なのは、目的を達成するための手段として妥当かどうかだよ。 245 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:00:51 ] 少なくとも理不尽さを軽減する効果はある。 ユーザ「なんでここで○○が出て来るんだよ！ありえないだろ！！！」 開発者「MTですから、乱数に変な癖は無いですよ」 ユーザ「そうか・・・偶然じゃあしょうがないな・・・」 みたいな。 246 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:20:35 ] Civシリーズの乱数FAQを思い出すナー 247 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:36:06 ] メルセンヌ・ツイスタのホームページが存在しないんだけど 作者はもう慶応には居ないってこと？ 248 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:45:00 ] >>247 普通に"MT 乱数"とかでググれば出てくると思うが 249 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 10:22:55 ] civの乱数には波がある 250 名前：デフォルトの名無しさん [2006/10/16(月) 12:05:45 ] すいません、昭和初期の国産バスの図面を探しているのですが、 適当な資料をご存じの方がいたら教えてください。 251 名前：228 mailto:sage [2006/10/16(月) 15:19:19 ] >>235 >一様性が担保されているなら …あ、そうか。やっぱ俺はバカでした。 ありがとうございます。ひとつ賢くなりました。 252 名前：デフォルトの名無しさん mailto:age [2006/10/18(水) 17:36:16 ] >>251 本物？釣り氏？ｗ 253 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 18:18:59 ] 一様性が担保されていても、長ーい周期の疑似乱数の最初の方だけ 使うんならあまり問題にならないような気がする。 40万組みのシャフルしたトランプから10枚だけ引くとか。 254 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 20:06:33 ] ここまでの俺の理解： （１）周期があるというのは、別に一様にしようがしまいが疑似乱数である限り言えること （２）一様乱数の場合は、そうでない疑似乱数と比べて 　　　　　　周期の終わりに近づくにつれてさらに予測しやすくなる （３）>>231が前半二行で（１）以外の情報を伝えたかったのかどうかは不明 255 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 23:53:23 ] 一様乱数の意味を勘違いしてる人が多いな。 (正しく作られた)サイコロは過去の出目に関係なく、次にある数字が出る 確率はすべて等しい。＝ 一様である。 サイコロを続けて振って得られる数列は一様乱数になる。 ソフトウエアで生成する乱数が原理的に真性乱数になり得ないのは まったく別の話。一様性とは無関係。 256 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 03:41:58 ] なるほど、その勘違いした人が大声で解説すると。 悪貨が良貨を駆逐するとはこのことか。 257 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 04:10:57 ] >>255 やっぱそうなのか 上の話を読んで 「サイコロを６回ふったら、１から６までの目がどれもぴったり１回出る」 が一様乱数かと思って焦ったよ 258 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 11:45:46 ] >>255 疑似乱数の場合、 ＞確率はすべて等しい。＝ 一様である。 ものと、そうでないものがある、というのはわかっていますか？ 259 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 12:08:06 ] なんでこう自分の言いたい内容を明確に書かない臆病者が多いんだろうね？ ム板の特徴なのかな 260 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 12:16:47 ] >>255 （有限の）周期があって、かつ一様な疑似乱数の特性について 教えてください。１周期内では各数字は同じ回数だけ現れますか？ 261 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 14:32:38 ] >>258 なぜ「過去の出目に関係なく」という部分まで引用しない。 重要なところだぞ。 また、間違ってると思ったらどこがどう間違ってるか書いてくれ。 262 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 23:38:43 ] 一度ギャンブル用のサイコロとかプログラムで作って、現金懸けていわゆる賭博でもしてみれば身にしみてわかるさw 263 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 11:30:26 ] 基本的に目的に使うものに影響がでない周期にして使えば問題ない。 厳密に一様というのは、愚かな考え。 １つの周波数に対して一様なのは可能だが。 264 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 22:58:19 ] >>262 プロと対峙して「てめぇいかさまだな」とか言われた日には。 265 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 11:35:42 ] >>264 その日を境に行方不明になると 266 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 00:15:58 ] サイコロの目は１から６まで均等にはでない。これが物理現象。 理屈の上の乱数と実際に作れる乱数とは別なことを理解できないとは 愚かだよな。 理屈上のサイコロでも「有限回数」の出目は一様ではない事実、これが何故か 理解できないの池沼に説明しても無駄だから放置だｗ 267 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 00:29:16 ] いや、単に「一様」という言葉を 「どの目も同じ回数出る」と誤解してる人がいて 勘違いしてる人もしてない人も混乱しただけだろ。 268 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 00:51:09 ] >>267 どの目でも確率分布を一様にさせると言う事は、出る回数が同じになって行くと言う事じゃないのか？ 269 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 00:56:51 ] >>268 そうじゃなくてサイコロを600回振ったら100回1が出る という意味の「同じ回数」。 出目が一様なサイコロを600回振っても1が100回じゃない ことの方がずっと多い。 270 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 01:02:53 ] >>269 100回でも99回でも101回でもいいけど、100回に近くするって事だろ？ 99回ならもう一回出そうかな？とか、101回出てたら、もう控えようかな？　とか、操作するんだよね？ 271 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 01:03:44 ] >>268 > どの目でも確率分布を一様にさせると言う事は、出る回数が同じになって行くと言う事じゃないのか？ 全然違う。 たとえば、n回サイコロを投げて1の目が出た回数をk1、2の目が出た回数をk2とすれば、 nを大きくしていくと k1/n と k2/n はともに 1/6 に収束していく(大数の法則)が、 |k1-k2|の期待値は大きくなっていくんだよ。 272 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 01:09:33 ] >>270 何の話だ？ まず、そういう操作をしたら一様でなくなってしまう。 過去の出目から未来がある程度予測できてしまうから。 で、そういう操作をする乱数の名前は知らない。 確かに、「誤用の一様」の意味はそれかも。 実用性はありそうだが、名前付いてる？ 273 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 01:20:30 ] >>272 ギャンブルマシンと言われるゲーム機やパチンコ台やスロットの中身 274 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 14:07:29 ] サイコロは真性乱数。規則性とかないんだから、いつでも確率で語るしかない。 しかし、初期条件で全て決定される疑似乱数で各出目の出現回数が違ったら、 それは一様でないということなんじゃないの？ >>273 スロやパチはほとんど真性乱数とみて問題無いよ。 現在スロで主流の方法は、数MHzのクロックを16bitのカウンタで数えていて レバーが叩かれた時にラッチするというもの。 カウンタが1周する周期が0.03秒とかだから、人間がレバーを叩いているかぎり ほとんど真性乱数といえる。（だからソレノイドでレバーを叩いて狙う方法が存在する） 275 名前：デフォルトの名無しさん mailto:sage [2006/10/25(水) 23:49:24 ] >>254 > （２）一様乱数の場合は、そうでない疑似乱数と比べて > 　　　　　　周期の終わりに近づくにつれてさらに予測しやすくなる それは違う。 一様でない疑似乱数、たとえば"1"が1/2の確率で"2"〜"6"がそれぞれ1/10の確率で 出現する疑似乱数列があるとして、その周期の大半を消費したとき"1"の出現率が 1/2より小さければ、周期の残りでは"1"の出現率が1/2より大きくなる。 つまり、次にでる数字を推定しやすいのは、その疑似乱数列の周期と分布が 「既知」であり、その周期に対して十分な長さの過去の乱数列を知っている場合だってこと。 その既知の分布の種類は、一様分布でなく二項分布であってもいいわけだ。 276 名前：デフォルトの名無しさん mailto:sage [2006/10/26(木) 11:02:45 ] 乱数は、完全な一様性を示さないものだろ、 サイコロの目のような有限の個数の値が どの数も確立も一定なら真の乱数ではない。 単なるスペクトルの問題であり、長超周期の乱数を否定しなければ 短期間の乱数の一様性を守ることは不可能だろ。 おまいらが有限と思っている期間でさえ無限に近い乱数の価値観から すれば短い期間であり、同じ値が続いたとしても確立の１つである。 短い期間が１億回同じ値が続くケースが存在したとしても、 乱数として間違いはない。 つまりだ、人間が扱える乱数とは有限回数の中でどの周波数成分でも 似た値を示すような数値を乱数と判断しているだけ。周期は確実にあり、 実用であるか、どうかの問題にしかすぎない。 プログラム板としては。ライブラリーが提供するような激しく短いビット 数の乱数を使うからこそ周期や特徴が出てしまうだけで、長い周期を 比較的単純なアルゴリズムで作れば問題はありえない。 円周率とか、無限級数でも使えｗ 277 名前：デフォルトの名無しさん [2006/10/26(木) 15:11:27 ] >>275 >それは違う。 中略 >つまり、次にでる数字を推定しやすいのは、その疑似乱数列の周期と分布が >「既知」であり、その周期に対して十分な長さの過去の乱数列を知っている場合だってこと。 「違う」といいながら同じことを言っているような気がする。 278 名前：デフォルトの名無しさん mailto:sage [2006/10/26(木) 16:44:04 ] >>276 何を主張したいのかよくわからんが、 一様の説明で例に出したサイコロは理想的なサイコロで、 理想的なサイコロは完全な一様性を示す。 有限回振ることが前提でも一様性は変わらない。 >>270みたいのを一様だと思っているのか？違うぞ。 >>277 同じことは言ってないだろ。ちゃんと違うよ。 >>254は一様乱数の場合に予測できると書いていて、（←間違い） >>275は周期と分布が既知の擬似乱数の場合に予測できると書いている。 279 名前：デフォルトの名無しさん mailto:sage [2006/10/26(木) 20:38:54 ] >>254は「周期の終わりの方では」と書いているんだから、 周期の終わりの方を使っていることが解る⇒周期が既知、 が前提なんじゃないのか？分布も「一様」が前提だし。 280 名前：デフォルトの名無しさん mailto:sage [2006/10/26(木) 20:58:11 ] >>279 ああ、そういうことか。 >>254(2)は、一様かつ周期があると言っているが、 これは言葉が矛盾してる。周期があったら一様じゃない。 ていうか擬似乱数は一様にならないだろ。 281 名前：デフォルトの名無しさん mailto:sage [2006/10/26(木) 21:28:23 ] 指向性が無ければ一様といえる 282 名前：280 mailto:sage [2006/10/26(木) 21:34:11 ] あ、ちょっと勘違いしてたかも。 >>275は周期のある擬似乱数に関して、 分布が既知ならそれが「一様分布でなくても」 予測ができる、と主張してるんだ。 >>254の勘違いは、一様の意味を>>268のように思っていること。 実際は>>271の言うように一様でも|k1-k2|の期待値は大きくなっていく。 更に、>>268のような数列は乱数ではあり得ない。 一様であるなしに関わらず乱数ならば過去の数列から予測は不可能。 逆に擬似乱数の場合、分布が一様でも何でも既知ならある程度予測ができる。 ということは、>>255も誤解を招く表現だ。 サイコロで次に出る目が過去の出目に関係ない＝乱数 サイコロでどの目が出る確率も同じ＝一様 擬似乱数に対して一様という言葉を使うかどうかは知らないが、 乱数であるならば既に過去の出目には関係ないので、 過去の出目に関係ないことを言うのに一様を主張する必要はない。 283 名前：デフォルトの名無しさん mailto:sage [2006/10/26(木) 21:48:58 ] はっきり言って俺最強すぎて我慢できない 284 名前：デフォルトの名無しさん mailto:sage [2006/10/27(金) 00:38:08 ] >>282 勘違いしているなら、「あ、ちょっと勘違いしてたかも。」は 常識が無い発言だよなｗ 285 名前：デフォルトの名無しさん mailto:sage [2006/10/27(金) 02:02:26 ] 一様性を検査しなくていいの？ 286 名前：デフォルトの名無しさん mailto:sage [2006/10/27(金) 02:07:39 ] >>285 一様性を「証明」する方が重要じゃないの 287 名前：デフォルトの名無しさん mailto:sage [2006/10/27(金) 23:14:52 ] >>254=>>257です >>254は「この人はこう言いたかったのかな？」と予想して書いたものなんで悪しからず >>276 ＞短い期間が１億回同じ値が続くケースが存在したとしても、 ＞乱数として間違いはない。 確率分布が一様分布な確率変数のとる値が、たまたま一億回同じ値だったとしても それは乱数ってことですよね。 （ここのほとんどの人は最初からそれは了解してるように思う） ＞つまりだ、人間が扱える乱数とは有限回数の中でどの周波数成分でも ＞似た値を示すような数値を乱数と判断しているだけ。 何か数列があって、それがバラバラな値の列だから乱数だ、そうでないから乱数じゃない、ってのは そもそも違うってことですよね？ 「どうやって採られたものか」が重要である、と。 んで ・有限長の数列を用意して、それを乱数として使う場合は 　　統計的に値の出現頻度が偏っているときに、それを補正することもある ・疑似乱数は有限の長さの数列の後に同じ数列の繰り返しになる この二点がとりあえず事実ということでおｋ？ 288 名前：デフォルトの名無しさん mailto:sage [2006/10/27(金) 23:15:59 ] 訂正 ×疑似乱数は 〇疑似乱数生成器の出力は 289 名前：デフォルトの名無しさん mailto:sage [2006/10/28(土) 01:02:27 ] 粘着しているのは極度に短い周期の擬似乱数＝ライブラリーに付属しているような ものを利用して乱数の一様性を補正すれば、乱数ではなくなるように勘違い しているとかか？ 極度に短い擬似乱数ではなく、極度に長い周期の乱数を用いて、目的の 一様性が保たれれば変な癖などでないだろ。元にしている擬似乱数が 貧弱すぎるじゃまいか？ 290 名前：デフォルトの名無しさん mailto:sage [2006/10/28(土) 08:19:35 ] >>287 >統計的に値の出現頻度が偏っているときに、それを補正することもある どういう補正を考えてるの？ 「1が続いたので次に1が出る確率を減らす」ような処理ならばNo。 そのような数列は乱数とは呼ばない。 乱数とは過去のデータにかかわらず常に一定の確率分布を持つもの。 計算によって異なる確率分布の乱数を作る事はある。 例えば、一様分布の乱数を利用して正規分布の乱数を得る等。 291 名前：デフォルトの名無しさん mailto:sage [2006/10/30(月) 01:03:45 ] 有名な同じ値が続かない乱数の作成方法として。 基本の擬似乱数発生から乱数がでる目の数だけ記録 （１から１０００なら１０００ビット） 同じ値が出た場合は出てないビットがでるまでか、適当な位置から 出ていない数値を検索しそれを乱数とする。 この場合だと１０００回の周期があるが１０００回中は同じ値がでないように できる。 １から１０００まで同じ確立で発生し、その発生根本は別の擬似乱数など から流用すればいい。 これは表面上は同じ値が続かないし元の擬似乱数が乱数的であれば それなりに使える、例えばシャッフル再生などの音楽プレーヤーの アルゴリズムなどで採用されている例がある。 292 名前：デフォルトの名無しさん mailto:age [2006/10/31(火) 17:45:56 ] >>291 それがＦＡ？ 293 名前：デフォルトの名無しさん [2006/10/31(火) 22:32:18 ] >280 >>>254の勘違いは、一様の意味を>>268のように思っていること。 >実際は>>271の言うように一様でも|k1-k2|の期待値は大きくなっていく。 それは真の乱数の話ではないでしょうか。 このスレでは疑似乱数についてだけ話すようにしないと混乱の元では？ >>更に、>>268のような数列は乱数ではあり得ない。 これも同様。 294 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 22:41:15 ] >>291 それは乱数というよりシャフルというかなんというか。 それはともかくとして、確率分布を補正する方法としては 目的の分布をもつ真の乱数列からなる適当なサイズの乱数表があれば、 疑似乱数でその表のn番目を拾ってゆくような方法があるような気がする。 どれくらいの大きさの表が必要なのかはよく分からないけど。 295 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 22:47:13 ] ループしすぎ 296 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 23:11:02 ] >>293 その通りだ。混乱しそうな場合は単に乱数と言わず、 「真の乱数」「擬似乱数」と言った方がいいね。 >>282は真の乱数のつもりで話している。 擬似乱数に対して一様という言葉を使ったら、 単に擬似乱数の周期の中でどの数が出る回数も同じという意味だよな。 1,2,3,4,1,2,3,4,・・・という周期的な擬似乱数（質は最悪だが）も、一様ということになる。 こういう使い方は正しい？ 297 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 23:26:51 ] >>296 > 1,2,3,4,1,2,3,4,・・・という周期的な擬似乱数（質は最悪だが） そこまで短い周期の数列を「擬似乱数」と呼ぶのは変だと思う。 「擬似」乱数なんだから、ある程度は真の乱数の代替に使えるくらいの 性質を持ってないと。 だから、ちょっとやそっとじゃ一周できないくらいの長い周期を持っていることは 「擬似乱数」と名乗るための重要なファクターだと思う。 298 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 23:30:17 ] >>297 つまり、ある程度乱数っぽい列に対しては 一様乱数という言葉を296の意味で使っていいということ？ 299 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 23:58:37 ] おまいら、円周率つかえ。 300 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 00:24:54 ] 円周率やルート2って、真の乱数と言えないような要素ある？ １億桁目までの数字の偏りとかじゃなくて、本質的にわかっている部分で。 301 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 00:43:21 ] 円周率は、任意の桁までは計算によって求める事が可能。 今まで出た数値が円周率の数値と同じならば、次に出る数値は計算によって算出可能。 この事は、予測可能な事を意味する。 よって乱数ではない。 302 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 01:37:13 ] >>301 下手な疑似乱数より周期長くていいぞw 303 名前：300 mailto:sage [2006/11/01(水) 01:42:15 ] >>301 > 今まで出た数値が円周率の数値と同じならば、次に出る数値は計算によって算出可能。 円周率に近い別の無理数かもしれない。例えばπ＋1/√(10^1000+1)とか。 で、俺が聞きたかったのはそういうことではなくて、 例えば円周率の10^1000+1桁目から10^1000+10^20桁目までの列と、 真性乱数の10^20個の列を与えられたときにある程度の区別が付くか、ということ。 わかりにくくてスマソ。 304 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 06:39:59 ] 真正な乱数ならどんな数列でも出現する可能性はあるわけで、 数列だけを比較して区別するなんて不可能でしょ。 305 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 08:08:48 ] >>304 そんなことはわかっている。 だが、例えば「1の後には2が来やすい」のような傾向があれば 十分な長さの列があればほぼ確実に判定できるだろ。 306 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 09:02:29 ] わかっているなら聞くまでもないじゃん。 307 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 23:39:31 ] 大学教授、円周率を計算し過ぎて逮捕 ttp://www.faireal.net/articles/4/23/#d60401 308 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 23:53:09 ] >>307 あのカスラックなら本当に言い出しかねんな 309 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 00:34:57 ] >>301 無限に続くものは任意の桁まで計算できない。 理由は、計算するまでに宇宙が終わるｗ 人類も機械も消える。 愚かだなｗ 310 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 00:48:07 ] 「任意の桁はどこにしますか？」 「無限桁目にします」 311 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 01:07:13 ] バカだな　宇宙が終わるなんて都市伝説だよ 312 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 01:47:41 ] 宇宙が意思、知能を持っていて、宇宙自身が算術を可能という説もある。 というのは、ガセ。 313 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 02:56:59 ] 42 314 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 03:57:58 ] 42 ：デフォルトの名無しさん ：2006/05/04(木) 08:51:13  要するにマンコ  315 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 14:23:01 ] 地面は平らだ。丸いわけがない。 象が支えて亀が歩いているんだ。 宇宙があるなんて都市伝説だ。 316 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 20:25:42 ] 人間なんて居るわけが無い。 これは全部俺の妄想だ、夢だ。 317 名前：デフォルトの名無しさん mailto:sage [2006/11/03(金) 04:02:16 ] >316 お前今「嘘」ってＷＯＰ使うの避けたろ 318 名前：デフォルトの名無しさん mailto:age [2006/11/03(金) 12:40:49 ] 何で擬似乱数程度でこれほど燃えるんだよ、馬鹿ばっかりだなｗ 319 名前：デフォルトの名無しさん mailto:sage [2006/11/03(金) 12:57:37 ] 燃えてるように感じてるのは多分お前だけ 320 名前：デフォルトの名無しさん mailto:age [2006/11/04(土) 02:58:27 ] 319みたいなＤＱＮばかりだけど勘弁してやれ>318 321 名前：デフォルトの名無しさん mailto:sage [2006/11/04(土) 04:25:47 ] 折角萌えるなら擬人ｋ 322 名前：デフォルトの名無しさん mailto:age [2006/11/06(月) 00:48:31 ] とうとう煽り愛のスレに成り果てましたか？ 323 名前：デフォルトの名無しさん mailto:age [2006/11/10(金) 15:09:58 ] >>294 短い周期なら乱数だろ？０と１の２種類とかｗ 324 名前：デフォルトの名無しさん mailto:sage [2006/11/10(金) 17:27:29 ] >>291 最初は[1,n]の乱数で、次は[1,n-1]の乱数…と発生させてその出力を使えば同じこと。 325 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 11:03:50 ] で、おまいらがほしい乱数とは、数値が連続せず、どの数値も同じ確立に なりやすい擬似乱数だろ？ プロセッサのリヤルタイムクロックに同期するようなプログラムはほぼ 困難というか事実上は不可能だろうから それでも利用すればいいんじゃないか？連続に高速で利用する場合も 考慮して乱数テーブルでも用意してミックスすればよさげ。 326 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 11:06:39 ] そんなあなたに www.t-rs.co.jp/products/p-5/index_j.htm 327 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 12:08:13 ] 時計もないしメモリの状態も常に一定の環境で 擬似乱数を発生させたいんだけど 不確定要素が無いので種がいつも同じなので 動作が常に一定になってしまい 擬似乱数にならないのです どうしたらいいのでしょうか？ 328 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 13:45:00 ] サイコロ振って手入力 329 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 13:55:21 ] 外部要因で動作・変化する何かがないとムリだっぺ 330 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 14:10:35 ] >>327 よく使う手だけど メモリをちょっと壊す 331 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 15:13:12 ] >>327 人間に２回何かさせる。 332 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 15:15:11 ] >>327 原理的に不確定要素が必要だから、何とかするしかない。 メモリ状態、ユーザの入力、CPUｊの状態、 それでもダメなら種を予め手入力しておく。 333 名前：327 mailto:sage [2006/11/23(木) 16:19:37 ] やはり不確定要素が必要なのですね アドバイスありがとうございました 334 名前：デフォルトの名無しさん mailto:sage [2006/11/23(木) 20:23:10 ] そこでUSBガイガーカウンタですよ。 335 名前：デフォルトの名無しさん mailto:sage [2006/11/26(日) 12:39:36 ] 擬似乱数の萌え擬人化希望 336 名前：デフォルトの名無しさん mailto:sage [2006/11/26(日) 17:18:11 ] > メモリの状態も常に一定 ずっとHLTでもしてるのか? 337 名前：デフォルトの名無しさん mailto:sage [2006/11/26(日) 18:21:36 ] >>336 初期値がクリアされているシングルスレッドではないかと・・・ いや、やっぱずっとHLTかな・・・ 338 名前：デフォルトの名無しさん mailto:sage [2006/11/28(火) 05:08:43 ] >>332 昔と違ってＯＳが動いているＰＣなら普通に不確定要素のタイミングで 動いている。 ＣＰＵコアのリヤルタイムクロックとアイドリングで動くカウンター要素 等を組み合わせても不確定要素を簡単に抽出可能だろ。 ワンチップマイコンや電子回路程度では話は変わってくるだろうけどな 339 名前：デフォルトの名無しさん mailto:sage [2006/11/28(火) 05:11:25 ] 時計もないしメモリの状態も常に一定の環境 340 名前：デフォルトの名無しさん mailto:sage [2006/11/28(火) 08:05:30 ] リヤルタイム 341 名前：デフォルトの名無しさん mailto:sage [2006/11/28(火) 13:50:36 ] >>334 プーチン政権を批判するロシア人に持たせれば 良質な乱数が作れそうだな。 342 名前：デフォルトの名無しさん mailto:sage [2006/11/28(火) 14:57:40 ] >>341 All1で乱数にならない罠。 343 名前：デフォルトの名無しさん mailto:sage [2006/11/29(水) 16:51:41 ] 擬似乱数なんてストリーム暗号の出力使えばいいじゃん 344 名前：デフォルトの名無しさん mailto:sage [2006/11/30(木) 12:06:53 ] マリーアントワネット様ｷﾀ 345 名前：デフォルトの名無しさん mailto:sage [2006/12/02(土) 22:43:18 ] >>325 >で、おまいらがほしい乱数とは、数値が連続せず、どの数値も同じ確立に >なりやすい擬似乱数だろ？ このへんが少し困るところだよな。 人によっては(もしかするとかなり多くの人が)その方がランダムだと 思っちゃうんだよな。 もしサイコロで6が5回位続いたら仕込んであると怪しまれそう。 同じ目が続かない方が乱数としてはおかしいんだけどな。 短周期で目の分布がいつも揃ってたらそれもおかしいし。 52314ときたら次は6だろうみたいな。 人の感じる乱数性は真の乱数性とは違うんだろう。 346 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 22:06:11 ] 音楽のランダム再生などは、真の乱数性ではなく、 人がランダムと感じることこそが重要だが、 こういう擬似乱数列を得る手法で有名どころとかある？ 347 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 22:46:36 ] >>346 単なるシャッフル再生じゃダメなのけ? 348 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 23:13:51 ] シャッフルといってもいろいろあるべさ。 某MP3プレーヤのシャッフルリピートは同じ曲を3回繰り返したし、 某なんとかシャッフルのシャッフルリピートは同じ曲を一回おきに3回繰り返した。 349 名前：347 mailto:sage [2006/12/03(日) 23:41:42 ] ランダム再生とシャッフル再生を区別しているプレイヤーもあるな。 ランダム再生 … 一曲終わるたびに、次に再生する曲を全プレイリストの中からランダムに選ぶ。 シャッフル再生 … 再生開始時にプレイリストの一覧をシャッフルしたものを内部的に作り、 その順序にしたがって再生する。プレイリストの全曲を再生し終わったら もう一度プレイリストをシャッフルする。 この分類だと、>348のようなことはランダム再生だと起こりうるが、 シャッフル再生だと起こらない。 350 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 23:54:15 ] >>347 言われてみればそうだな。連続出現の心配はなくなるわけだ。 あとで思い出したが、同じアルバムの曲が１０曲中３曲もあるから ランダムじゃないと感じることもある。 まあこれもバラし方を考えればいいだけで、 乱数の発生方法とは関係ない話だったな。 351 名前：デフォルトの名無しさん mailto:sage [2006/12/04(月) 11:10:31 ] >>346 >>324みたいな乱数列を作ればいい訳で 352 名前：デフォルトの名無しさん mailto:sage [2006/12/05(火) 13:57:14 ] >>345 擬似乱数なんだから乱数を元にしたシャッフルで問題ないだろ。 現実のサイコロにしても目の数の周期性はあるわけだし。 ※理論的なサイコロではない。 単に乱数に拘るのは周期が短いライブラリーなどにある乱数関数を使うと 規則性が表面に出て見えることがある。 この点であると思う。真の乱数であるなばら規則性が目立っても それは一時的（数年続いても無限からすれば極短期間）な挙動であって 乱数である。 何かの規則で一様性な分布がほしいのであれば「無限級数」等を使えば 言い訳で、人間から見て一様乱数にみえるのはシャッフルがもっとも 近いものじゃないか？ 353 名前：デフォルトの名無しさん mailto:sage [2006/12/05(火) 18:28:56 ] >>352 ぐだぐだな日本語に気持ち悪くなってくる。 >擬似乱数なんだから乱数を元にしたシャッフルで問題ないだろ。 シャッフルな用途にはシャッフルで問題ない。シャッフルでは困る用途もきっとある。 >現実のサイコロにしても目の数の周期性はあるわけだし。 現実のサイコロに周期性など無い。ってか「目の数の周期性」って何？ >単に乱数に拘るのは周期が短いライブラリーなどにある乱数関数を使うと >規則性が表面に出て見えることがある。 この文は「周期が短い乱数関数を使うと規則性が見える。」でよいか？ （冒頭の「単に乱数に拘るのは」はなんなんだろう？） >この点であると思う。 何が？？ >真の乱数であるなばら規則性が目立っても >それは一時的（数年続いても無限からすれば極短期間）な挙動であって >乱数である。 最後の「乱数である。」はいらない。「挙動である。」で締めましょう。 >何かの規則で一様性な分布がほしいのであれば「無限級数」等を使えば言い訳で、 無限級数なんて関係無いでしょう。級数=数列の和　ですよ。 >人間から見て一様乱数にみえるのはシャッフルがもっとも >近いものじゃないか？ 人がどう見るかなんて、その人によるとしか言えない。 一巡するまで同じものが出ないものは一様乱数にみえないって人もいるだろう。 354 名前：デフォルトの名無しさん mailto:sage [2006/12/06(水) 00:16:44 ] ところで↓こういうネタがあるんだが、どう思う? ttp://bugfix.jp/blog/culdceptsaga/2006/12/post_42.html 355 名前：デフォルトの名無しさん mailto:sage [2006/12/06(水) 10:33:38 ] >>353 釣り氏？ 356 名前：287 mailto:sage [2006/12/06(水) 15:34:10 ] >>290 >>統計的に値の出現頻度が偏っているときに、それを補正することもある >どういう補正を考えてるの？ 全然わからないです．というか >「1が続いたので次に1が出る確率を減らす」ような処理ならばNo。 >そのような数列は乱数とは呼ばない。 >乱数とは過去のデータにかかわらず常に一定の確率分布を持つもの。 私もそう思う（そういう定義しか知らない）ので・・・ 357 名前：デフォルトの名無しさん mailto:sage [2006/12/08(金) 23:57:04 ] >>356 ここは擬似乱数のところだから、真の乱数、つまり論理的な真の乱数を 言うのならそれなりの説明が必要とおもわれる。 実際に必要とされるのは真の乱数ではなく、擬似乱数であり 擬似乱数にはいろいろ種類があり、用途別に話しを展開しなければ 無意味な議論じゃないのか？ 358 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 20:21:25 ] ほしゅ 359 名前：デフォルトの名無しさん [2007/01/31(水) 23:01:07 ] >>330 しょ、詳細を… 360 名前：デフォルトの名無しさん mailto:sage [2007/02/01(木) 22:52:43 ] >>359 カオスのバタフライ現象を簡易化した形を使うのが簡易です。 シフトとビット操作で比較的簡単に作れる。 放送大学で具体的手法まで解説していたよ。 全体を均一にしたい場合はＣＤプレイヤーなどで 使われるシャッフルのアルゴリズムが一番簡易です。 ０〜９９９の間なら１０００ビットのRAMが最低必要になりますが。 361 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 08:09:20 ] CDプレイヤのシャッフルと言うと、実装方法によってばらつきがまちまちということですか? #中には同じ曲が連続しやがるCDプレイヤも一回置きに繰り返すCDプレイヤもあるのだが。 362 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 08:46:34 ] それはシャッフル再生ではなくてランダム再生？ 363 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 09:17:28 ] シャッフル再生と言い張りつつ>361のようなのはあるね。iPodShuffleも所謂シャッフルじゃないし。 364 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 16:31:17 ] Winampは完全なオプションでシャッフルから完全なランダムまで変化の度合いを設定できるんだよな Morph Rateとか名づけてたっけ 365 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 16:32:05 ] すまん1行目訂正 Winampはオプションで完全なシャッフルから完全なランダムまで変化の度合いを 366 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 22:52:08 ] >>361 シャッフルを正しく実装しているものは同じ曲をバラバラにすべての曲を １回づつ再生する機能のこと。 ランダム再生をしているのにシャッフルと名前を付けている のは単に誤訳か、まがい物じゃないか？ e-words.jp/w/E382B7E383A3E38383E38395E383ABE5868DE7949F.html 367 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 22:54:16 ] 公取委かJAROに訴えればいいのそれ？ 368 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 23:50:08 ] >>366 iPodShuffule訴えてくれ。 369 名前：デフォルトの名無しさん mailto:sage [2007/02/03(土) 22:08:43 ] >>368>>367 アップルに騙されたオマイがDQN 370 名前：デフォルトの名無しさん mailto:sage [2007/02/11(日) 10:15:46 ] 最も単純で低精度な擬似乱数の作り方てどこかにない？ 371 名前：デフォルトの名無しさん mailto:sage [2007/02/11(日) 10:25:27 ] どんなアルゴリズムでも擬似乱数と言い張れば、それは擬似乱数 372 名前：デフォルトの名無しさん mailto:sage [2007/02/11(日) 10:53:43 ] >370 ttp://ja.wikipedia.org/wiki/擬似乱数 373 名前：デフォルトの名無しさん mailto:sage [2007/02/11(日) 11:21:27 ] もっとも単純なわけでも低精度なわけでもないが 地球上でもっとも虐げられている擬似乱数アルゴリズムは やっぱ線形合同法なんじゃね？ 374 名前：デフォルトの名無しさん [2007/02/11(日) 18:07:28 ] >>370 5かけて1足してffでマスク 375 名前：デフォルトの名無しさん mailto:sage [2007/02/14(水) 06:24:21 ] >>370 擬似バタフライ効果があれば何でもいいんじゃない？ 376 名前：デフォルトの名無しさん mailto:sage [2007/03/06(火) 15:47:49 ] >>370 常に定数を返す擬似乱数がもっとも周期が短い。 これより周期の短い擬似乱数はない。 377 名前：デフォルトの名無しさん mailto:sage [2007/03/06(火) 22:46:09 ] 何も返さない擬似乱数 378 名前：デフォルトの名無しさん mailto:sage [2007/03/07(水) 07:58:43 ] 何も返さない擬似乱数は周期が短いとは言えない。 何も返さない擬似乱数は分布が偏っているとは言えない。 何も返さない擬似乱数は擬似乱数テストプログラムをテストするために使えない。 370の目的はたぶん最後のコレ。 379 名前：デフォルトの名無しさん mailto:sage [2007/03/07(水) 20:58:47 ] >>376 定数ってだけじゃなく1bitであるべき(どうしても int にするなら 0 or -1)だろうな。 そうじゃないとbit単位のストリームとして見たときにbit数分の周期が存在することになる。 380 名前：デフォルトの名無しさん mailto:sage [2007/03/08(木) 08:13:45 ] うむ、0と1の分布という点からも0か-1であるべきだな。 そして、0超過状態からの脱出という観点からは0であるべきだな。 381 名前：171 [2007/04/10(火) 04:02:15 ] いつのまにやらSIMD対応ほかいろいろ改良してるモノが出てるな。 まあ俺が以前いってたSIMD対応はメモリ上の並びをパズルみたいにコチョコチョいじるだけで メモリ使用量も増やさず意外と簡単にできたんだが、 それ以外の改良となると、やっぱじっくり研究しないといかんわな。 悔しいが現役の学生にはかなわん。これは認めておいて、 とりあえずコード読んで高速化の余地を探すとするか。 382 名前：デフォルトの名無しさん [2007/04/10(火) 04:26:31 ] どっちの乱数の方が優れているか判定をおしえろ 383 名前：382(乱数の精度判定) [2007/04/10(火) 05:08:58 ] #include <stdio.h> #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;} 384 名前：382 改良版 [2007/04/10(火) 05:40:20 ] #include <stdio.h> #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);} 385 名前：382 [2007/04/10(火) 05:43:38 ] Cの標準がかなりいいんだが >>18のrandの精度(値が小さいほど良い) 0.000233346 生成速度8.329000秒 >>84のrandの精度(値が小さいほど良い) 0.000106306 生成速度8.171000秒 自前のrandの精度(値が小さいほど良い) 0.000263426 生成速度19.563000秒 　 Cのrandの精度(値が小さいほど良い) 0.000001454 生成速度9.734000秒 386 名前：CryptGenRandomはいまいち [2007/04/10(火) 06:28:12 ] #include <stdio.h> #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);} 387 名前：デフォルトの名無しさん mailto:sage [2007/04/10(火) 12:22:01 ] コード直貼りもいいが、うｐろだを活用してくれ 388 名前：デフォルトの名無しさん mailto:sage [2007/04/11(水) 01:36:14 ] ム板的にはwikiのが良くね？ 389 名前：デフォルトの名無しさん [2007/04/11(水) 02:34:04 ] 疑似乱に周期があるから、パイで検定するときは、1000回、10000回、と増やして いって近似がパイに近づかなくなる回数を調べる事も重要 390 名前：デフォルトの名無しさん mailto:sage [2007/04/11(水) 16:34:53 ] 擬似乱数のことを擬似乱と略す人間は初めて見た 391 名前：デフォルトの名無しさん mailto:sage [2007/04/11(水) 21:27:44 ] >>386 この精度がいいと(あるいは悪いと)どういう乱数ってことになるの？ あと、なんで win_rand() だけ 1 bit 捨ててんの？ 392 名前：デフォルトの名無しさん [2007/04/16(月) 16:57:12 ] >>391 円周率は、3.1415である 正方形(サイズは40000とする)の内部にランダムに 点を4万回打てば、それに内接する円の内部に点が打たれる回数は 31415回程度になる 試行回数を増やせば増やすほど円周率にちかずく ここで乱数の生成が均等であるほど近くなる 393 名前：デフォルトの名無しさん mailto:sage [2007/04/16(月) 20:00:37 ] このスレは共立版 knuth の3巻を読んでる事を前提にしていいんですよね? 394 名前：デフォルトの名無しさん mailto:sage [2007/04/16(月) 20:59:09 ] >>392 �d。 win_rand() で 1 bit 捨ててんのはなんで？ 395 名前：デフォルトの名無しさん [2007/04/16(月) 21:15:24 ] 捨てないと符号関係のエラーがでるんだが 396 名前：デフォルトの名無しさん mailto:sage [2007/04/16(月) 21:25:48 ] >>395 それはなんかチョンボってないか？ 俺んとこじゃ return (double)(b[0]+(b[1]<<8)+(b[2]<<16)+(b[3]<<24))/4294967296; で、エラーにはならんし。kaisu を 1000000あたりで試行した時は win_rand() が断トツの精度を誇るぞ。 # 処理に要する時間も断トツだけどｗ 397 名前：デフォルトの名無しさん mailto:sage [2007/04/16(月) 22:10:39 ] >>393 共立じゃなくてサイエンス社 398 名前：デフォルトの名無しさん mailto:sage [2007/04/16(月) 22:12:25 ] boost::random::mersenne_twisterはだめなん？ 399 名前：デフォルトの名無しさん mailto:sage [2007/04/17(火) 01:51:37 ] ダメじゃないよ。 というか実質的には最強。 とりあえずwikiでも読んでみなよ。 400 名前：デフォルトの名無しさん mailto:sage [2007/04/17(火) 07:06:41 ] もっとすごいのあるよ SIMD-oriented Fast Mersenne Twister (SFMT): ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html 401 名前：デフォルトの名無しさん mailto:sage [2007/04/17(火) 19:30:13 ] WELLの登場で次世代の擬似乱数は混沌とするかと思ったが、 これでしばらくMTの系譜が続くのは確定だな 402 名前：デフォルトの名無しさん mailto:sage [2007/04/17(火) 22:40:44 ] 周期長っ！ 403 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 00:14:07 ] 速っ ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html 404 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 10:51:22 ] boost::random::mersenne_twister「メモリぱくぱく　おいちい＾＾＾＾」 405 名前：デフォルトの名無しさん mailto:sage [2007/04/19(木) 20:33:08 ] >>402 >>404 だからSFMTでは短周期版も作ったんじゃないか 406 名前：デフォルトの名無しさん [2007/07/04(水) 20:56:27 ] SFMTのboost対応版ﾏﾀﾞｰ? 407 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 00:18:50 ] Twister 系の擬似乱数て 単にカオスの簡単な例「２重振り子」を演算で出しただけじゃん。 適度に内部ビット数増やせば、周期なんて測定不能な域にするのは容易じゃん。 ワンチップとかの超小型マイコンで作るんじゃないんだし、今のＰＣなら 乱数で使うメモリは捨てるほどあるわけだしな。 408 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 00:29:35 ] >単にカオスの簡単な例「２重振り子」を演算で出しただけじゃん。 それを実装したことに意味があるんじゃん。 …って開発者が言ってた。 409 名前：デフォルトの名無しさん mailto:sage [2007/07/09(月) 23:43:55 ] >>408 似た事を主張した奴とか類似物を作ったやつも、正式に論文発表しなかった だけにすぎない。 410 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 09:47:42 ] コロンブスなんて西に航海しただけ。コロンブスがしなくても誰かがやったよね。 411 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 09:52:53 ] コロンブスってタダの方向音痴なんじゃないかと思う 412 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 10:22:53 ] 「西に向かえば地球は丸いそうだからアジアに辿り着ける筈だ」と言う発想は方向音痴とはいえまい。 413 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 13:30:58 ] 西に向かって最初に見つけた陸地を西インド諸島と名付けるのはどうか。 せめて西ジパング諸島と呼ぶべきだったと思う。 414 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 15:29:18 ] コロンブス以前に原始人が海をわったったという遺伝子が原住民の 遺伝子確認で分かっている点について（ｒｙ 415 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 20:29:40 ] 同時代に同じことを考えた香具師はいっぱいいる コロンブスチームのマーケティングの勝利 416 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 20:40:37 ] このビルのガラス窓は頑丈だと証明しようと体当たりしてぶち破って死んだ弁護士もいたな 417 名前：デフォルトの名無しさん [2007/07/11(水) 01:10:25 ] >>416 荒縄静香を思い出した 確かWeb魚拓は取っといたはずだけど どこいっちゃたｔかな 418 名前：デフォルトの名無しさん [2007/07/11(水) 01:16:28 ] 【総連】「安倍一味には負けない」総連弾圧に対して措置取る…朝鮮外務省代弁人声明 ttp://news21.2ch.net/test/read.cgi/news4plus/1183572310/l50 419 名前：・∀・）っ-○◎● mailto:sage [2007/07/11(水) 01:22:51 ] >>406 斉藤君に連絡とってみるかな。 個人的にはSSE2非対応CPU向けにMMX版くらいは欲しいんだが。 本人が動いてくれるくれないにかかわらず、SSE2版だけならVC8/ICC用の クラスを作ってみようと思うが。どうせ俺が使うし。 420 名前：デフォルトの名無しさん [2007/07/11(水) 01:28:04 ] で、SCEからオファーはきたの？ 421 名前：・∀・）っ-○◎● mailto:sage [2007/07/11(水) 01:34:19 ] 音沙汰無いよ 422 名前：・∀・）っ-○◎● mailto:sage [2007/07/11(水) 01:59:55 ] Cスタイルのコーディングってさ、どうしてグローバル変数汚染しようとするのかねぇ。 スレッド毎にインスタンス生成すればスレッドセーフうめぇｗｗｗｗ 423 名前：デフォルトの名無しさん mailto:sage [2007/07/11(水) 02:17:06 ] スタックに作ればいいやん 424 名前：・∀・）っ-○◎● mailto:sage [2007/07/11(水) 07:26:20 ] たとえばさ、MTのgenrand()を複数のスレッドから参照してみてごらん。必ずおかしなことがおきます。 BoostのRNGは全部クラス化してあって一時計算領域もインスタンス毎に生成するからスレッドセーフなのよ 425 名前：デフォルトの名無しさん mailto:sage [2007/07/11(水) 07:55:00 ] 乱数生成ルーチンがバグってて出鱈目な値を返していても誰も気がつかない罠 426 名前：デフォルトの名無しさん mailto:sage [2007/07/12(木) 08:19:10 ] 内部ベクトルでかいんだから、ミューテックスのがよくね？ 427 名前：デフォルトの名無しさん [2007/07/12(木) 21:44:58 ] おいおい19937ビット＋αだぜ？ 428 名前：デフォルトの名無しさん mailto:sage [2007/07/12(木) 22:28:42 ] TLS使えばしまいだろ 429 名前：デフォルトの名無しさん mailto:sage [2007/07/12(木) 22:36:08 ] >>428は>>422宛ね 430 名前：デフォルトの名無しさん mailto:sage [2007/07/12(木) 23:29:54 ] TLSとは何か。 Transport Layer Security Thread Local Storage True Love Story いろいろあるんだな…… 431 名前：デフォルトの名無しさん mailto:sage [2007/07/13(金) 02:11:06 ] いや、内部ステートをスレッド毎に持つというのは 確かに複数スレッドからの同時アクセスの点では良いのだが 例えばよく使われるsrand()はどうするのか。 スレッド毎にsrand()を呼ぶのか あるいはsrand()の内部でスレッドを数え上げるのか srand(time(NULL))の後にスレッドを作成したらどうなるのか ↑を最初に一度だけ呼んである過去のコードの扱いはどうなるのか 等々、面倒くさいことがありすぎるよ。 まともなコードで、srand()を呼ばずにrand()を使っているものがあるとは思えないし。 もちろん、「標準のrand()」を置き換えるのではなく 「自分で使う乱数生成器」をどうするか、という話なら 好きなようにどうぞ、というだけだけど。 432 名前：・∀・）っ-○◎● mailto:sage [2007/07/13(金) 03:11:46 ] そりゃ各スレッド毎にパラメータがあるわけだから、それぞれに初期化が必要になるだろうね。 種は現在時間＋スレッドID＋GUID/UUID＋HDDシークタイムからとった自然乱数もどき＋・・・・ 見たいな感じでいろいろ組み合わせればよくね？ 最近のMTの派生実装は種を配列で与えることができるんで、ユニークな乱数列になるように なるべく多くのパラメータを与えるといい。 MTは種さえ被らせなきゃそこそこうまくバラけてくれる。 433 名前：デフォルトの名無しさん [2007/07/13(金) 08:20:03 ] CryptGenRandは？ 434 名前：デフォルトの名無しさん mailto:sage [2007/07/13(金) 09:29:57 ] そういう話かよ？ 435 名前：デフォルトの名無しさん mailto:sage [2007/07/13(金) 12:42:16 ] ワークメモリがスレッド毎に独立してると、たとえばモンテカルロみたいなのを複数スレッドで分割処理やりたいときに有用。 プロセスを分ければいいと言われると返す言葉がないがね。 436 名前：デフォルトの名無しさん mailto:sage [2007/07/13(金) 22:15:41 ] >>386 亀レス double 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); 437 名前：デフォルトの名無しさん mailto:sage [2007/07/16(月) 21:40:05 ] CryptGenRandomって自分じゃジェネレートしてないのに、なんでGenRandomなんだ？ GetRandomじゃないのか？ 438 名前：デフォルトの名無しさん mailto:sage [2007/07/17(火) 19:01:44 ] その Gen は Generate ではなく、元、つまり集合の1要素だって おじいちゃんがゆってた。 439 名前：デフォルトの名無しさん mailto:sage [2007/07/18(水) 00:24:49 ] 「源」じゃないの？ すなわち「おじいちゃんの名前（ゲンじいちゃん）」 え？ちがう？ 440 名前：デフォルトの名無しさん mailto:sage [2007/07/18(水) 00:29:36 ] ﾗﾗ… わしゃ悔しいわい 441 名前：デフォルトの名無しさん mailto:sage [2007/07/18(水) 14:32:34 ] アゴなしの人か。 442 名前：デフォルトの名無しさん mailto:sage [2007/07/19(木) 22:22:22 ] ＤＤＡで円の軌跡を計算して、それを２重にして乱数作ったんだが、 擬似乱数として性能がいいのか調べる方法はある？１から１０までの分布は それらしくなっているんだけどな。 443 名前：・∀・）っ-○◎● mailto:sage [2007/07/19(木) 23:57:25 ] だんごやさんはSSE2用sfmtをboostに移植しようとしたがテンプレート地獄に涙目 444 名前：デフォルトの名無しさん mailto:sage [2007/07/20(金) 13:54:11 ] ビット毎の出現確率でも調べたら？ 445 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 07:35:38 ] >>442 どっかに基準とはる判定方法があったかも 446 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 09:09:19 ] とりあえず、こんなのは見つかった。 DieHarder: A Random Number Test Suite Robert G. Brown's General Tools Page www.phy.duke.edu/~rgb/General/dieharder.php 447 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 19:11:11 ] >>446 乱数検定の定番だな 448 名前：デフォルトの名無しさん [2007/08/15(水) 00:44:29 ] いろんな圧縮アルゴリズムにかけて 圧縮率を見るのってどうなの？ 邪道？

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef