擬似乱数

1 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:19:35 ] 擬似乱数発生器について語ろうか。 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 連続起動時間とそうたいして変わらんと思う

---

---

[ 続きを読む ] / [ 携帯版 ]

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