擬似乱数 - 暇つぶし2ch

擬似乱数 at TECH

1:デフォルトの名無しさん
06/04/27 02:19:35
擬似乱数発生器について語ろうか。

2:デフォルトの名無しさん
06/04/27 02:21:19
n * 1103515245 + 12345 mod 2147483647

3:デフォルトの名無しさん
06/04/27 02:26:29
LD A, R

4:デフォルトの名無しさん
06/04/27 02:35:58
>>2は
n * 1103515245 + 12345 mod 2147483648
の間違い

5:デフォルトの名無しさん
06/04/27 02:39:25
*(char *)(0xFFBC0161)

6:デフォルトの名無しさん
06/04/27 03:00:43
MT

7:デフォルトの名無しさん
06/04/27 05:52:27
では手始めに、メルセンヌツイスタの荒探しの話題から頼む。

8:デフォルトの名無しさん
06/04/27 06:28:13
数学板
乱数スレ
ｽﾚﾘﾝｸ(math板)

電気電子板
【疑似】乱数をつくる【本物】
ｽﾚﾘﾝｸ(denki板)

シミュ板
乱数
ｽﾚﾘﾝｸ(sim板)

9:デフォルトの名無しさん
06/04/27 14:29:10
ここはム板らしく、あら捜しよりも高速化とか考えた方がいいんじゃない？

10:デフォルトの名無しさん
06/04/27 15:42:25
暗号通信用に擬似乱数生成専用チップがあるようだが

11:デフォルトの名無しさん
06/04/28 11:56:29
ではその仕組みについて講義してくれ

12:デフォルトの名無しさん
06/04/28 14:01:30
擬似乱数ではないが
URLﾘﾝｸ(www.toshiba.co.jp)
URLﾘﾝｸ(www.internix.co.jp)
URLﾘﾝｸ(www.hmi-jp.com)

13:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/04/28 18:39:05
ゲーム用ライブラリとかで、mt19937.cがほとんどそのまま使われているのを見ると
「お前本当に分かっててその乱数発生器を薦めているのか？」と言いたくなる。

15:デフォルトの名無しさん
06/04/28 23:12:59
>>7
>では手始めに、メルセンヌツイスタの荒探しの話題から頼む。　

でかい、重い。

大体、普通の用途でここまで乱数性に拘る場面はそうそうない
（だから喧嘩を売られた　knuth　もスルーした）。

16:デフォルトの名無しさん
06/04/28 23:42:09
でかいは同意だが、そんな重いか？

17:デフォルトの名無しさん
06/04/28 23:47:00
あーでも初期化は重いかな。ほとんどハッシュ関数だよね、あれ。

まあ周期長いから頻繁に初期化するような使い方はしないが。

18:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/04/29 00:09:50
つか、速くてランダムなやつとなると
やっぱりどれもハッシュ関数みたくなるのな。

20:デフォルトの名無しさん
06/04/29 00:10:17
パチンコで勝つためはどのような乱数をシミュレートすればいいのですか

21:デフォルトの名無しさん
06/04/29 00:12:53
脳内乱数

22:デフォルトの名無しさん
06/04/29 01:01:05
ゲーム用途なら、そこそこ均等に出てくれれば精度自体は8ビットぐらいでも問題ないよな。

23:デフォルトの名無しさん
06/04/29 01:02:49
つうかMTは本家サイト自身が「モンテカルロ法シミュレーションのための擬似乱数」って言ってなかったか？
均等な乱数が超大量に必要な場合に使う、みたいな。

24:デフォルトの名無しさん
06/04/29 01:43:55
ここはまあまあ有意義なスレですね

25:デフォルトの名無しさん
06/04/29 04:20:02
ゲームで言えば、１フレームに数百から数万（雨とかパーティクル）なら線形合同法で十分だろう。
プログラマーには見えても、ユーザーには周期性は見えないよ。

１フレーム数回以下なら、必要なら重くても高品質なほうがいいんじゃない？
AI とか、ランダムダンジョンとか。

26:デフォルトの名無しさん
06/04/29 07:30:18
>>18それ、まともにM系列のが

27:デフォルトの名無しさん
06/04/29 20:33:09
でも、正直な話、現実での　MT　の用途の割合なんて

　1.ゲームプログラマの自己満足の為：86%

　2.汎用のライブラリが乱数生成関数として
　MT　を採用しているから、いつの間にか使っている：10%

　3.本来のシミュレーション用に使用:3%

　4.その他：1%

位だと思う。

28:デフォルトの名無しさん
06/04/30 15:17:30
WELLについて調べようとおもったんだけど……
ぐぐっても"well"なんて単語としてありきたりすぎて
関係ないページがヒットしまくりなんだが。
作者的には「より良い」と語呂合わせしたつもりなんだろうが、
いまや情報化社会。物にはなるべく一般的な語とかぶらないような名称をつけて頂きたい。

29:デフォルトの名無しさん
06/04/30 22:18:10
ゲーム用で再現性無くていいなら、時間とユーザーの入力
（その時しかありえないようなPCの状態）を混ぜりゃほぼ
ランダムになる。

30:デフォルトの名無しさん
06/04/30 22:23:18
>>29
その必要も無いのに、
テスト項目に「時間」と「ユーザーの入力」の要素が
入るような実装は、極力避けるべき。

テストの自動化が出来ない。　

31:デフォルトの名無しさん
06/04/30 22:31:53
SSL の証明書作るときのシードにキー入力使ってたな。

32:デフォルトの名無しさん
06/05/03 15:09:15
インターネットを利用したランダム関数できないかな？

33:デフォルトの名無しさん
06/05/03 18:20:08
>>32
パケットが通過する間隔はポアソン分布に従う、とかそういうのを利用するのか？

34:デフォルトの名無しさん
06/05/03 18:58:42
２ちゃんねるを利用したランダム関数欲しい

35:デフォルトの名無しさん
06/05/03 21:02:28
>>18
これ確かに早いけど、種を選ぶのが難点だね。
128ビットで、そこそこ0と1が混じってないと駄目ってのが。
種用に物理乱数とか、遅くても質のいい乱数発生器を別個に使う必要があるなあ

36:デフォルトの名無しさん
06/05/04 00:41:36
>>13
あと、初期化が糞だよねぇ。そのせいでかなり癖のある乱数列が生成される。理論台無し。

37:デフォルトの名無しさん
06/05/04 08:02:03
まあ初期化ルーチンに関しては他の乱数生成関数とかハッシュ関数とか組み込めばええんでない？
xorgensでもMTでもどの擬似乱数でも言えることだけど。

38:デフォルトの名無しさん
06/05/04 08:09:30
MTの初期化ルーチンをそのまま使うときは最初の100万個ぐらいは読み飛ばしたほうがいいらしい。

39:デフォルトの名無しさん
06/05/04 08:14:57
100万の根拠は？

40:デフォルトの名無しさん
06/05/04 08:26:44
統計的としか言いようが無い。
50万とか70万とかいうデータもあるが

41:デフォルトの名無しさん
06/05/04 08:37:49
正確には681,1573個だ。

42:デフォルトの名無しさん
06/05/04 08:51:13
要するにマンコ

43:デフォルトの名無しさん
06/05/04 09:36:18
>>30
再現性がなくなるだけで、時間を加味していればテストは自動化できるだろ。
話それるがユーザー入力だって、ある程度自動化するし。
>>32 >>33>34
全部ユーザー入力と一緒じゃね

44:デフォルトの名無しさん
06/05/04 10:57:54
>>38
はつみみなのでソースおせーて

45:デフォルトの名無しさん
06/05/04 12:31:25
初期化が糞な場合、MTみたいに周期がアホみたいに長い疑似乱数はその程度
読み飛ばすだけで癖が抜けるとは思えんのだが。

46:デフォルトの名無しさん
06/05/04 12:51:05
>>40
その統計の在処をぜひ

47:デフォルトの名無しさん
06/05/04 14:23:52
じゃあみんなで初期化関数考えようぜ。
（新しい擬似乱数考えるのと同じになりそうだが）

48:デフォルトの名無しさん
06/05/04 14:37:16
>>47
そんなの Windows なら CryptGenRandom 、Unix系なら /dev/urandom を使う・・・てのが常識では？

49:デフォルトの名無しさん
06/05/04 15:30:21
MD5だっけ？
まあ暗号用に使うんじゃなくてあくまで擬似乱数用の種だからCRCとかでもいいような希ガス

50:デフォルトの名無しさん
06/05/04 16:47:54
どうでもいいならシステムタイマー使えばいいし
厳密にやりたきゃ>>48の使えばいいし。

51:デフォルトの名無しさん
06/05/04 19:56:01
結局、MT　厨は、そのネームバリューを闇雲に信じるだけで、
自分で乱数性の検証はしていなかったんだな。

52:デフォルトの名無しさん
06/05/05 18:18:49
>>51
当たり前だろｗ
偉い人が使えるって言えば使うだけ

53:デフォルトの名無しさん
06/05/05 18:25:54
Ｍ系列乱数と、線形合同法の結果をXORして使えば

Ｍ系列が2^127-1の周期で線形合同法が2^32の周期だから　合成周期は掛け算でいいんだよな？

54:デフォルトの名無しさん
06/05/05 19:59:17
>>51
それが厨の厨たる所以。

>>53
ヒント指数は掛け算が足し算。
つまり合成周期は2^159弱ってこった。

55:デフォルトの名無しさん
06/05/05 20:47:20
Ｍ系列乱数と、線形合同法の結果をXORした場合、
簡単に種を見つけるアルゴリズムはあるのだろうか？

56:デフォルトの名無しさん
06/05/06 15:07:25
総当たりが一番簡単だ。

57:デフォルトの名無しさん
06/05/06 18:27:20
>>55の言う「簡単」はそういう意味じゃないと思われ

58:デフォルトの名無しさん
06/05/06 19:05:50
もし総当りしかないのなら暗号に使えないかな

59:デフォルトの名無しさん
06/05/06 19:51:45
ワンタイムパッドとしてなら

60:SOURCE ◆tAo.kQ2STk
06/05/06 20:53:53
>>55
両方の式を満たすような特殊な式があればいくらでも出来そうなｷｶﾞｽ。
線形合同法は離散対数とかの扱いが面倒だが？

>>56
総当りすればいつかは解けるけどさ、現実的な時間内で2^159弱ある鍵空間を全て試せるのか？
2^159≒10^47*7.3
一秒間に10^39回強のスピードで当たれるとして23年ほどかかるぞよ。

>>58
それは正しいけど、総当り以外に破る方法が存在しない事を証明する事は難しいとオモフ。

61:デフォルトの名無しさん
06/05/07 12:15:43
証明されてなくても多分大丈夫だろうって使われてるのはあるな

62:デフォルトの名無しさん
06/05/07 13:19:27
証明できるくらいまで研究が進む頃には、
総当たりで簡単に種を探せるようなスペックのマシンが動いている気がする。

63:デフォルトの名無しさん
06/05/07 13:38:43
>>62
光の速度を考えると、本当にそんなマシンが出来ると思う？

64:デフォルトの名無しさん
06/05/07 14:34:54
量子論的重ねあわせがどうこう

65:デフォルトの名無しさん
06/05/07 14:44:58
>>64
この場合、全部の組み合わせを検索しなければならないのだとしたら
まず全部の組み合わせをどこかに入れておく必要があるんじゃないの？
そうすると物理的に不可能でしょ

66:デフォルトの名無しさん
06/05/09 00:29:21
>>10
半導体中の熱電子の揺らぎを使った、
熱的乱数発生モジュールを売っているベンチャーもある。
もう数年前の話だけど。

67:デフォルトの名無しさん
06/05/11 00:56:09
>>65
一つの量子に複数の状態を重ね合わせることが出来るので
理論上はあらゆる組み合わせを一箇所に保管できるようになる。
現在の技術では4状態で実験に成功したそうだｗ先は長い……

68:1つ、二つ、おっぱい。
06/05/11 22:14:09
> 一つの量子に複数の状態を重ね合わせることが出来るので
　～～～～～～～～
> 理論上はあらゆる組み合わせを一箇所に保管できるようになる。
　　　　　　　～～～～～～～～～～～～～　

後半ダウト。
「複数＝あらゆる」って、おまいは大きな数を数えられない未開人ですか？

69:デフォルトの名無しさん
06/05/12 04:36:31
別に間違っていないが。

70:デフォルトの名無しさん
06/05/13 10:13:33
また開き直りか。

71:デフォルトの名無しさん
06/05/14 08:48:58
考える問題において可能なあらゆる状態数がＮのとき
一個の量子ビットにＮ個の状態を重ね合わせる量子アルゴリズムを使うなら
別におかしくないね

72:デフォルトの名無しさん
06/05/14 10:29:03
言い訳乙ｗ

頭悪すぎ

73:デフォルトの名無しさん
06/05/14 10:34:05
おまぃの「理論」とやらでは、
量子と周囲とのインタラクションを完全遮断して、
かつ、その量子に任意個数の状態を保持可能なのかｗｗｗ

ずいぶん貧弱な理論だなｗｗｗ想像力が足りないというかｗｗｗ基礎知識がない素人の発言は怖いというかｗｗｗ

74:デフォルトの名無しさん
06/05/14 10:48:20
というより　
検索が高速だとしても、
1万なら1万通りの状態を一瞬で作る方法があるのか？
あるなら、既にその問題は解けてるわけじゃないのか？

75:71
06/05/14 11:07:33
>>67でも>>69でもないですが、おいらはShorの素因数分解アルゴリズムのことを言ったんだけど

＞かつ、その量子に任意個数の状態を保持可能なのか

一体何の話？

76:71
06/05/14 11:09:49
あ、>>62からの流れだったんですね
すいません

77:デフォルトの名無しさん
06/05/14 11:23:40
＞考える問題において可能なあらゆる状態数がＮのとき
＞一個の量子ビットにＮ個の状態を重ね合わせる

とか言ってる時点で素人モロバレ

78:71
06/05/14 11:31:16
>>77
あ、ほんとだ
一個のqubitに格納する状態の数はＮ個じゃなかった
うろ覚えですいません

79:デフォルトの名無しさん
06/05/14 17:12:03
>>66
それって周囲の温度によって乱数変わったりしない？

80:デフォルトの名無しさん
06/05/14 17:13:20
アメリカの暗号乱数発生チップには諜報機関の権限でバックドアが仕掛けられているという話だが…

81:デフォルトの名無しさん
06/05/14 18:25:00
>>18これって普通にソースに組み込んで使ってもライセンスの問題無い？

82:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/05/16 07:51:37
>>82
よく見ろ、t の初期値は使われてないぞ。

84:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/05/16 12:12:56
ここには乱数に詳しい人はいない件

86:デフォルトの名無しさん
06/05/16 14:33:23
飯の種だし
こんなところにタダで書くわけにも

87:デフォルトの名無しさん
06/05/16 22:17:00
>>18
乱数全然わからんけど、
y,zはただのキャリアーでx,wの上下32bitを使うのね。
中間の64bitは使わなくてもいいの？
その方が出力が読みにくかったりする？

88:デフォルトの名無しさん
06/05/17 05:19:45
そんな単純な問題じゃない

89:デフォルトの名無しさん
06/05/17 06:36:50
>>87
よく見れ、種として機能している。

90:デフォルトの名無しさん
06/05/17 17:02:00
擬似乱数の種を得る方法には時刻以外にどんなものがある？

91:デフォルトの名無しさん
06/05/17 18:20:51
未初期化変数のゴミ値

92:デフォルトの名無しさん
06/05/17 20:48:26
マウスカーソルの座標

93:デフォルトの名無しさん
06/05/17 20:51:13
俺の場合、セキュリティ関係の用途じゃない時のデフォは[時刻＋プロセスID]。
セキュリティ関係の用途の時には >>48 。

94:デフォルトの名無しさん
06/05/17 21:32:34
サウンドカードからの入力(ノイズ)値

95:デフォルトの名無しさん
06/05/17 22:47:54
>>94
俺DTMやっててフルデジタル環境なのでサウンド入力は常時0になりますが……
もしかして俺の環境だとうまく乱数吐かないソフトあるんかな？

96:デフォルトの名無しさん
06/05/17 23:28:26
>>91
それ、ほとんど毎回同じになるだろ。

97:デフォルトの名無しさん
06/05/18 00:42:15
連続起動時間
CPU稼働率
メモリ使用率
メモリキャッシュ量
HD容量+使用率

98:デフォルトの名無しさん
06/05/18 01:46:47
素直に>>48使おうよ…

99:デフォルトの名無しさん
06/05/18 17:28:17
CryptGenRandomは失敗する環境があるから

100:デフォルトの名無しさん
06/05/18 17:35:53
１００

101:デフォルトの名無しさん
06/05/18 18:28:39
>>94
そういやファミコンはアナログ信号ピンがあってカートリッジ側でそいつを読めたんだっけ？
それを乱数に使ったゲームは知らないが。

102:デフォルトの名無しさん
06/05/18 20:56:02
>>99
MSが標準で提供してるサービスプロバイダを選んでちゃんとした初期化をすれば、失敗する環境なんてないだろ？

...俺も、以前はヘタレなコードを書いて環境よっては失敗するからなんでだろう？
と悩んでたけど初期化コードの問題だったぞ。(状態によって初期化方法を変える必要がある。)

103:デフォルトの名無しさん
06/05/18 21:01:00
>>90
そういえば、Z80のアセンブラとかではリフレッシュレジスタ(※)の値を利用するなんて話もあったなぁ。

※昔のメモリシステムの名残で、メモリの内容が揮発しないように定期的にリフレッシュするのに
　使われたレジスタ。どこのメモリブロックをリフレッシュするべきかを指し示して高速にその値が循環する。

104:デフォルトの名無しさん
06/05/18 21:04:34
>>103
>>3

105:デフォルトの名無しさん
06/05/18 21:05:41
>>103
連続起動時間とそうたいして変わらんと思う

106:デフォルトの名無しさん
06/05/18 21:14:18
たしか3ビットだか4ビットぐらいしかなかったような気がする＞リフレッシュレジスタ

107:デフォルトの名無しさん
06/05/18 23:11:51
>>106
7ビットだよ。
しかし互換CPUでは全く変化しないこともある罠。

108:デフォルトの名無しさん
06/05/20 18:47:53
ところで、乱数性を評価する方の話はどうなのよ
URLﾘﾝｸ(csrc.nist.gov)
とかさ

109:デフォルトの名無しさん
06/05/20 19:38:12
>>108
俺は乱数を自作したりその乱数性を評価するときにはその評価対象の乱数である程度のサイズの
乱数列を生成しそれをそのままファイルとして保存し、ファイルの圧縮プログラムを使ってその結果
の圧縮率が悪いほどエントロピーが高い良い乱数として評価してる。俺的にはこの方法はお手軽で
且つかなり有効なテストの方法だと思ってるんだけど、ちょっと他人の意見を聞いてみたい。

所謂「後出し」にならないように付け加えておくと、俺はこの評価方法は飽くまでエントロピーの高さを
計るものであって真性乱数性を計るものではないと自覚している。真性乱数性はその特性上
(まともな)評価方法は存在しないものと思ってる。( だって、ずっと同じ値を吐き続けたって真性乱数
の場合はアリってされるんだから、そんなもん評価のしようがない。 )

ちなみに俺はこのスレでMTに癖があるって言い出したヤツだけど、
それはこの方法による評価でMTで生成した乱数列の圧縮率がよかったから。

110:デフォルトの名無しさん
06/05/20 21:36:02
おいおい、エントロピーが高いってことはその範囲でのビットの出現回数に
偏りがないって事だろ。
MTほどの長い周期であれば部分的に偏りが生じる区間があるのは当然じゃない。
重要なのはその区間から次の区間を予測できないことな訳だ。
むしろ、いつどの区間を見ても偏りがないのなら短い周期しかもっていないことになる。

高々数MB、数GB程度のサイズじゃ乱数性は測れないよ。
試しに普通の線形合同法で乱数を生成してみれば分かる。
普通に圧縮できないから。
下位ビットは使うなよ。

111:デフォルトの名無しさん
06/05/20 21:48:45
>>110
おまい、ちゃんとわかってる？　ちゃんと実測した？

俺はMTの理論に問題があるなんて言ってない。初期化が糞だって言っただけ。
MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、
線形合同法なんかだと下位ビット捨てても圧縮率はいいぞ。

112:デフォルトの名無しさん
06/05/20 21:50:44
>>111
> MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、
それって、 MT には何にも問題ないってことだよな？

113:デフォルトの名無しさん
06/05/20 22:20:49
圧縮についてなんか知っててそんなこと言ってるのか？
圧縮ソフトが何やってるのか調べた方がいいぞ。

114:デフォルトの名無しさん
06/05/20 22:26:01
>>112
そだよ。だけど、極端な話すると100万回やっても同じ値を吐き続けるとってもあほみたいに周期の長い乱数と
100万回で一週しちゃうんだけどその間のエントロピーは文句なしの乱数のどっちが実用的だと思う？
少なくともあの実装のMTではモンテカルロ法に利用すんのも止めといたほうがいいぞ。

115:デフォルトの名無しさん
06/05/20 22:27:42
>>113
そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。
だからこそ、他人の意見を聞きたい。

116:デフォルトの名無しさん
06/05/21 08:53:55
辞書サイズよりも大きい周期で同じデータを吐き出しても圧縮率は変化しないよね

117:デフォルトの名無しさん
06/05/21 09:25:46
>>116
にも関わらず、MTや線形合同法では圧縮率がいいんですよ。

てか、他の優れた評価方法とかないの？
俺も多少は乱数性の評価方法とか調べたけどあまりにもしょぼいしのか見つからなくてよー
たとえ例えハックにも過ぎなくても、これじゃ圧縮を利用したほうが断然いいじゃん・・・て、今んとこ結論してるわけよ。

118:デフォルトの名無しさん
06/05/21 10:49:31
>>111
>おまい、ちゃんとわかってる？　ちゃんと実測した？
実測データｷﾎﾞﾝﾇ

119:デフォルトの名無しさん
06/05/21 14:52:24
>>118
俺も記録をちゃんと残してたわけじゃないから、精確な情報じゃないけど
数十MB規模のデータでMTの場合、だいたい圧縮率が90%代後半で
線形合同法だと圧縮率が80%代後半だった。
ちなみに俺が自作したヤツやMTでも初期化をちゃんとしたヤツだと
圧縮率は100±1%ぐらいだった。

↑これは記憶を元に書いたんで多少間違ってるかもしれん。
精確なデータが欲しかったら自分で実測すれ。
あと俺が試した圧縮アルゴリズムはLZHとZIP。この二つはアルゴリズムが
かなり似てるから本当はもっといろんなアルゴリズムで比較したほうが
いいんだろうけど俺はそこまではやってない。

# 当然だけど、LZHとZIPではほとんど圧縮率に差がでなかった。

120:デフォルトの名無しさん
06/05/21 15:33:55
他の圧縮やってみたら全然結果が違ったらどうする。

121:デフォルトの名無しさん
06/05/21 15:39:52
>>120
別にどうもしないけど。圧縮アルゴリズムが違えば結果も異なるのは当たり前。
しいて言うなら評価をする為の圧縮アルゴリズムのひとつとして採用するだけ。

122:デフォルトの名無しさん
06/05/21 15:44:50
てか、ちゃんとした知識を持ってて、理論に基づいてどーこー言えるヤツはおらんのか？
俺自身も知識よりは閃きの人間だから、知識のないヤツは黙ってろとかは思わないが、
できれば知識を持ってる人間の意見を聞きたい。

123:デフォルトの名無しさん
06/05/21 15:53:05
断る

124:デフォルトの名無しさん
06/05/21 15:58:02
>>123
そんなこと言わないで、頼むよ～

125:デフォルトの名無しさん
06/05/21 17:11:27
1,2,3,・・・というデータはハフマン圧縮ではまったく圧縮できないがランダム性はない

126:デフォルトの名無しさん
06/05/21 17:32:09
>>125
そこまでテキトーなこと抜かすなよ。
ちょっとバイナリでの表現がどうなるか考えりゃ、圧縮できることぐらいわかんだろ。
せめてもうちゃっと考えてから書き込んでくれ、な？

127:デフォルトの名無しさん
06/05/21 17:51:37
>>126
いや循環し続けるデータなら　ハフマンでは圧縮出来ないのは正しいだろ
ただ、差分をとれば途端に圧縮出来るのだが

128:デフォルトの名無しさん
06/05/21 17:58:04
まずはランダム性を定義しろ

129:デフォルトの名無しさん
06/05/21 18:30:55
>>127
理論ベースで言えば確かに >>125 が言わんとすることもわからんでもないが
実装ベースで考えれば >>125 の言う理論は途端に破綻する。
>>125 があげたようなデータを 8bit 表記にすればたかだか256バイトで循環するデータになるし
32bit 表記にすれば上位bitが圧縮可能なデータ群と可す。

が、bit幅可変長表記にすれば、確かに少なくともbit幅固定表記に比べ圧縮し難いデータには
なるだろう。しかし、それはランダム性がないデータと言えるか？　これをランダム性のないデータ
だと言うヤツがいても、俺はそれを否定しないが、これがランダム性のないデータとするならあら
ゆる疑似乱数もランダム性がないものと評価するべきだろう。

>>128
ランダム性の定義ではないが、
圧縮アルゴリズムによる評価目的はエントロピーの高さを測ること。

130:デフォルトの名無しさん
06/05/21 18:37:41
>>125
付け加えておくと、それはもっとも簡単な疑似乱数列だぞ。

131:デフォルトの名無しさん
06/05/21 18:43:47
>>129
1,2,3,・・・,2^32までのデータを使えば32bit表記では各ビットパターンは一回ずつ登場する事になるぞ

132:デフォルトの名無しさん
06/05/21 19:15:14
>>131
それでも圧縮は可能だろうが。

やっぱり、こんなとこでまともな意見を求めた俺がバカだったか。
こんなやりとり続けても時間の無駄だしもっと生産的なことに時間をつかうよ。じゃぁな。ﾉｼ

133:デフォルトの名無しさん
06/05/21 19:21:20
>>115
>そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。　
それは唯のハックでは無いだろ？
むしろ、コルモゴロフの定義に忠実すぎるぐらいだ。

ちなみに俺も同じ方法で別のものを評価していたりする。

それはソースコード。
圧縮率が高いコードは間違いなく糞コードだったりする。

圧縮後のファイルサイズは、いわゆるステップ数なんかよりも、
ずっとよい指標になる。

134:デフォルトの名無しさん
06/05/21 19:30:37
>>133
基準はどれぐらい？
テキストなんでだいたい 20% ぐらいになるのも普通かと思うんだが。

135:デフォルトの名無しさん
06/05/21 19:36:20
ところで、折角　>>108　が　NIST　の乱数検定器を挙げているのに
その実行結果について議論をするどころか、

>>117
>てか、他の優れた評価方法とかないの？　
>俺も多少は乱数性の評価方法とか調べたけどあまりにもしょぼいしのか見つからなくてよー　

とかぬかしている件について、どうよ？

136:デフォルトの名無しさん
06/05/21 19:41:20
>>134
むしろ圧縮後のサイズがポイントだな。
圧縮した後のファイルサイズで、
「このアプリは、この程度の規模の複雑さを持っているんだな」
ってのが、意外に分かると思う。

137:デフォルトの名無しさん
06/05/21 20:01:01
>>132
圧縮云々を言うならせめて情報理論ぐらい勉強しろよ・・・

138:デフォルトの名無しさん
06/05/21 20:06:51
>>136
コメントに日記が書かれていても複雑なプログラムなのかw

139:デフォルトの名無しさん
06/05/21 20:33:04
>138
で？何？

140:デフォルトの名無しさん
06/05/21 21:38:44
バカばっか

141:デフォルトの名無しさん
06/05/22 00:21:49
データ列を圧縮してその圧縮率がどう、ってのはシャノン情報量を見てるんだよね？

>>114
>そだよ。だけど、極端な話すると100万回やっても同じ値を吐き続けるとってもあほみたいに周期の長い乱数と
>100万回で一週しちゃうんだけどその間のエントロピーは文句なしの乱数のどっちが実用的だと思う？
確かに。
「100万ビットでも同じ値が続いてくれることがありえないと困る」ような乱数の使用法をしてるか否か、ってことだよね。
ゲーム用途なら下位ビットが最悪のrand()の方が人間相手には『確実にランダムっぽく』見える分有利かもしれないな。
でもそれはつまるところ、人間の持つ「ランダムさ」の感覚が
シャノン情報量の大小と一致していないところに問題があるわけだよね。
だから、マジで何万回も同じ値が出続けるかもしれないサイコロ振りより、例えばM系列の方が喜ばれたりする。
難しいねえ。

142:・∀・）っ-○◎● ◆toBASh....
06/05/22 00:31:35 BE:752619896-#
１００万回同じ値を吐くという状況を再現できんのだが、何が問題なのかサパーリ
俺はboost::random::mt19937使ってる

143:デフォルトの名無しさん
06/05/22 00:37:45
>>142
そりゃー32bitの乱数なら100万回同じ値になる確率は1/((2^32)^999999)なんだから
そうそう簡単に再現されるわけ無いじゃん。

144:デフォルトの名無しさん
06/05/22 00:39:24
で、そうそう再現されない状況なんだから、
「はじめっからそんな値を吐かないアルゴリズムでも問題ないよな？」
という考え方で、もっと短周期の乱数アルゴリズムが『実用的』とみなされている。
ってこと。

145:デフォルトの名無しさん
06/05/22 00:42:00
boostのMTはあんまり速度でなかったと思われ。
同じ使うにしても本家サイトで公開されてる「高速化版」に差し替えた方がいいかも。
（乱数生成アルゴリズムを入れ替えできて、同じインターフェースを提供、ってのがboostのいいところだしな）

146:デフォルトの名無しさん
06/05/22 00:43:17
池沼としか思えんｗ

147:デフォルトの名無しさん
06/05/22 00:46:42
いけぬまで悪かったな！これでも頑張って勉強中の身なんだ……

148:デフォルトの名無しさん
06/05/22 04:08:13
このスレ見てて思ったんだが、乱数がどういうものかっていう理解度が人によってかなりまちまちなんだけど、
理解度が低い側の人が自分自身の理解度が低いということすらが自覚してなさげだね。

最低限↓このページの最初に書かれていることぐらいは理解したうえで議論すべきだと思うけど。
Wikipedia項目ﾘﾝｸ

149:デフォルトの名無しさん
06/05/23 18:43:51
「ｽﾚが急激に伸びる時は大抵、池沼が書き込んでいる」

150:デフォルトの名無しさん
06/05/23 18:45:47
↓↑
└┘　そうだね

151:デフォルトの名無しさん
06/05/25 21:30:16
また池沼が寄ってきた

152:デフォルトの名無しさん
06/05/25 21:42:01
おかえり池沼くんｗ

153:デフォルトの名無しさん
06/05/31 02:33:35
なあMTよりもうちょっと周期短くていいからベクトル数すくない乱数ないの？

154:デフォルトの名無しさん
06/05/31 21:39:14
AESやtwofish 等のブロック暗号の結果を使うと、エントロピーという面では良い？
ちなみに、暗号化した結果をさらに暗号化して、次の乱数を出していくような形だと、悪い性質が出てきたりするのかな？

155:デフォルトの名無しさん
06/05/31 22:23:43
それOutput-FeedBackって奴じゃん。

じゃなくって、生成器Aで作った乱数列を鍵にして生成器Bで乱数列を作る、ってこと？

156:デフォルトの名無しさん
06/05/31 22:50:20
XORすべき平文はないけれど、それも OFB って言っていいのかな？
そうであれば、たしかに OFBですね。

157:デフォルトの名無しさん
06/05/31 22:52:01
で、結局、まともなブロック暗号であれば、エントロピー的な意味では、
悪い性質が出てきたりはしない筈…ですかね？

158:デフォルトの名無しさん
06/06/01 00:25:28
>>156
全0の数列とXORして結果を得ていると考えればOFBの一種だな

159:デフォルトの名無しさん
06/06/01 00:26:39
>>157
その「まともな暗号」を考えるのがﾑﾂｶｼｲ

160:デフォルトの名無しさん
06/06/01 10:58:08
>>159
154で書いた通り、前提として、AESやtwofishを想定していますけれど。
暗号の世界の死屍累々の歴史を見れば、よほどでなければ俺様暗号を作ろうなんて傲慢な気持ちにはなれないですよね。
AES 選考のときも、ドイツテレコムが採用していた暗号が 10秒で即死したり、笑い話に事欠かない世界…怖いですね。
URLﾘﾝｸ(h2np.net)

161:デフォルトの名無しさん
06/06/01 13:58:02
>>160
ﾊｧﾊｧ読んでて興奮するね。

162:デフォルトの名無しさん
06/06/03 04:14:33
>>160
ｶｺｲｲ!!

163:デフォルトの名無しさん
06/06/03 05:16:05
>>160
最終的にAESに選ばれたのはそこで名前すら挙がっていなかったRijndaelだというのも
おもしろいな

164:デフォルトの名無しさん
06/06/05 00:58:00
高速な乱数の基本はシフトとXORを使うことらしいが
この二つってそんなに演算早いの？
加減算やローテートは遅い部類なの？

165:デフォルトの名無しさん
06/06/05 01:32:04
シフトとローテイトはCPUレベルではそんな変わらんと思うが

加減算は変わりそう

166:デフォルトの名無しさん
06/06/05 01:42:13
>>164
命令自体は別に変わらないよ。
M系列でググると分かるけど、
ある周期で全てのビットが0である場合を除いて、
全ての0と1の組み合わせが出現するアルゴリズムがある。
そんでそれはシフトとxorのみで実現する事が出来るというだけ。
これはなかなか自然的な乱数の性質に近くて、
しかもコンピューターに都合のいい形をしている。
で、よく使われる。
加減算やローテートでも実現出来るんじゃないかな。
ただ、周期を大きくするのが難しそうだ。

167:デフォルトの名無しさん
06/06/05 01:53:02
Pen4なら加減算が倍速でローテートはアホみたく遅い。
使用する環境が決まってるならCPUに特化した乱数ルーチンもアリだと思う。

168:デフォルトの名無しさん
06/06/06 17:33:17
>>167
そのために、RCなんとかコンテストで、PowerPC とかがクロックの割に健闘したりってことがあった気が。
そういえば、CPU自体が（熱雑音とかを使った？）乱数生成器を持っているやつって、あるのかな？

169:デフォルトの名無しさん
06/06/06 22:10:12
>>168
ぐぐったら出てきた
URLﾘﾝｸ(journal.mycom.co.jp)

170:デフォルトの名無しさん
06/06/07 10:40:12
こんなのも。どうやって使うのか知らないけれども。
URLﾘﾝｸ(www.intel.co.jp)
インテル 820 チップセットは～インテル(R) ランダム・ナンバ・ジェネレータ（乱数生成器）を搭載しています。

171:デフォルトの名無しさん
06/06/07 20:49:19
メルセンヌ・ツイスタをSSE2で高速に計算する方法を思いついた！！
でも…… ワーキングメモリが2.5倍強ほど必要になってしまう…
ただでさえデカイと評判のMTがさらにでかく…
くそっ、SSEに128ビットアライメント縛りなんてものがなければ……
せめて64ビット縛りならいいのに

172:デフォルトの名無しさん
06/06/07 21:37:59
PCで使うなら気にするこたねぇだろ
組み込みで使うならともかく

173:デフォルトの名無しさん
06/06/07 21:46:05
そだね。
SSE2使おうってCPUならキャッシュで収まるもんね。
気兼ねせず実装することにしますわ。

でもアライメント縛りって本当に鬱陶しいな。スレ違い愚痴ｽﾏｿ

174:デフォルトの名無しさん
06/06/07 23:20:13
ま、その前提で高速演算できますって機能だから仕方ない。
組み込み系だと日常茶飯事だけどｗ

175:デフォルトの名無しさん
06/06/11 14:44:38
「とってもごはん」のMMX版MTって、オリジナル版と出力違ってないか？

176:デフォルトの名無しさん
06/06/11 16:49:37
>>171
うｐはdvi形式でおｋ

177:デフォルトの名無しさん
06/06/11 17:06:53
>>175
オリジナルのMTも32bit版と64bit版で出力違うから気にしなくていいと思う

178:デフォルトの名無しさん
06/06/12 06:13:17
で、初期化がどーのこーのに難癖つけてた件は結局うやむやのうちに終了しちゃったの？

179:デフォルトの名無しさん
06/06/12 10:48:14

そもそも何で乱数に初期化が必要なんだ？

種から生成するアプローチ以外の方法は無いのか？

180:デフォルトの名無しさん
06/06/12 16:50:29
MT-32よりCM-64の方が面白いよ

181:デフォルトの名無しさん
06/06/12 18:19:34
ローランド音源かよｗ

182:デフォルトの名無しさん
06/06/12 18:21:24
>>178
心配なら暗号論的乱数で初期化汁、そこまで気にしないならどうでもいい、でFA出ちゃったからね。

183:デフォルトの名無しさん
06/06/12 18:57:12
線形合同法で十分

場合によっては

184:デフォルトの名無しさん
06/06/13 00:26:32
いけぬますれ

185:デフォルトの名無しさん
06/06/13 00:48:08
>>184
そんなこと言ってないでなにか話題提供してくれよ

186:デフォルトの名無しさん
06/06/13 03:09:15
擬似乱数について素人ですが、教えて頂けないでしょうか？

(0,1)の擬似乱数をMT19937（作成者のHPからFortranソースを拾ってきた）で発生させて、
その平均値と標準偏差が0.5と0.25になるのを確認しようとしました。
（作者の作成したサンプルデータと同じ結果がでることを確認しました。）
平均値は0.5にかなり近づくんですが、標準偏差が0.28程度になります。
乱数の個数を増やしていくと、0.28程度で収束しているように見えます。
octave（実装されてる乱数生成器）でもやってみたんですが、0.25程度に収束しません。

よろしくお願いします。

187:デフォルトの名無しさん
06/06/13 04:27:11
[0,1] の一様分布に従う擬似乱数の標準偏差が
1/sqrt(12) に収束するのは別に何もおかしいところが無いわけだが

乱数の話というよりか確率・統計の話だな

188:デフォルトの名無しさん
06/06/13 13:49:37
187さんへ
　ありがとうございます。
　たしかに、1/3-(1/2)**2でも0.288...になりました。
　0.25と思い込んでいました。

189:デフォルトの名無しさん
06/06/14 01:07:11
>>175
それ以前に、メルセンヌツイスタはBSDライセンスのはずなのに
ソースコード中にライセンスについて一切の記述がない事がまずいと思う。
SYN氏、忘れてんのか？

190:デフォルトの名無しさん
06/06/14 01:13:54
そーいや乱数発生器のライセンスってどうなってるんだ。
AESはフリーなんだっけ？

191:デフォルトの名無しさん
06/06/14 05:53:41
yes

192:デフォルトの名無しさん
06/06/14 21:52:44
Rijndaelだけ？他のは？

193:デフォルトの名無しさん
06/06/15 10:46:52
自分で調べろ

194:デフォルトの名無しさん
06/07/08 19:10:20
量子論的乱数発生器ってある？

195:デフォルトの名無しさん
06/07/08 22:27:59
Intelの最近のチップセットには内蔵されてるはず

196:デフォルトの名無しさん
06/07/09 02:16:37
詳細規模んう

197:デフォルトの名無しさん
06/07/09 08:39:00
なんでコンピュータは擬似乱数しか出せないの？

198:デフォルトの名無しさん
06/07/09 09:45:09
真性乱数も出せるだろ、専用のハードウェアがあれば。

199:デフォルトの名無しさん
06/07/09 12:52:06
>>197
決定性チューリングマシンだから。

ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか？

200:デフォルトの名無しさん
06/07/09 14:55:03
>>197
つ /dev/random

201:デフォルトの名無しさん
06/07/09 19:03:50
>>199
> ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか？
真性乱数は無理。

というか、非決定性チューリングマシンができてしまうと、
今まで暗号論的擬似乱数と呼んでいたものの前提が全て崩れちまうな。
Wikipedia項目ﾘﾝｸ

202:デフォルトの名無しさん
06/07/10 01:33:58
>>201
えっと、そんなことはないです、オーダー的に。デタラメ言わないで。

203:201
06/07/10 02:36:50
>>202
え、なんでだ?

非決定性チューリングマシンとはNP完全な問題を多項式時間で解くマシン、
すなわち、単純な総当たりで解くしかない(=解くには指数時間かかる)と思われていた問題を
多項式時間で解いてしまうことのできるマシンであるから、
RC4などストリーム暗号で使われる暗号論的擬似乱数列も多項式時間で解けちゃうでしょ。

204:デフォルトの名無しさん
06/07/10 21:01:48
どうでもいいがWikipediaを参考文献として引き合いに出すのは勘弁してくれｗ

俺が書いた文章だったりするからｗｗｗ

205:デフォルトの名無しさん
06/07/10 21:13:30
>>204
嘘書いたの？

206:デフォルトの名無しさん
06/07/11 06:52:21
自分の使ってる狭い専門用語を広めるのには便利かもしれないな。

207:デフォルトの名無しさん
06/07/11 13:35:06
>>109の方法をやってみたら
どの乱数列データもまったく圧縮できないorz

208:デフォルトの名無しさん
06/07/11 18:56:18
>>205
いやそういう意味じゃないが、非常に照れくさい……

209:デフォルトの名無しさん
06/07/19 03:02:36
ま、素人はそう考えるわな。

210:デフォルトの名無しさん
06/07/19 03:07:16
間違ってるけど

211:デフォルトの名無しさん
06/07/19 12:52:58
一様な乱数のお薦めを見繕ってくれ

212:デフォルトの名無しさん
06/07/19 13:08:01
MT

213:デフォルトの名無しさん
06/07/19 18:00:52
C99のrand()関数は「ラグ付きフィボナッチ」だと聞いたけど、
どんなアルゴリズムなの？

214:デフォルトの名無しさん
06/07/19 18:12:33
アルゴリズムまで規定してたっけ？？＜C99

215:デフォルトの名無しさん
06/07/19 20:30:32
x_i = a * x_(i-p) + b * x_(i-q) (mod M)
狭義のlagged Fibonacciだとa = b = 1.

216:デフォルトの名無しさん
06/08/26 01:43:17
線形合同法と似てない？

217:デフォルトの名無しさん
06/10/08 06:58:26
>>211
一様では乱数とは言わない。
特定の周波数幅に対するホワイトノイズ乱数というのなら可能。
この場合は特徴があるが、目的に使う限り特徴は現れにくい。

218:デフォルトの名無しさん
06/10/08 07:16:59
>>217
フィルタ使わずそんなもん発生する事できるのか
是非教えてくれ

219:デフォルトの名無しさん
06/10/09 18:00:37
ちょークロックの早いPCM合成チップで生成

220:デフォルトの名無しさん
06/10/09 18:54:49
ブラム・ブラム・シャブって乱度高そうだな
シャブ打ってラリってそうな響きだ

221:デフォルトの名無しさん
06/10/09 23:00:54
>>218
例えば想像する対象をサイコロの目としてみる。
１から６まで均等にでる乱数なら可能だろ
その種類だけ格納するテーブルを作って
確立が高い部分か低い部分を再度乱数を求め補正するだけ
原始的な方法で昔から使われている。
記憶容量に依存するが、多重評価することで要求に対するバランスが測定
可能であれば、それを元に補正するだけでいい。
この方法だと周期はでるが、結果として分かっている周期を補正するのは
容易だろう。
任意の偏りがでるかスペクトルを測定し再評価すればいいだけの話だね。

222:デフォルトの名無しさん
06/10/10 00:38:32
統計を取って補正すると、乱数じゃなくなるけど？
時系列で見ると偏ってるからね。

223:デフォルトの名無しさん
06/10/10 00:45:37
もともと偏った確率で目が出る疑似乱数に、統計情報を加えて一様乱数にしようとすると、必ず波が出来るよ。
パチンコやスロット台で波が出来るのもこのせい。

224:デフォルトの名無しさん
06/10/10 01:20:57
>>222
１０年間同じ値が続いても乱数。無限に長い時間からすれば確率的には存在する。
そのぐらい理解しておけ

225:デフォルトの名無しさん
06/10/10 01:23:04
>>223
元の擬似乱数にある偏りが表にでただけで偏りがすくないものなら
測定できるような波はでない。
それに波がでたとしてもそれをフィードバックさせるだけで補正は可能。

226:デフォルトの名無しさん
06/10/10 01:25:25
まあ、224と225が別人で、まったく逆の方向を指してるのだけはわかった。

227:222
06/10/10 01:39:12
>>224
統計を取って補正しちゃうと、それが不可能になるって言ってるんだけど？

228:デフォルトの名無しさん
06/10/10 19:31:09
バカな俺に「一様では乱数とは言わない」の意味を教えて下さい。
一様乱数は一様ではないの？

229:デフォルトの名無しさん
06/10/10 19:40:53
Wikipedia項目ﾘﾝｸ

230:デフォルトの名無しさん
06/10/10 23:18:00
一応乱数

231:デフォルトの名無しさん
06/10/13 14:21:51
>>228
一様だと周期があるということになるのは理解できない？
一様乱数とは有限の範囲内では周期がないが、それ以上だと
周期がある乱数を言う。
>>224
それは自然乱数の本質だな
>>225
これは正規乱数の類だな。上のwikiに解説してあるからしっかり読んでおけ。

232:228
06/10/13 17:44:49
>>231
>一様だと周期があるということになるのは理解できない？
はい。
「一様であること」とは「偏りがないこと」と理解しています。なので、
>それ以上だと
>周期がある乱数を言う。
「一様であること」と「周期があること」の関係が解らないでいるのです。

233:デフォルトの名無しさん
06/10/14 01:15:08
数学出来なそうなニオイ…

234:デフォルトの名無しさん
06/10/14 02:45:28
横レスで済まんが、俺もわからないんで、デキるあなたが解説してよ>>233
暗号と情報セキュリティのお勉強はしたけど、正直乱数はよくわからん

235:デフォルトの名無しさん
06/10/14 03:09:53
>>231が何言ってるのかは全く不明だけど、

特定の有限回の試行での一様性が担保されているなら、
それは全く乱数ではない、というのは自明だと思う。

ところで、疑似乱数は内部状態を有限量のデジタルデータで
持つという仕組み上、有限の周期をもつこともまた自明。
なわけで、一様な疑似乱数＝乱数ではない、ということになる。
のか？

一様だろうがそうでなかろうが、所詮周期があるという点で
「疑似」乱数でしかないわけだけど、一様性が担保されている
場合は、そうでない（一様かどうか不明な）場合と違って、
周期の終わりの方では次にでる数字を推定しやすくなる。
ギャンブルには使いにくい。

次ページ