擬似乱数

擬似乱数発生器について語ろうか。

n * 1103515245 + 12345 mod 2147483647

LD A, R

>>2は
n * 1103515245 + 12345 mod 2147483648
の間違い

*(char *)(0xFFBC0161)

MT

では手始めに、メルセンヌツイスタの荒探しの話題から頼む。

数学板
乱数スレ
http://science4.2ch.net/test/read.cgi/math/1126350979/

電気電子板
【疑似】乱数をつくる【本物】
http://science4.2ch.net/test/read.cgi/denki/1074867250/

シミュ板
乱数
http://science4.2ch.net/test/read.cgi/sim/1100375806/

ここはム板らしく、あら捜しよりも高速化とか考えた方がいいんじゃない？

暗号通信用に擬似乱数生成専用チップがあるようだが

ではその仕組みについて講義してくれ

擬似乱数ではないが
http://www.toshiba.co.jp/about/press/2004_08/pr_j0901.htm
http://www.internix.co.jp/publish/newsletter/nl85_pdf/nl85fdk.pdf
http://www.hmi-jp.com/hmi/security/clutterbox.html

>>7
アルゴリズムじゃなくて、その実装(mt19937ar.c)のアラでよければ。

MTは内部状態として624個のベクトルを持ち、そこから乱数をひねり出す。
つまりはMTは624*32=19968ビットの乱数生成器で、
その19968ビットの乱数表から32ビットずつ取り出すのがgenrand_int32()関数ということができる。
で、genrand_int32()を624回呼ぶごとに内部のベクトルを一度に「えいや」と更新するようになっている。
大量の乱数が必要な場合は並列処理が効くのでこれでよいのだが、
中程度数の乱数がリアルタイムで必要となる場合、これはいただけない。
例えばゲームでMTを使うとすると、624回乱数を生成するごとにフレーム落ちが発生、ということもありうる。
genrand_int32()を1回呼び出すごとに1つのベクトルを更新するようにすれば
いつでも同じ時間で乱数が得られる。

ゲーム用ライブラリとかで、mt19937.cがほとんどそのまま使われているのを見ると
「お前本当に分かっててその乱数発生器を薦めているのか？」と言いたくなる。

>>7
>では手始めに、メルセンヌツイスタの荒探しの話題から頼む。 

でかい、重い。

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

でかいは同意だが、そんな重いか？

あーでも初期化は重いかな。ほとんどハッシュ関数だよね、あれ。

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

軽さで言えば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)) );
}

つか、速くてランダムなやつとなると
やっぱりどれもハッシュ関数みたくなるのな。

パチンコで勝つためはどのような乱数をシミュレートすればいいのですか

脳内乱数

ゲーム用途なら、そこそこ均等に出てくれれば精度自体は8ビットぐらいでも問題ないよな。

つうかMTは本家サイト自身が「モンテカルロ法シミュレーションのための擬似乱数」って言ってなかったか？
均等な乱数が超大量に必要な場合に使う、みたいな。

ここはまあまあ有意義なスレですね

ゲームで言えば、１フレームに数百から数万（雨とかパーティクル）なら線形合同法で十分だろう。
プログラマーには見えても、ユーザーには周期性は見えないよ。

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

>>18それ、まともにM系列のが

でも、正直な話、現実での MT の用途の割合なんて

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

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

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

　4.その他：1%

位だと思う。

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

ゲーム用で再現性無くていいなら、時間とユーザーの入力
（その時しかありえないようなPCの状態）を混ぜりゃほぼ
ランダムになる。

>>29
その必要も無いのに、
テスト項目に「時間」と「ユーザーの入力」の要素が
入るような実装は、極力避けるべき。

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

SSL の証明書作るときのシードにキー入力使ってたな。

インターネットを利用したランダム関数できないかな？

>>32
パケットが通過する間隔はポアソン分布に従う、とかそういうのを利用するのか？

２ちゃんねるを利用したランダム関数欲しい

>>18
これ確かに早いけど、種を選ぶのが難点だね。
128ビットで、そこそこ0と1が混じってないと駄目ってのが。
種用に物理乱数とか、遅くても質のいい乱数発生器を別個に使う必要があるなあ

>>13
あと、初期化が糞だよねぇ。そのせいでかなり癖のある乱数列が生成される。理論台無し。

まあ初期化ルーチンに関しては他の乱数生成関数とかハッシュ関数とか組み込めばええんでない？
xorgensでもMTでもどの擬似乱数でも言えることだけど。

MTの初期化ルーチンをそのまま使うときは最初の100万個ぐらいは読み飛ばしたほうがいいらしい。

100万の根拠は？

統計的としか言いようが無い。
50万とか70万とかいうデータもあるが

正確には681,1573個だ。

要するにマンコ

>>30
再現性がなくなるだけで、時間を加味していればテストは自動化できるだろ。
話それるがユーザー入力だって、ある程度自動化するし。
>>32>>33 全部ユーザー入力と一緒じゃね

>>38
はつみみなのでソースおせーて

初期化が糞な場合、MTみたいに周期がアホみたいに長い疑似乱数はその程度
読み飛ばすだけで癖が抜けるとは思えんのだが。

>>40
その統計の在処をぜひ

じゃあみんなで初期化関数考えようぜ。
（新しい擬似乱数考えるのと同じになりそうだが）

>>47
そんなの Windows なら CryptGenRandom 、Unix系なら /dev/urandom を使う・・・てのが常識では？

MD5だっけ？
まあ暗号用に使うんじゃなくてあくまで擬似乱数用の種だからCRCとかでもいいような希ガス

どうでもいいならシステムタイマー使えばいいし
厳密にやりたきゃ>>48の使えばいいし。

結局、MT 厨は、そのネームバリューを闇雲に信じるだけで、
自分で乱数性の検証はしていなかったんだな。

>>51
当たり前だろｗ
偉い人が使えるって言えば使うだけ

Ｍ系列乱数と、線形合同法の結果をXORして使えば

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

>>51
それが厨の厨たる所以。

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

Ｍ系列乱数と、線形合同法の結果をXORした場合、
簡単に種を見つけるアルゴリズムはあるのだろうか？

総当たりが一番簡単だ。

>>55の言う「簡単」はそういう意味じゃないと思われ

もし総当りしかないのなら暗号に使えないかな

ワンタイムパッドとしてなら

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

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

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

証明されてなくても多分大丈夫だろうって使われてるのはあるな

証明できるくらいまで研究が進む頃には、
総当たりで簡単に種を探せるようなスペックのマシンが動いている気がする。

>>62
光の速度を考えると、本当にそんなマシンが出来ると思う？

量子論的重ねあわせがどうこう

>>64
この場合、全部の組み合わせを検索しなければならないのだとしたら
まず全部の組み合わせをどこかに入れておく必要があるんじゃないの？
そうすると物理的に不可能でしょ

>>10
半導体中の熱電子の揺らぎを使った、
熱的乱数発生モジュールを売っているベンチャーもある。
もう数年前の話だけど。

>>65
一つの量子に複数の状態を重ね合わせることが出来るので
理論上はあらゆる組み合わせを一箇所に保管できるようになる。
現在の技術では4状態で実験に成功したそうだｗ 先は長い……

> 一つの量子に複数の状態を重ね合わせることが出来るので
　〜〜〜〜〜〜〜〜
> 理論上はあらゆる組み合わせを一箇所に保管できるようになる。
　　　　　　　〜〜〜〜〜〜〜〜〜〜〜〜〜　

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

別に間違っていないが。

また開き直りか。

考える問題において可能なあらゆる状態数がＮのとき
一個の量子ビットにＮ個の状態を重ね合わせる量子アルゴリズムを使うなら
別におかしくないね

言い訳乙ｗ

頭悪すぎ

おまぃの「理論」とやらでは、
量子と周囲とのインタラクションを完全遮断して、
かつ、その量子に任意個数の状態を保持可能なのかｗｗｗ

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

というより　
検索が高速だとしても、
1万なら1万通りの状態を一瞬で作る方法があるのか？
あるなら、既にその問題は解けてるわけじゃないのか？

>>67でも>>69でもないですが、おいらはShorの素因数分解アルゴリズムのことを言ったんだけど

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

一体何の話？

あ、>>62からの流れだったんですね
すいません

＞考える問題において可能なあらゆる状態数がＮのとき
＞一個の量子ビットにＮ個の状態を重ね合わせる

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

>>77
あ、ほんとだ
一個のqubitに格納する状態の数はＮ個じゃなかった
うろ覚えですいません

>>66
それって周囲の温度によって乱数変わったりしない？

アメリカの暗号乱数発生チップには諜報機関の権限でバックドアが仕掛けられているという話だが…

>>18これって普通にソースに組み込んで使ってもライセンスの問題無い？

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の初期値が種？

>>82
よく見ろ、t の初期値は使われてないぞ。

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数の根拠がよう解らんのですわ。

ここには乱数に詳しい人はいない件

飯の種だし
こんなところにタダで書くわけにも

>>18
乱数全然わからんけど、
y,zはただのキャリアーでx,wの上下32bitを使うのね。
中間の64bitは使わなくてもいいの？
その方が出力が読みにくかったりする？

そんな単純な問題じゃない

>>87
よく見れ、種として機能している。

擬似乱数の種を得る方法には時刻以外にどんなものがある？

未初期化変数のゴミ値

マウスカーソルの座標

俺の場合、セキュリティ関係の用途じゃない時のデフォは[時刻＋プロセスID]。
セキュリティ関係の用途の時には >>48 。

サウンドカードからの入力(ノイズ)値

>>94
俺DTMやっててフルデジタル環境なのでサウンド入力は常時0になりますが……
もしかして俺の環境だとうまく乱数吐かないソフトあるんかな？

>>91
それ、ほとんど毎回同じになるだろ。

連続起動時間
CPU稼働率
メモリ使用率
メモリキャッシュ量
HD容量+使用率

素直に>>48使おうよ…

CryptGenRandomは失敗する環境があるから

１００

>>94
そういやファミコンはアナログ信号ピンがあってカートリッジ側でそいつを読めたんだっけ？
それを乱数に使ったゲームは知らないが。

>>99
MSが標準で提供してるサービスプロバイダを選んでちゃんとした初期化をすれば、失敗する環境なんてないだろ？

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

>>90
そういえば、Z80のアセンブラとかではリフレッシュレジスタ(※)の値を利用するなんて話もあったなぁ。

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

>>103
>>3

>>103
連続起動時間とそうたいして変わらんと思う

たしか3ビットだか4ビットぐらいしかなかったような気がする＞リフレッシュレジスタ

>>106
7ビットだよ。
しかし互換CPUでは全く変化しないこともある罠。

ところで、乱数性を評価する方の話はどうなのよ
http://csrc.nist.gov/rng/
とかさ

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

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

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

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

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

>>110
おまい、ちゃんとわかってる？　ちゃんと実測した？

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

>>111
> MTでもちゃんとした初期化をすればちゃんと圧縮率が悪くなるのも確認済みだし、
それって、 MT には何にも問題ないってことだよな？

圧縮についてなんか知っててそんなこと言ってるのか？
圧縮ソフトが何やってるのか調べた方がいいぞ。

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

>>113
そもそも乱数性の検証に圧縮を利用するのはただのハックに過ぎないことはわかってる。
だからこそ、他人の意見を聞きたい。

辞書サイズよりも大きい周期で同じデータを吐き出しても圧縮率は変化しないよね

>>116
にも関わらず、MTや線形合同法では圧縮率がいいんですよ。

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

>>111
>おまい、ちゃんとわかってる？　ちゃんと実測した？
実測データｷﾎﾞﾝﾇ

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

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

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

他の圧縮やってみたら全然結果が違ったらどうする。

>>120
別にどうもしないけど。圧縮アルゴリズムが違えば結果も異なるのは当たり前。
しいて言うなら評価をする為の圧縮アルゴリズムのひとつとして採用するだけ。

てか、ちゃんとした知識を持ってて、理論に基づいてどーこー言えるヤツはおらんのか？
俺自身も知識よりは閃きの人間だから、知識のないヤツは黙ってろとかは思わないが、
できれば知識を持ってる人間の意見を聞きたい。

断る

>>123
そんなこと言わないで、頼むよ〜

1,2,3,・・・というデータはハフマン圧縮ではまったく圧縮できないがランダム性はない

>>125
そこまでテキトーなこと抜かすなよ。
ちょっとバイナリでの表現がどうなるか考えりゃ、圧縮できることぐらいわかんだろ。
せめてもうちゃっと考えてから書き込んでくれ、な？

>>126
いや循環し続けるデータなら　ハフマンでは圧縮出来ないのは正しいだろ
ただ、差分をとれば途端に圧縮出来るのだが

まずはランダム性を定義しろ

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

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

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

>>125
付け加えておくと、それはもっとも簡単な疑似乱数列だぞ。

>>129
1,2,3,・・・,2^32までのデータを使えば32bit表記では各ビットパターンは一回ずつ登場する事になるぞ

>>131
それでも圧縮は可能だろうが。

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

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

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

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

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

>>133
基準はどれぐらい？
テキストなんでだいたい 20% ぐらいになるのも普通かと思うんだが。

ところで、折角 >>108 が NIST の乱数検定器を挙げているのに
その実行結果について議論をするどころか、

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

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

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

>>132
圧縮云々を言うならせめて情報理論ぐらい勉強しろよ・・・

>>136
コメントに日記が書かれていても複雑なプログラムなのかw

>138
で？何？

バカばっか

データ列を圧縮してその圧縮率がどう、ってのはシャノン情報量を見てるんだよね？

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

１００万回同じ値を吐くという状況を再現できんのだが、何が問題なのかサパーリ
俺はboost::random::mt19937使ってる

>>142
そりゃー32bitの乱数なら100万回同じ値になる確率は1/((2^32)^999999)なんだから
そうそう簡単に再現されるわけ無いじゃん。

で、そうそう再現されない状況なんだから、
「はじめっからそんな値を吐かないアルゴリズムでも問題ないよな？」
という考え方で、もっと短周期の乱数アルゴリズムが『実用的』とみなされている。
ってこと。

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

池沼としか思えんｗ

いけぬまで悪かったな！ これでも頑張って勉強中の身なんだ……

このスレ見てて思ったんだが、乱数がどういうものかっていう理解度が人によってかなりまちまちなんだけど、
理解度が低い側の人が自分自身の理解度が低いということすらが自覚してなさげだね。

最低限↓このページの最初に書かれていることぐらいは理解したうえで議論すべきだと思うけど。
http://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0

「ｽﾚが急激に伸びる時は大抵、池沼が書き込んでいる」

↓↑
└┘　そうだね

また池沼が寄ってきた

おかえり池沼くんｗ

なあMTよりもうちょっと周期短くていいからベクトル数すくない乱数ないの？

AESやtwofish 等のブロック暗号の結果を使うと、エントロピーという面では良い？
ちなみに、暗号化した結果をさらに暗号化して、次の乱数を出していくような形だと、悪い性質が出てきたりするのかな？

それOutput-FeedBackって奴じゃん。

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

XORすべき平文はないけれど、それも OFB って言っていいのかな？
そうであれば、たしかに OFBですね。

で、結局、まともなブロック暗号であれば、エントロピー的な意味では、
悪い性質が出てきたりはしない筈…ですかね？

>>156
全0の数列とXORして結果を得ていると考えればOFBの一種だな

>>157
その「まともな暗号」を考えるのがﾑﾂｶｼｲ

>>159
154で書いた通り、前提として、AESやtwofishを想定していますけれど。
暗号の世界の死屍累々の歴史を見れば、よほどでなければ俺様暗号を作ろうなんて傲慢な気持ちにはなれないですよね。
AES 選考のときも、ドイツテレコムが採用していた暗号が 10秒で即死したり、笑い話に事欠かない世界…怖いですね。
http://h2np.net/bit/aes-rep.html

>>160
ﾊｧﾊｧ 読んでて興奮するね。

>>160
ｶｺｲｲ!!

>>160
最終的にAESに選ばれたのはそこで名前すら挙がっていなかったRijndaelだというのも
おもしろいな

高速な乱数の基本はシフトとXORを使うことらしいが
この二つってそんなに演算早いの？
加減算やローテートは遅い部類なの？

シフトとローテイトはCPUレベルではそんな変わらんと思うが

加減算は変わりそう

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

Pen4なら加減算が倍速でローテートはアホみたく遅い。
使用する環境が決まってるならCPUに特化した乱数ルーチンもアリだと思う。

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

>>168
ぐぐったら出てきた
ttp://journal.mycom.co.jp/news/2003/01/22/15.html

こんなのも。どうやって使うのか知らないけれども。
http://www.intel.co.jp/jp/intel/pr/press99/991116.htm
インテル 820 チップセットは〜インテル(R) ランダム・ナンバ・ジェネレータ（乱数生成器）を搭載しています。

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

PCで使うなら気にするこたねぇだろ
組み込みで使うならともかく

そだね。
SSE2使おうってCPUならキャッシュで収まるもんね。
気兼ねせず実装することにしますわ。

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

ま、その前提で高速演算できますって機能だから仕方ない。
組み込み系だと日常茶飯事だけどｗ

「とってもごはん」のMMX版MTって、オリジナル版と出力違ってないか？

>>171
うｐはdvi形式でおｋ

>>175
オリジナルのMTも32bit版と64bit版で出力違うから気にしなくていいと思う

で、初期化がどーのこーのに難癖つけてた件は結局うやむやのうちに終了しちゃったの？

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

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

MT-32よりCM-64の方が面白いよ

ローランド音源かよｗ

>>178
心配なら暗号論的乱数で初期化汁、そこまで気にしないならどうでもいい、でFA出ちゃったからね。

線形合同法で十分

場合によっては

いけぬますれ

>>184
そんなこと言ってないでなにか話題提供してくれよ

擬似乱数について素人ですが、教えて頂けないでしょうか？

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

よろしくお願いします。

[0,1] の一様分布に従う擬似乱数の標準偏差が
1/sqrt(12) に収束するのは別に何もおかしいところが無いわけだが

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

187さんへ
　ありがとうございます。
　たしかに、1/3-(1/2)**2でも0.288...になりました。
　0.25と思い込んでいました。

>>175
それ以前に、メルセンヌツイスタはBSDライセンスのはずなのに
ソースコード中にライセンスについて一切の記述がない事がまずいと思う。
SYN氏、忘れてんのか？

そーいや乱数発生器のライセンスってどうなってるんだ。
AESはフリーなんだっけ？

yes

Rijndaelだけ？他のは？

自分で調べろ

量子論的乱数発生器ってある？

Intelの最近のチップセットには内蔵されてるはず

詳細規模んう

なんでコンピュータは擬似乱数しか出せないの？

真性乱数も出せるだろ、専用のハードウェアがあれば。

>>197
決定性チューリングマシンだから。

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

>>197
つ /dev/random

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

というか、非決定性チューリングマシンができてしまうと、
今まで暗号論的擬似乱数と呼んでいたものの前提が全て崩れちまうな。
ttp://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0

>>201
えっと、そんなことはないです、オーダー的に。デタラメ言わないで。

>>202
え、なんでだ?

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

どうでもいいがWikipediaを参考文献として引き合いに出すのは勘弁してくれｗ

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

>>204
嘘書いたの？

自分の使ってる狭い専門用語を広めるのには便利かもしれないな。

>>109の方法をやってみたら
どの乱数列データもまったく圧縮できないorz

>>205
いやそういう意味じゃないが、非常に照れくさい……

ま、素人はそう考えるわな。

間違ってるけど

一様な乱数のお薦めを見繕ってくれ

MT

C99のrand()関数は「ラグ付きフィボナッチ」だと聞いたけど、
どんなアルゴリズムなの？

アルゴリズムまで規定してたっけ？？＜C99

x_i = a * x_(i-p) + b * x_(i-q) (mod M)
狭義のlagged Fibonacciだとa = b = 1.

線形合同法と似てない？

>>211
一様では乱数とは言わない。
特定の周波数幅に対するホワイトノイズ乱数というのなら可能。
この場合は特徴があるが、目的に使う限り特徴は現れにくい。

>>217
フィルタ使わずそんなもん発生する事できるのか
是非教えてくれ

ちょークロックの早いPCM合成チップで生成

ブラム・ブラム・シャブって乱度高そうだな
シャブ打ってラリってそうな響きだ

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

統計を取って補正すると、乱数じゃなくなるけど？
時系列で見ると偏ってるからね。

もともと偏った確率で目が出る疑似乱数に、統計情報を加えて一様乱数にしようとすると、必ず波が出来るよ。
パチンコやスロット台で波が出来るのもこのせい。

>>222
１０年間同じ値が続いても乱数。無限に長い時間からすれば確率的には存在する。
そのぐらい理解しておけ

>>223
元の擬似乱数にある偏りが表にでただけで偏りがすくないものなら
測定できるような波はでない。
それに波がでたとしてもそれをフィードバックさせるだけで補正は可能。

まあ、224と225が別人で、まったく逆の方向を指してるのだけはわかった。

>>224
統計を取って補正しちゃうと、それが不可能になるって言ってるんだけど？

バカな俺に「一様では乱数とは言わない」の意味を教えて下さい。
一様乱数は一様ではないの？

http://ja.wikipedia.org/wiki/%E4%B9%B1%E6%95%B0%E5%88%97

一応乱数

>>228
一様だと周期があるということになるのは理解できない？
一様乱数とは有限の範囲内では周期がないが、それ以上だと
周期がある乱数を言う。
>>224
それは自然乱数の本質だな
>>225
これは正規乱数の類だな。上のwikiに解説してあるからしっかり読んでおけ。

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

数学出来なそうなニオイ…

横レスで済まんが、俺もわからないんで、デキるあなたが解説してよ>>233
暗号と情報セキュリティのお勉強はしたけど、正直乱数はよくわからん

>>231が何言ってるのかは全く不明だけど、

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

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

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

普通のrandじゃいけない理由は？

>>236 その「理由」を君が知りたい理由は？

>>237日本語でおｋ

ところで、
ttp://www.optoscience.com/maker/id/id.html
の真性乱数発生器ってのはホンモノなの？
熱雑音を利用したチップやボードはよく見かけるけど、
量子乱数ってのはあまり見かけないような気がするッス
どういう仕組みになってるんだろうか…

周期が終わったら初期化すればいいじゃない

>>236
いまどき普通のrandを使う理由は？

>>241
いまどきじゃないrandが存在する理由は？

>>242
いまどきじゃない方が便利だから

便利かどうかで言えば、便利さは「同じ」だと思うな。
重要なのは、目的を達成するための手段として妥当かどうかだよ。

少なくとも理不尽さを軽減する効果はある。

ユーザ「なんでここで○○が出て来るんだよ！ありえないだろ！！！」
開発者「MTですから、乱数に変な癖は無いですよ」
ユーザ「そうか・・・偶然じゃあしょうがないな・・・」

みたいな。

Civシリーズの乱数FAQを思い出すナー

メルセンヌ・ツイスタのホームページが存在しないんだけど
作者はもう慶応には居ないってこと？

>>247
普通に"MT 乱数"とかでググれば出てくると思うが

civの乱数には波がある

すいません、昭和初期の国産バスの図面を探しているのですが、
適当な資料をご存じの方がいたら教えてください。

>>235
>一様性が担保されているなら
…あ、そうか。やっぱ俺はバカでした。
ありがとうございます。ひとつ賢くなりました。

>>251
本物？釣り氏？ｗ

一様性が担保されていても、長ーい周期の疑似乱数の最初の方だけ
使うんならあまり問題にならないような気がする。

40万組みのシャフルしたトランプから10枚だけ引くとか。

ここまでの俺の理解：
（１）周期があるというのは、別に一様にしようがしまいが疑似乱数である限り言えること

（２）一様乱数の場合は、そうでない疑似乱数と比べて
　　　　　　周期の終わりに近づくにつれてさらに予測しやすくなる

（３）>>231が前半二行で（１）以外の情報を伝えたかったのかどうかは不明

一様乱数の意味を勘違いしてる人が多いな。

(正しく作られた)サイコロは過去の出目に関係なく、次にある数字が出る
確率はすべて等しい。＝ 一様である。
サイコロを続けて振って得られる数列は一様乱数になる。

ソフトウエアで生成する乱数が原理的に真性乱数になり得ないのは
まったく別の話。一様性とは無関係。

なるほど、その勘違いした人が大声で解説すると。
悪貨が良貨を駆逐するとはこのことか。

>>255
やっぱそうなのか
上の話を読んで
「サイコロを６回ふったら、１から６までの目がどれもぴったり１回出る」
が一様乱数かと思って焦ったよ

>>255
疑似乱数の場合、
＞確率はすべて等しい。＝ 一様である。
ものと、そうでないものがある、というのはわかっていますか？

なんでこう自分の言いたい内容を明確に書かない臆病者が多いんだろうね？
ム板の特徴なのかな

>>255
（有限の）周期があって、かつ一様な疑似乱数の特性について
教えてください。１周期内では各数字は同じ回数だけ現れますか？

>>258
なぜ「過去の出目に関係なく」という部分まで引用しない。
重要なところだぞ。
また、間違ってると思ったらどこがどう間違ってるか書いてくれ。

一度ギャンブル用のサイコロとかプログラムで作って、現金懸けていわゆる賭博でもしてみれば身にしみてわかるさw

基本的に目的に使うものに影響がでない周期にして使えば問題ない。
厳密に一様というのは、愚かな考え。
１つの周波数に対して一様なのは可能だが。

>>262
プロと対峙して「てめぇいかさまだな」とか言われた日には。

>>264
その日を境に行方不明になると

サイコロの目は１から６まで均等にはでない。これが物理現象。
理屈の上の乱数と実際に作れる乱数とは別なことを理解できないとは
愚かだよな。
理屈上のサイコロでも「有限回数」の出目は一様ではない事実、これが何故か
理解できないの池沼に説明しても無駄だから放置だｗ

いや、単に「一様」という言葉を
「どの目も同じ回数出る」と誤解してる人がいて
勘違いしてる人もしてない人も混乱しただけだろ。

>>267
どの目でも確率分布を一様にさせると言う事は、出る回数が同じになって行くと言う事じゃないのか？

>>268
そうじゃなくてサイコロを600回振ったら100回1が出る
という意味の「同じ回数」。
出目が一様なサイコロを600回振っても1が100回じゃない
ことの方がずっと多い。

>>269
100回でも99回でも101回でもいいけど、100回に近くするって事だろ？
99回ならもう一回出そうかな？とか、101回出てたら、もう控えようかな？　とか、操作するんだよね？

>>268
> どの目でも確率分布を一様にさせると言う事は、出る回数が同じになって行くと言う事じゃないのか？
全然違う。
たとえば、n回サイコロを投げて1の目が出た回数をk1、2の目が出た回数をk2とすれば、
nを大きくしていくと k1/n と k2/n はともに 1/6 に収束していく(大数の法則)が、
|k1-k2|の期待値は大きくなっていくんだよ。

>>270
何の話だ？
まず、そういう操作をしたら一様でなくなってしまう。
過去の出目から未来がある程度予測できてしまうから。

で、そういう操作をする乱数の名前は知らない。
確かに、「誤用の一様」の意味はそれかも。
実用性はありそうだが、名前付いてる？

>>272
ギャンブルマシンと言われるゲーム機やパチンコ台やスロットの中身

サイコロは真性乱数。規則性とかないんだから、いつでも確率で語るしかない。
しかし、初期条件で全て決定される疑似乱数で各出目の出現回数が違ったら、
それは一様でないということなんじゃないの？


>>273
スロやパチはほとんど真性乱数とみて問題無いよ。
現在スロで主流の方法は、数MHzのクロックを16bitのカウンタで数えていて
レバーが叩かれた時にラッチするというもの。
カウンタが1周する周期が0.03秒とかだから、人間がレバーを叩いているかぎり
ほとんど真性乱数といえる。（だからソレノイドでレバーを叩いて狙う方法が存在する）

>>254
> （２）一様乱数の場合は、そうでない疑似乱数と比べて
> 　　　　　　周期の終わりに近づくにつれてさらに予測しやすくなる
それは違う。

一様でない疑似乱数、たとえば"1"が1/2の確率で"2"〜"6"がそれぞれ1/10の確率で
出現する疑似乱数列があるとして、その周期の大半を消費したとき"1"の出現率が
1/2より小さければ、周期の残りでは"1"の出現率が1/2より大きくなる。

つまり、次にでる数字を推定しやすいのは、その疑似乱数列の周期と分布が
「既知」であり、その周期に対して十分な長さの過去の乱数列を知っている場合だってこと。
その既知の分布の種類は、一様分布でなく二項分布であってもいいわけだ。

乱数は、完全な一様性を示さないものだろ、
サイコロの目のような有限の個数の値が
どの数も確立も一定なら真の乱数ではない。
単なるスペクトルの問題であり、長超周期の乱数を否定しなければ
短期間の乱数の一様性を守ることは不可能だろ。
おまいらが有限と思っている期間でさえ無限に近い乱数の価値観から
すれば短い期間であり、同じ値が続いたとしても確立の１つである。
短い期間が１億回同じ値が続くケースが存在したとしても、
乱数として間違いはない。
つまりだ、人間が扱える乱数とは有限回数の中でどの周波数成分でも
似た値を示すような数値を乱数と判断しているだけ。周期は確実にあり、
実用であるか、どうかの問題にしかすぎない。
プログラム板としては。ライブラリーが提供するような激しく短いビット
数の乱数を使うからこそ周期や特徴が出てしまうだけで、長い周期を
比較的単純なアルゴリズムで作れば問題はありえない。
円周率とか、無限級数でも使えｗ

>>275
>それは違う。
中略
>つまり、次にでる数字を推定しやすいのは、その疑似乱数列の周期と分布が
>「既知」であり、その周期に対して十分な長さの過去の乱数列を知っている場合だってこと。

「違う」といいながら同じことを言っているような気がする。

>>276
何を主張したいのかよくわからんが、
一様の説明で例に出したサイコロは理想的なサイコロで、
理想的なサイコロは完全な一様性を示す。
有限回振ることが前提でも一様性は変わらない。
>>270みたいのを一様だと思っているのか？違うぞ。

>>277
同じことは言ってないだろ。ちゃんと違うよ。
>>254は一様乱数の場合に予測できると書いていて、（←間違い）
>>275は周期と分布が既知の擬似乱数の場合に予測できると書いている。

>>254は「周期の終わりの方では」と書いているんだから、
周期の終わりの方を使っていることが解る⇒周期が既知、
が前提なんじゃないのか？分布も「一様」が前提だし。

>>279
ああ、そういうことか。
>>254(2)は、一様かつ周期があると言っているが、
これは言葉が矛盾してる。周期があったら一様じゃない。
ていうか擬似乱数は一様にならないだろ。

指向性が無ければ一様といえる

あ、ちょっと勘違いしてたかも。
>>275は周期のある擬似乱数に関して、
分布が既知ならそれが「一様分布でなくても」
予測ができる、と主張してるんだ。

>>254の勘違いは、一様の意味を>>268のように思っていること。
実際は>>271の言うように一様でも|k1-k2|の期待値は大きくなっていく。

更に、>>268のような数列は乱数ではあり得ない。
一様であるなしに関わらず乱数ならば過去の数列から予測は不可能。
逆に擬似乱数の場合、分布が一様でも何でも既知ならある程度予測ができる。

ということは、>>255も誤解を招く表現だ。
サイコロで次に出る目が過去の出目に関係ない＝乱数
サイコロでどの目が出る確率も同じ＝一様
擬似乱数に対して一様という言葉を使うかどうかは知らないが、
乱数であるならば既に過去の出目には関係ないので、
過去の出目に関係ないことを言うのに一様を主張する必要はない。

はっきり言って俺最強すぎて我慢できない

>>282
勘違いしているなら、「あ、ちょっと勘違いしてたかも。」は
常識が無い発言だよなｗ

一様性を検査しなくていいの？

>>285
一様性を「証明」する方が重要じゃないの

>>254=>>257です
>>254は「この人はこう言いたかったのかな？」と予想して書いたものなんで悪しからず

>>276
＞短い期間が１億回同じ値が続くケースが存在したとしても、
＞乱数として間違いはない。

確率分布が一様分布な確率変数のとる値が、たまたま一億回同じ値だったとしても
それは乱数ってことですよね。
（ここのほとんどの人は最初からそれは了解してるように思う）


＞つまりだ、人間が扱える乱数とは有限回数の中でどの周波数成分でも
＞似た値を示すような数値を乱数と判断しているだけ。

何か数列があって、それがバラバラな値の列だから乱数だ、そうでないから乱数じゃない、ってのは
そもそも違うってことですよね？
「どうやって採られたものか」が重要である、と。

んで
・有限長の数列を用意して、それを乱数として使う場合は
　　統計的に値の出現頻度が偏っているときに、それを補正することもある

・疑似乱数は有限の長さの数列の後に同じ数列の繰り返しになる

この二点がとりあえず事実ということでおｋ？

訂正

×疑似乱数は
〇疑似乱数生成器の出力は

粘着しているのは極度に短い周期の擬似乱数＝ライブラリーに付属しているような
ものを利用して乱数の一様性を補正すれば、乱数ではなくなるように勘違い
しているとかか？
極度に短い擬似乱数ではなく、極度に長い周期の乱数を用いて、目的の
一様性が保たれれば変な癖などでないだろ。元にしている擬似乱数が
貧弱すぎるじゃまいか？

>>287
>統計的に値の出現頻度が偏っているときに、それを補正することもある
どういう補正を考えてるの？

「1が続いたので次に1が出る確率を減らす」ような処理ならばNo。
そのような数列は乱数とは呼ばない。
乱数とは過去のデータにかかわらず常に一定の確率分布を持つもの。

計算によって異なる確率分布の乱数を作る事はある。
例えば、一様分布の乱数を利用して正規分布の乱数を得る等。

有名な同じ値が続かない乱数の作成方法として。
基本の擬似乱数発生から乱数がでる目の数だけ記録
（１から１０００なら１０００ビット）
同じ値が出た場合は出てないビットがでるまでか、適当な位置から
出ていない数値を検索しそれを乱数とする。
この場合だと１０００回の周期があるが１０００回中は同じ値がでないように
できる。
１から１０００まで同じ確立で発生し、その発生根本は別の擬似乱数など
から流用すればいい。
これは表面上は同じ値が続かないし元の擬似乱数が乱数的であれば
それなりに使える、例えばシャッフル再生などの音楽プレーヤーの
アルゴリズムなどで採用されている例がある。

>>291
それがＦＡ？

>280
>>>254の勘違いは、一様の意味を>>268のように思っていること。
>実際は>>271の言うように一様でも|k1-k2|の期待値は大きくなっていく。

それは真の乱数の話ではないでしょうか。
このスレでは疑似乱数についてだけ話すようにしないと混乱の元では？
>>更に、>>268のような数列は乱数ではあり得ない。
これも同様。

>>291
それは乱数というよりシャフルというかなんというか。

それはともかくとして、確率分布を補正する方法としては
目的の分布をもつ真の乱数列からなる適当なサイズの乱数表があれば、
疑似乱数でその表のn番目を拾ってゆくような方法があるような気がする。

どれくらいの大きさの表が必要なのかはよく分からないけど。

ループしすぎ

>>293
その通りだ。混乱しそうな場合は単に乱数と言わず、
「真の乱数」「擬似乱数」と言った方がいいね。
>>282は真の乱数のつもりで話している。

擬似乱数に対して一様という言葉を使ったら、
単に擬似乱数の周期の中でどの数が出る回数も同じという意味だよな。
1,2,3,4,1,2,3,4,・・・という周期的な擬似乱数（質は最悪だが）も、一様ということになる。
こういう使い方は正しい？

>>296
> 1,2,3,4,1,2,3,4,・・・という周期的な擬似乱数（質は最悪だが）
そこまで短い周期の数列を「擬似乱数」と呼ぶのは変だと思う。
「擬似」乱数なんだから、ある程度は真の乱数の代替に使えるくらいの
性質を持ってないと。

だから、ちょっとやそっとじゃ一周できないくらいの長い周期を持っていることは
「擬似乱数」と名乗るための重要なファクターだと思う。

>>297
つまり、ある程度乱数っぽい列に対しては
一様乱数という言葉を296の意味で使っていいということ？

おまいら、円周率つかえ。

円周率やルート2って、真の乱数と言えないような要素ある？
１億桁目までの数字の偏りとかじゃなくて、本質的にわかっている部分で。

円周率は、任意の桁までは計算によって求める事が可能。
今まで出た数値が円周率の数値と同じならば、次に出る数値は計算によって算出可能。
この事は、予測可能な事を意味する。
よって乱数ではない。

>>301
下手な疑似乱数より周期長くていいぞw

>>301
> 今まで出た数値が円周率の数値と同じならば、次に出る数値は計算によって算出可能。
円周率に近い別の無理数かもしれない。例えばπ＋1/√(10^1000+1)とか。

で、俺が聞きたかったのはそういうことではなくて、
例えば円周率の10^1000+1桁目から10^1000+10^20桁目までの列と、
真性乱数の10^20個の列を与えられたときにある程度の区別が付くか、ということ。
わかりにくくてスマソ。

真正な乱数ならどんな数列でも出現する可能性はあるわけで、
数列だけを比較して区別するなんて不可能でしょ。

>>304
そんなことはわかっている。
だが、例えば「1の後には2が来やすい」のような傾向があれば
十分な長さの列があればほぼ確実に判定できるだろ。

わかっているなら聞くまでもないじゃん。

大学教授、円周率を計算し過ぎて逮捕
ttp://www.faireal.net/articles/4/23/#d60401

>>307
あのカスラックなら本当に言い出しかねんな

>>301
無限に続くものは任意の桁まで計算できない。
理由は、計算するまでに宇宙が終わるｗ
人類も機械も消える。
愚かだなｗ

「任意の桁はどこにしますか？」
「無限桁目にします」

バカだな　宇宙が終わるなんて都市伝説だよ

宇宙が意思、知能を持っていて、宇宙自身が算術を可能という説もある。
というのは、ガセ。

42

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

地面は平らだ。丸いわけがない。
象が支えて亀が歩いているんだ。
宇宙があるなんて都市伝説だ。

人間なんて居るわけが無い。
これは全部俺の妄想だ、夢だ。

>316
お前今「嘘」ってＷＯＰ使うの避けたろ

何で擬似乱数程度でこれほど燃えるんだよ、馬鹿ばっかりだなｗ

燃えてるように感じてるのは多分お前だけ

319みたいなＤＱＮばかりだけど勘弁してやれ>318

折角萌えるなら擬人ｋ

とうとう煽り愛のスレに成り果てましたか？

>>294
短い周期なら乱数だろ？０と１の２種類とかｗ

>>291
最初は[1,n]の乱数で、次は[1,n-1]の乱数…と発生させてその出力を使えば同じこと。

で、おまいらがほしい乱数とは、数値が連続せず、どの数値も同じ確立に
なりやすい擬似乱数だろ？
プロセッサのリヤルタイムクロックに同期するようなプログラムはほぼ
困難というか事実上は不可能だろうから
それでも利用すればいいんじゃないか？連続に高速で利用する場合も
考慮して乱数テーブルでも用意してミックスすればよさげ。

そんなあなたに
http://www.t-rs.co.jp/products/p-5/index_j.htm

時計もないしメモリの状態も常に一定の環境で
擬似乱数を発生させたいんだけど
不確定要素が無いので種がいつも同じなので
動作が常に一定になってしまい
擬似乱数にならないのです
どうしたらいいのでしょうか？

サイコロ振って手入力

外部要因で動作・変化する何かがないとムリだっぺ

>>327
よく使う手だけど
メモリをちょっと壊す

>>327
人間に２回何かさせる。

>>327
原理的に不確定要素が必要だから、何とかするしかない。
メモリ状態、ユーザの入力、CPUｊの状態、
それでもダメなら種を予め手入力しておく。

やはり不確定要素が必要なのですね
アドバイスありがとうございました

そこでUSBガイガーカウンタですよ。

擬似乱数の萌え擬人化希望

> メモリの状態も常に一定
ずっとHLTでもしてるのか?

>>336
初期値がクリアされているシングルスレッドではないかと・・・
いや、やっぱずっとHLTかな・・・

>>332
昔と違ってＯＳが動いているＰＣなら普通に不確定要素のタイミングで
動いている。
ＣＰＵコアのリヤルタイムクロックとアイドリングで動くカウンター要素
等を組み合わせても不確定要素を簡単に抽出可能だろ。
ワンチップマイコンや電子回路程度では話は変わってくるだろうけどな

時計もないしメモリの状態も常に一定の環境

リヤルタイム

>>334
プーチン政権を批判するロシア人に持たせれば
良質な乱数が作れそうだな。

>>341
All1で乱数にならない罠。

擬似乱数なんてストリーム暗号の出力使えばいいじゃん

マリーアントワネット様ｷﾀ

>>325
>で、おまいらがほしい乱数とは、数値が連続せず、どの数値も同じ確立に
>なりやすい擬似乱数だろ？

このへんが少し困るところだよな。
人によっては(もしかするとかなり多くの人が)その方がランダムだと
思っちゃうんだよな。
もしサイコロで6が5回位続いたら仕込んであると怪しまれそう。
同じ目が続かない方が乱数としてはおかしいんだけどな。
短周期で目の分布がいつも揃ってたらそれもおかしいし。
52314ときたら次は6だろうみたいな。
人の感じる乱数性は真の乱数性とは違うんだろう。

音楽のランダム再生などは、真の乱数性ではなく、
人がランダムと感じることこそが重要だが、
こういう擬似乱数列を得る手法で有名どころとかある？

>>346
単なるシャッフル再生じゃダメなのけ?

シャッフルといってもいろいろあるべさ。
某MP3プレーヤのシャッフルリピートは同じ曲を3回繰り返したし、
某なんとかシャッフルのシャッフルリピートは同じ曲を一回おきに3回繰り返した。

ランダム再生とシャッフル再生を区別しているプレイヤーもあるな。

ランダム再生
… 一曲終わるたびに、次に再生する曲を全プレイリストの中からランダムに選ぶ。
シャッフル再生
… 再生開始時にプレイリストの一覧をシャッフルしたものを内部的に作り、
その順序にしたがって再生する。プレイリストの全曲を再生し終わったら
もう一度プレイリストをシャッフルする。

この分類だと、>348のようなことはランダム再生だと起こりうるが、
シャッフル再生だと起こらない。

>>347
言われてみればそうだな。連続出現の心配はなくなるわけだ。
あとで思い出したが、同じアルバムの曲が１０曲中３曲もあるから
ランダムじゃないと感じることもある。
まあこれもバラし方を考えればいいだけで、
乱数の発生方法とは関係ない話だったな。

>>346
>>324みたいな乱数列を作ればいい訳で

>>345
擬似乱数なんだから乱数を元にしたシャッフルで問題ないだろ。
現実のサイコロにしても目の数の周期性はあるわけだし。
※理論的なサイコロではない。
単に乱数に拘るのは周期が短いライブラリーなどにある乱数関数を使うと
規則性が表面に出て見えることがある。
この点であると思う。真の乱数であるなばら規則性が目立っても
それは一時的（数年続いても無限からすれば極短期間）な挙動であって
乱数である。
何かの規則で一様性な分布がほしいのであれば「無限級数」等を使えば
言い訳で、人間から見て一様乱数にみえるのはシャッフルがもっとも
近いものじゃないか？

>>352
ぐだぐだな日本語に気持ち悪くなってくる。

>擬似乱数なんだから乱数を元にしたシャッフルで問題ないだろ。
シャッフルな用途にはシャッフルで問題ない。シャッフルでは困る用途もきっとある。

>現実のサイコロにしても目の数の周期性はあるわけだし。
現実のサイコロに周期性など無い。ってか「目の数の周期性」って何？

>単に乱数に拘るのは周期が短いライブラリーなどにある乱数関数を使うと
>規則性が表面に出て見えることがある。
この文は「周期が短い乱数関数を使うと規則性が見える。」でよいか？
（冒頭の「単に乱数に拘るのは」はなんなんだろう？）

>この点であると思う。
何が？？

>真の乱数であるなばら規則性が目立っても
>それは一時的（数年続いても無限からすれば極短期間）な挙動であって
>乱数である。
最後の「乱数である。」はいらない。「挙動である。」で締めましょう。

>何かの規則で一様性な分布がほしいのであれば「無限級数」等を使えば言い訳で、
無限級数なんて関係無いでしょう。級数=数列の和　ですよ。

>人間から見て一様乱数にみえるのはシャッフルがもっとも
>近いものじゃないか？
人がどう見るかなんて、その人によるとしか言えない。
一巡するまで同じものが出ないものは一様乱数にみえないって人もいるだろう。

ところで↓こういうネタがあるんだが、どう思う?
ttp://bugfix.jp/blog/culdceptsaga/2006/12/post_42.html

>>353
釣り氏？

>>290

>>統計的に値の出現頻度が偏っているときに、それを補正することもある
>どういう補正を考えてるの？

全然わからないです．というか

>「1が続いたので次に1が出る確率を減らす」ような処理ならばNo。
>そのような数列は乱数とは呼ばない。
>乱数とは過去のデータにかかわらず常に一定の確率分布を持つもの。

私もそう思う（そういう定義しか知らない）ので・・・

>>356
ここは擬似乱数のところだから、真の乱数、つまり論理的な真の乱数を
言うのならそれなりの説明が必要とおもわれる。
実際に必要とされるのは真の乱数ではなく、擬似乱数であり
擬似乱数にはいろいろ種類があり、用途別に話しを展開しなければ
無意味な議論じゃないのか？

ほしゅ

>>330
しょ、詳細を…

>>359
カオスのバタフライ現象を簡易化した形を使うのが簡易です。
シフトとビット操作で比較的簡単に作れる。
放送大学で具体的手法まで解説していたよ。
全体を均一にしたい場合はＣＤプレイヤーなどで
使われるシャッフルのアルゴリズムが一番簡易です。
０〜９９９の間なら１０００ビットのRAMが最低必要になりますが。

CDプレイヤのシャッフルと言うと、実装方法によってばらつきがまちまちということですか?
#中には同じ曲が連続しやがるCDプレイヤも一回置きに繰り返すCDプレイヤもあるのだが。

それはシャッフル再生ではなくてランダム再生？

シャッフル再生と言い張りつつ>361のようなのはあるね。iPodShuffleも所謂シャッフルじゃないし。

Winampは完全なオプションでシャッフルから完全なランダムまで変化の度合いを設定できるんだよな
Morph Rateとか名づけてたっけ

すまん1行目訂正

Winampはオプションで完全なシャッフルから完全なランダムまで変化の度合いを

>>361
シャッフルを正しく実装しているものは同じ曲をバラバラにすべての曲を
１回づつ再生する機能のこと。
ランダム再生をしているのにシャッフルと名前を付けている
のは単に誤訳か、まがい物じゃないか？
http://e-words.jp/w/E382B7E383A3E38383E38395E383ABE5868DE7949F.html

公取委かJAROに訴えればいいのそれ？

>>366
iPodShuffule訴えてくれ。

>>368>>367
アップルに騙されたオマイがDQN

最も単純で低精度な擬似乱数の作り方てどこかにない？

どんなアルゴリズムでも擬似乱数と言い張れば、それは擬似乱数

>370
ttp://ja.wikipedia.org/wiki/擬似乱数

もっとも単純なわけでも低精度なわけでもないが
地球上でもっとも虐げられている擬似乱数アルゴリズムは
やっぱ線形合同法なんじゃね？

>>370
5かけて1足してffでマスク

>>370
擬似バタフライ効果があれば何でもいいんじゃない？

>>370
常に定数を返す擬似乱数がもっとも周期が短い。
これより周期の短い擬似乱数はない。

何も返さない擬似乱数

何も返さない擬似乱数は周期が短いとは言えない。
何も返さない擬似乱数は分布が偏っているとは言えない。
何も返さない擬似乱数は擬似乱数テストプログラムをテストするために使えない。
370の目的はたぶん最後のコレ。

>>376
定数ってだけじゃなく1bitであるべき(どうしても int にするなら 0 or -1)だろうな。
そうじゃないとbit単位のストリームとして見たときにbit数分の周期が存在することになる。

うむ、0と1の分布という点からも0か-1であるべきだな。
そして、0超過状態からの脱出という観点からは0であるべきだな。

いつのまにやらSIMD対応ほかいろいろ改良してるモノが出てるな。
まあ俺が以前いってたSIMD対応はメモリ上の並びをパズルみたいにコチョコチョいじるだけで
メモリ使用量も増やさず意外と簡単にできたんだが、
それ以外の改良となると、やっぱじっくり研究しないといかんわな。
悔しいが現役の学生にはかなわん。これは認めておいて、
とりあえずコード読んで高速化の余地を探すとするか。

どっちの乱数の方が優れているか判定をおしえろ

#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;}

#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);}

Cの標準がかなりいいんだが

>>18のrandの精度(値が小さいほど良い) 0.000233346 生成速度8.329000秒
>>84のrandの精度(値が小さいほど良い) 0.000106306 生成速度8.171000秒
自前のrandの精度(値が小さいほど良い) 0.000263426 生成速度19.563000秒
　 Cのrandの精度(値が小さいほど良い) 0.000001454 生成速度9.734000秒

#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);}

コード直貼りもいいが、うｐろだを活用してくれ

ム板的にはwikiのが良くね？

疑似乱に周期があるから、パイで検定するときは、1000回、10000回、と増やして
いって近似がパイに近づかなくなる回数を調べる事も重要

擬似乱数のことを擬似乱と略す人間は初めて見た

>>386
この精度がいいと(あるいは悪いと)どういう乱数ってことになるの？
あと、なんで win_rand() だけ 1 bit 捨ててんの？

>>391
円周率は、3.1415である
正方形(サイズは40000とする)の内部にランダムに
点を4万回打てば、それに内接する円の内部に点が打たれる回数は
31415回程度になる
試行回数を増やせば増やすほど円周率にちかずく
ここで乱数の生成が均等であるほど近くなる

このスレは共立版 knuth の3巻を読んでる事を前提にしていいんですよね?

>>392
�d。

win_rand() で 1 bit 捨ててんのはなんで？

捨てないと符号関係のエラーがでるんだが

>>395
それはなんかチョンボってないか？
俺んとこじゃ
return (double)(b[0]+(b[1]<<8)+(b[2]<<16)+(b[3]<<24))/4294967296;
で、エラーにはならんし。kaisu を 1000000あたりで試行した時は
win_rand() が断トツの精度を誇るぞ。

# 処理に要する時間も断トツだけどｗ

>>393
共立じゃなくてサイエンス社

boost::random::mersenne_twisterはだめなん？

ダメじゃないよ。
というか実質的には最強。
とりあえずwikiでも読んでみなよ。

もっとすごいのあるよ
SIMD-oriented Fast Mersenne Twister (SFMT):
ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html

WELLの登場で次世代の擬似乱数は混沌とするかと思ったが、
これでしばらくMTの系譜が続くのは確定だな

周期長っ！

速っ
ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html

boost::random::mersenne_twister「メモリぱくぱく　おいちい＾＾＾＾」

>>402
>>404
だからSFMTでは短周期版も作ったんじゃないか

SFMTのboost対応版ﾏﾀﾞｰ?

Twister 系の擬似乱数て
単にカオスの簡単な例「２重振り子」を演算で出しただけじゃん。
適度に内部ビット数増やせば、周期なんて測定不能な域にするのは容易じゃん。
ワンチップとかの超小型マイコンで作るんじゃないんだし、今のＰＣなら
乱数で使うメモリは捨てるほどあるわけだしな。

>単にカオスの簡単な例「２重振り子」を演算で出しただけじゃん。
それを実装したことに意味があるんじゃん。
…って開発者が言ってた。

>>408
似た事を主張した奴とか類似物を作ったやつも、正式に論文発表しなかった
だけにすぎない。

コロンブスなんて西に航海しただけ。コロンブスがしなくても誰かがやったよね。

コロンブスってタダの方向音痴なんじゃないかと思う

「西に向かえば地球は丸いそうだからアジアに辿り着ける筈だ」と言う発想は方向音痴とはいえまい。

西に向かって最初に見つけた陸地を西インド諸島と名付けるのはどうか。
せめて西ジパング諸島と呼ぶべきだったと思う。

コロンブス以前に原始人が海をわったったという遺伝子が原住民の
遺伝子確認で分かっている点について（ｒｙ

同時代に同じことを考えた香具師はいっぱいいる
コロンブスチームのマーケティングの勝利

このビルのガラス窓は頑丈だと証明しようと体当たりしてぶち破って死んだ弁護士もいたな

>>416
荒縄静香を思い出した

確かWeb魚拓は取っといたはずだけど どこいっちゃたｔかな

【総連】「安倍一味には負けない」総連弾圧に対して措置取る…朝鮮外務省代弁人声明
ttp://news21.2ch.net/test/read.cgi/news4plus/1183572310/l50

>>406
斉藤君に連絡とってみるかな。
個人的にはSSE2非対応CPU向けにMMX版くらいは欲しいんだが。

本人が動いてくれるくれないにかかわらず、SSE2版だけならVC8/ICC用の
クラスを作ってみようと思うが。どうせ俺が使うし。

で、SCEからオファーはきたの？

音沙汰無いよ

Cスタイルのコーディングってさ、どうしてグローバル変数汚染しようとするのかねぇ。
スレッド毎にインスタンス生成すればスレッドセーフうめぇｗｗｗｗ

スタックに作ればいいやん

たとえばさ、MTのgenrand()を複数のスレッドから参照してみてごらん。必ずおかしなことがおきます。
BoostのRNGは全部クラス化してあって一時計算領域もインスタンス毎に生成するからスレッドセーフなのよ

乱数生成ルーチンがバグってて出鱈目な値を返していても誰も気がつかない罠

内部ベクトルでかいんだから、ミューテックスのがよくね？

おいおい19937ビット＋αだぜ？

TLS使えばしまいだろ

>>428は>>422宛ね

TLSとは何か。

Transport Layer Security
Thread Local Storage
True Love Story

いろいろあるんだな……

いや、内部ステートをスレッド毎に持つというのは
確かに複数スレッドからの同時アクセスの点では良いのだが

例えばよく使われるsrand()はどうするのか。
スレッド毎にsrand()を呼ぶのか
あるいはsrand()の内部でスレッドを数え上げるのか
srand(time(NULL))の後にスレッドを作成したらどうなるのか
↑を最初に一度だけ呼んである過去のコードの扱いはどうなるのか
等々、面倒くさいことがありすぎるよ。
まともなコードで、srand()を呼ばずにrand()を使っているものがあるとは思えないし。

もちろん、「標準のrand()」を置き換えるのではなく
「自分で使う乱数生成器」をどうするか、という話なら
好きなようにどうぞ、というだけだけど。

そりゃ各スレッド毎にパラメータがあるわけだから、それぞれに初期化が必要になるだろうね。
種は現在時間＋スレッドID＋GUID/UUID＋HDDシークタイムからとった自然乱数もどき＋・・・・
見たいな感じでいろいろ組み合わせればよくね？

最近のMTの派生実装は種を配列で与えることができるんで、ユニークな乱数列になるように
なるべく多くのパラメータを与えるといい。
MTは種さえ被らせなきゃそこそこうまくバラけてくれる。

CryptGenRandは？

そういう話かよ？

ワークメモリがスレッド毎に独立してると、たとえばモンテカルロみたいなのを複数スレッドで分割処理やりたいときに有用。

プロセスを分ければいいと言われると返す言葉がないがね。

>>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);

CryptGenRandomって自分じゃジェネレートしてないのに、なんでGenRandomなんだ？
GetRandomじゃないのか？

その Gen は Generate ではなく、元、つまり集合の1要素だって
おじいちゃんがゆってた。

「源」じゃないの？
すなわち「おじいちゃんの名前（ゲンじいちゃん）」
え？ちがう？

ﾗﾗ… わしゃ悔しいわい

アゴなしの人か。

ＤＤＡで円の軌跡を計算して、それを２重にして乱数作ったんだが、
擬似乱数として性能がいいのか調べる方法はある？１から１０までの分布は
それらしくなっているんだけどな。

だんごやさんはSSE2用sfmtをboostに移植しようとしたがテンプレート地獄に涙目

ビット毎の出現確率でも調べたら？

>>442
どっかに基準とはる判定方法があったかも

とりあえず、こんなのは見つかった。
DieHarder: A Random Number Test Suite
Robert G. Brown's General Tools Page
http://www.phy.duke.edu/~rgb/General/dieharder.php

>>446
乱数検定の定番だな

いろんな圧縮アルゴリズムにかけて
圧縮率を見るのってどうなの？
邪道？

簡単なテストにはなるだろうけど、信頼性はかなり低いと思う。
zipで圧縮して50%になる乱数とかはそもそも論外だし。

はっきりした規則性があるのに圧縮率は低い、といった
データを作るのは簡単だから。

圧縮してみるというのはNISTにあったけど、今はない（非推奨？取り下げ？）

擬似乱数のテストは、あとはWELLの設計者たちによるtestU01くらいか。

無相関性擬似乱数アルゴリズム
http://www.trickpalace.net/column/random.htm

↑一般には、初期化以外の部分でエントロピーを取り入れたら擬似乱数とは言わないと思う。

>>452
再現性があるから疑似乱数だよ。

>>466アンカーミス？

>>454
( ´∀｀)

なんだこれ？
ＰＣで見た時と携帯で見た時で番号がずれてるぞ。

最近携帯鯖は不安定だからな

>>452
初期化以外の部分ってどこのこと？

Boostっていくつも擬似乱数クラスがあるけど、
その中に >>451 みたいな思想のヤツってないの？

>>451
なんかよく分からんがテーブルの中からいくつかの要素を取り出して
XORして出力してるのかな？
テーブルの状態次第でビットの出現比に偏りがでそうな気がするんだが。

>>458
失礼、用語に騙された。要するにエントロピー供給してないのね。
問題外じゃん。まず、状態空間の大きさとそれに対する最低周期

101+103+107+109+113+127=660
101 * 103 * 107 * 109 * 113 * 127 = 1741209542339 ≒ 10^12 ≒ 2^36

>>460
現状では出現比を特定できないほど巨大なテープルを用意できると
考えるのが妥当じゃないか？
気がするレベルではなく、偏りが計測できなければ、微小の偏りなど
有効誤差の範囲でしょう。
乱数であるかぎり特定の位置と周期でみれば偏りは常に存在する。
言語に付属するライブラリーが吐く擬似乱数が余りにも周期が短く
偏るためにいろいろ別の方法を試す奴が多いが、目的ごとにその方法論は
変わってくる。例えば組み込みの４ＫＢ以下のＲＯＭしかないマイコン用の
擬似乱数と考えれば偏りの無い性能より超コンパクトで一様に出るほうが
無難である。大量の計算を必要とする模擬計算などでは応答性の速度が
重要だったりする。あまりにも複雑な計算をして結果を生むより、適度に
妥協するのが擬似乱数の役割で、何が一番良いというのはありえないと思うが。

>>463
巨大なテーブルにエントロピーを満たすのがえらい大変だと思う

>>462
かけ算だから細かく分けた方が周期が長くなる
MTと同程度のメモリとすると2番目の素数から20番目の素数までぐらい
Sum[Prime[i],{i,2, 20}]
637
最大周期は十進数の桁で
N[Log[10, Product[Prime[i],{i,2, 20}]], 5]
26.446
二進数の桁で、
N[Log[2, Product[Prime[i],{i,2, 20}]], 5]
87.850
最低周期は，エントロピープールから持って来ている以上、
全部おんなじ値という可能性が否定出来ない。よって１

>>18
これイイな。
ちょっと乱数が欲しい時にちょうどいい。
MT使う程でもないけど線形合同法は気分的に嫌なんだよな。
下位ビットになるほど周期が短くなるのがな。
こういうの他にないのかな？
2^64 - 2^128位の周期で速くてメモリ使わないやつ。

いろいろご意見ありがとです。

>>460
アルゴリズム的に意図的に用意したエントロピープールでも使わない限り、
変な偏りがでることはまずないです。


>>461
擬似乱数関数に第一に求められるのは周期でも速度でもフットプリントのサイズでもなく
その出力される乱数列上に相関性が表れないことだと考えて作りましたですよ。極端な話、
相関性がどれだけ現れようが容認できるのであれば乱数なんて使わずにカウンタでも
使ってればいいわけですから。

MTが周期の為にメモリを消費してるのに対してこの乱数アルゴリズムは品質の為に
メモリを消費してるんで、メモリ消費に対する周期効率は悪くて当然で、気にしとらんです。

とりあえず論文の形にしてどこかに凸してみてくれ

>>464
そこまではいらないです。この乱数アルゴリズムで生成された乱数列も、
一応、建前上は相関性のない乱数列なんで、例えば 2^32 なインスタンス
を二つ組み合わせて(4294967279x4294967291) 2^63 な周期を実現で
きるですよ。その分、乱数の生成速度にも影響はでちゃいますけど。


この手のものはいろんな批判に耐えることができてなんぼって面もあるんで
いろんな批判もウェルカムですけど、この乱数アルゴリズムは本当に優れた
ばらつきの乱数列を出力できるんで、是非とも皆様、他とは異なるこの上品質
の乱数列を一度ご賞味くだされ。

いいこと思いついた！
これとMT組み合わせれば最強

>>467
論文はちょっと・・・
でも、仕事で付き合いのある情報セキュリティ関係の数学者に
今度会う機会があったら見てもらおうかなとは思ってます。

>>469
水と油というかうまく組み合わせるのは難しいんで、
なんかいいアイデアがあったら教えてください。

乳化剤のイメージ

>>451
本題と関係ないけど、コードの突っ込み。
環境(私が確認したのは2000と2003)によるけどCryptGenRandomしか使用しない場合は、
CryptAcquireContextのdwFlagsにCRYPT_VERIFYCONTEXTも指定したほうがいいよ。

>>451
そもそも MT で奇数と偶数が交互だったり、プロットで特定の形に集中したり、
過去の結果から予測できることなんてあるの？

それがないなら MT でいいじゃんってことになると思うんだけど。

>>468
いや、これって質の良いエントロピー源が存在することを前提として、
それを少し引き延ばしているだけなんだよ。
でも、質のよいエントロピーを得るのは結構難しくて、
多くのビットを捨てることによってなんとか質を上げているのが現状。

濃縮スープがあれば、薄めてスープが作れますという感じ。

MTの質が悪いなんて聞いたことがないんだが。
MTの長周期を考えたら出力をプールしてxorすれば良さそうに思える。

>>468
よう考えてつかぁさい。
ランダム情報源じゃぁ、それまでに出現した数とこれから出現する数との
間にゃぁ関係がないっちゅうなぁほんまじゃ。例えてゆぅたら、サイコロ
を二回振った時に、１回目に出る目と２回目に出る目の間にゃぁ関係がなぁ
のぉ。
ほぃじゃが、それと、ある特定の取り出した値の間に関係がないことたぁ
別なんよ。サイコロを二回振りゃぁ、例えてゆぅたら（１，１）が出るか
もしれんわけで、普通の人はこの二つん目の間にゃぁ関係があるとみなす
わけじゃ。

まあ、実際にプログラムを書いて実験してごらんさい。
ほいで結果をＭＴと比較してどこが違うんかを表なりグラフなりにしてみ
たらどうじゃろうか。
論文を書いてみるんも、参考文献を読まんにゃぁいけんっちゅう点じゃぁ、
よいゆぅて思いますけぇの。

でもそんなの関係ねぇ

malloc() は断片化するから危険って言って、 malloc() より遥かに質の悪い
アロケータを自作しちゃうのと同じ感じがする。

>>479
動作するプラットホーム、ＣＰＵ等に激しく依存するので何が正しいかは
動作させなければ判断は難しい。

前のはなしになるが >>111 が MT の出力を圧縮できたと言っていたが、
おれはできなかった。>>111 は MT の使い方を間違えたんじゃないかな。

#include <stdio.h>
#include <stdlib.h>
#define main dummy
#include "mt19937ar.c"
#undef main
long buf[262144];

int main(void) {
int i; FILE*fp=fopen("test.dat","wb");
for (i=0;i<262144;i++) buf[i]=genrand_int32();
fwrite(buf,4,262144,fp);
fclose(fp);
system("zip test test.dat");
system("lha32 a test.lzh test.dat");
return 0;
}

テストコードをdefineで回避するアイディアに脱帽。

>動作するプラットホーム、ＣＰＵ等に激しく依存するので何が正しいかは
>動作させなければ判断は難しい。

だが、動作させなくてもわかるほど確実に悪いものも、たくさん存在する。

>>473
情報�d。ちなみに今の trickrng.h のそのまわりの実装は MS の knowleg base から
パクってきたモノです。Crypt API まわりは下手に弄るとマシンによって動いたり動か
なかったりが出やすいんでよく調査した上で検討させて頂きますです。

>>474
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
「暗号用の乱数として使いたい」のところ。

>>475
正に仰る通りで、おいしいスープができたんで是非ともご賞味ください。

>>477
３行でお願い。

>>479
そうでなければ喜ばしいんですけどね。

もう熱雑音を種にMTを読み飛ばしながらつかってりゃいいよ

>>465
古典だがLFSRは?

>>451
「nビットの真性乱数からmビット(m>n)の真性乱数を演算で生成する」ってのを
しようとしてる? ...わけじゃないよね。それは原理的に無理。
# 昔圧縮で同じようなことを主張した会社があったっけか

「nビットの入力列からmビットの乱数っぽい数値を演算で生成する」のが
疑似乱数アルゴリズムなわけで、入力列に真性乱数を与えるとみなすなら、
入力エントロピーを引き伸ばして使ってるって意味ではみな同じでは。
線形合同法とMTが五十歩百歩なら、何を持ってきても五十歩百歩な気がする。

まあそれはさておき、入力エントロピーを薄め過ぎない方向に振るってのは、
発想としては面白いかもね。
ただ、既存の疑似乱数や暗号論的演算のコンボに実用性の観点で勝ち目があるものを
さくっと作れるのかというと、正直厳しい気がする。

>>451
統計的な検査はよく分からんので置いておくとして、遅すぎ。
インデックス決めるためだけに呼び出す毎に整数除算8回もしてる。
試しにVC++(ver.7)で1億回呼び出すコード書いたら(releaseビルド)

0.578 (>>18のやつ)
1.000 (VC++のrandたぶん線形合同法)
1.672 (MT19937)
156.016 (>>451)

だった。(単位は秒、CPUはAthlonX2 3800+,WinXP SP2)

さっぱりメリットが見えてこない

すまん間違えた。
やりなおし

0.516 (>>18のやつ)
1.078 (VC++のrandたぶん線形合同法)
1.766 (MT19937)
17.015 (>>451)

>>484
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
> 「暗号用の乱数として使いたい」のところ。

MT に対する優位性が暗号論的な安全性にしかないってこと？
その用途ならそもそも >>451 の種にできるようなエントロピーを
直接ぶっこむべきなんじゃないの？

何か >>451 を使うのが最適（MTでもOSの乱数でもダメ）っていう
現実的な例が欲しいかな。

>>491
同感。得意な領域でもいいから、優位性があるところをデータで示してほしい

なんか突っ込みどころ満載だな。
>>451
assert(0 != master_list[master_list_size -1]);
これ意味あるか？
1/2^32の確率で正しいテーブルがエラーになっちまうよ。

http://www.interq.or.jp/snake/totugeki/hdrand.htm

すでにあるじゃん
ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/CRYPTMT/index-jp.html

>>484
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
> 「暗号用の乱数として使いたい」のところ。

予測できるのが嫌なら、そこに書いてあるとおりハッシュを噛ませれば良いんじゃないの？
そういう意味ではなくて？

数学的な漸化式の形になってるのが嫌なんじゃないの？

皆さん、いろいろご意見、ありがとです。

>>487
>「nビットの真性乱数からmビット(m>n)の真性乱数を演算で生成する」ってのを
>しようとしてる? ...わけじゃないよね。それは原理的に無理。

先述の数学者の先生にそのへんのことはいろいろ教えて頂いているおかげで知ってるですよ。
あと、真性乱数だと今度は逆に偏りが出やすくばらつきが悪いって欠点もありますし、
あくまで目指したのは良質な擬似乱数でするよ。

>入力エントロピーを引き伸ばして使ってるって意味ではみな同じでは。

このへん、私の考えが変なのかも知れませんが、MT は本質的にはカウンタであると
同時に本質的には 1 bit もエントロピーを持ち合わせていないとすら思ってます。
( 別にそれ自体は悪いことだとは思いませんけど。 )

実際 MT は多倍精度高速カウンタとして非常に強力ですよ、あのアルゴリズムは。

# 実際に多倍精度高速カウンタとして使うにはデコーダを用意する必要がありますけど。
# →で、そのデコーダがあれば 623 個の出力から MT のその後出力が全部わかるです。

>ただ、既存の疑似乱数や暗号論的演算のコンボに実用性の観点で勝ち目があるものを
>さくっと作れるのかというと、正直厳しい気がする。

出力される乱数列の優位性をできれば数値で測定・証明したいとは思ってます。
仰る通り、厳しいでしょうけど。

>>488,>>490
重鈍なのはよく承知してます。恐らく一番ネックになってんのは剰余算やXORを
何度もやってることじゃなくてテーブル参照だと思います。最適化が綺麗に働けば
>>18 のヤツなんて全部レジスタに収まっちゃうんで、メモリ参照が必要な prime
spiral では絶対に敵いません。

prime spiral にあるのは「上質な乱数列」、ただそれだけです。

>>491
ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。

>>493
例えば自前で csv を用意した際にデータが足りてないと致命的なんですが、
乱数であるが故にそれが非常に分かりにくいという問題があるんで過剰な
assert であることを承知の上でミスを検出できることを優先しました。

>>495
それはそれ、これはこれ。それは MT の仲間ではあるかも知れませんが、MT
そのものではなく、必然的に特性も MT とはいろいろ違うでしょうし、わけて
考える必要があると思います。実情はどうか知りませんが、情報セキュリティ
向けの対策を施されているということは一般的に考えて素の MT よりは処理が
重く、また乱数列としてのばらつきは悪くなっていることなどが予想されます。

>>496
予想できること自体は私は問題視していないのですが、それは乱数列上に
問題を起こしかねない相関性を含んでいる証左なので。

>>497
それ自体はあまり気にしていないのですが、私は乱数列上に現れる相関性を
擬似乱数のバグのようなものだと捉えていて、その延長線で、多くの擬似乱数
アルゴリズムはそのバグを根本的に解決しようとするのではなく、バグの
再現率を下げて分かりにくくし誤魔化せればそれでよしとしているように
解釈してしまい、どうにも私にはそれが受け入れ難いのです。

紛らわしい返し方しちゃったんでちょい補足。

>>499
>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。

これは、prime spiral じゃなくて MT の話です。

>>500
MTは高次元（623次元）に均等分布することが証明されている。
このことは出力中の連続する値間の相関性が無視できる程度しかないということを意味する。

MTで問題があるというのは結構ですが、
貴方が作ろうとしているものは、それ以上の高次元に均等分布し、
数学的にちゃんと証明できるんですか。

>>502
とりあえず

>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。

なんて問題はないです。

>>502
均等分布の意味を私が取り違えてなければ prime spiral は 2^32 次元を超えてます。

>>503
んで、周期はどうなるの？そっちのほうが問題だと思うが。

>>504
根拠は？

>>499
＞ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。

ないだろ。出鱈目書くなよ。

>>504
あ、ごめん、やっぱり多分勘違いしてた。
MTで言ってる均等分布 623 次元空間を隙間なく且つ重ならずに埋め尽くすって意味ね。
だとしたら、prime spiral は 2^4800 パターンで 2^32 を超える次元に広がるんで隙間が現れます。

>>505
バグを直さずに周期もなにも・・・てな考えなんでごめんなさい。

>>507
ソースでも読んで。・・・と思ったけど、このへんはすでに改善されてる？

orz


数年ぶりに mt のソース見て、思いっきり記憶違いしてることに気づいた。
俺の mt に対するコメントはいったん忘れてくれ。
検証し直したあとでまた mt に対する見解を述べます。大変、申し訳ない。

2^32 次元って・・・

このひとのボケっぷりからして、32次元の間違い以外の何物でもない。
そして、32次元均等分布もウソだろう。

批判するなら最新のものもチェックしておけよな

>>508
http://tricklib.com/cxx/dagger/trickrng.h
見たが、周期はどんなに良くても10^10ぐらいしかない。
初期ベクトル（エントロピープールという恥ずかしい名前が付いているようだが）の状態によっては、
悲惨な結果が待ってるな。

正直ゴミだと思う。MT叩く前に数学の世界を舐めるのを止めたほうがいい。

>>513
追加。
ちなみにこれを、10000以下のすべての素数を使って実装しても、MTの周期に及ばない。

XORとシフトを使うだけの超高速な擬似乱数生成アルゴリズム「Xorshift法」
http://lucille.atso-net.jp/blog/?p=9

MTって最後に調律、とかやって遅くなってるのがいまいち。
M系列乱数の方が明らかに速いし、無理にMTを使うメリットが見えてこないんだけど。

M系列で要求仕様を満たすならM系列で問題ないと思う。
生成速度だけが擬似乱数に求められる性能ではないし、要は適材適所だよ。

>>516
というか、MTで速度が不満ってどういうこと？
全体の負荷の何パーセントをMTに持ってかれるの？
そういうところを無視して、速度を語っても意味がないぞ。数パーセントならマシン買いかえればいいんだし。

＞マシン買いかえればいいんだし
えー

負荷の割合で語るのも意味無いぞ

>>515
>>18で超既出

>>516
そこらへんはSIMDでなんとかならんかなあ

MT使ってソフトを配布してる人って、ちゃんとcopyrightも付けてるの？
俺が乱数ルーチンを作ったんだ！と主張したいんだろうけど、
たかが乱数ごときで、毎回書かなきゃならんのもなんだかな。

コピーライト表記はしらんけど
修正BSDライセンスかなんかだったような

>>523
アルゴリズムに著作権はないよ。サンプル実装のソースコードを、
そのまま使ってるなら、ソースコードには著作権が発生するけど。

>>509
敵を知り、己を知れば…

そう、つまり最初にすべきは敵をちゃんと知っておくことなんだよね。

>>508
> だとしたら、prime spiral は 2^4800 パターンで 2^32 を超える次元に広がるんで隙間が現れます。
周期 2^32 以下なのに、どうやって 2^32 次元に均等分布するのか謎だが…

>>527
やあ、あんた少しはわかってる人だね。

>>516
M系列の方が明らかに周期が短いだろ

>>515
XORSHIFTはMTの周期や均等分布次元が必要でない時には、
実際に有力な選択肢だ。SFMTの速度比較でも速いと出てるしな。

prime spiral のバラつきを見てみたが、かなり出てくる数値に偏りがあるな。

2^20 回試行して集計かけたところ、こんな感じ。

　1度しか現れない数値　30.9%
　出現回数が多い数値
　　0 (2656回)
　　8 (2637回)
　　32759 (2452回)
　　…

ちなみに MT だと、こうなる。

　1度しか現れない数値　99.9%
　出現回数が多い数値
　　113個の数字が2回出現
　　他はすべて1回出現

周期とかは見てないが、この時点で、すでにまともに解析する気なしってことで。

>>526
というか、それ以前に敵ではないものを敵と勘違いしていると思われ。

「敵」の姿を勝手に思い描き、己の姿も勝手に思い描いている。
そして、想像上の何者かと想像上の「己」が、
何かを戦っているつもりになっている。
これを妄想という。

夢みのりがたく、敵あまたなりとも、我は勇みて行かん

乱数検定のやりかたおせーて

>>529
周期が短い場合はそのとおり、周期がとてつもなく長い場合は
偏りも乱数であり正しい性能である。
後者であれば、長い周期を測定できない評価ソフトの性能が悪いことになる。

2^32までチェックしろと？

>>534
周期以前にprime spiralは乱数になっていないのが問題。線形合同法にも劣る。ゴミだ。
2^20の試行で、0が2^11も出ている時点で正常な分布ではなく、2^32までチェックすることもなく明らかだ。

>>534
> 周期が短い場合
prime spiral は内部状態が 32bit 符号なし整数1つだけなので、周期は最大 2^32 だよ。

初期ベクトルとしてもう少しマトモなものを選べば改善されるかもしれんが、いずれにしろ
やる気ないです。はい。

>>529
どこか間違ってない？
別に擁護するわけじゃないけど、
俺も実験してみた結果、
100万回(2^20)出力して同じ値が出たのは
133 (>>18 xorshift)
146 (mt19937)
105 (>>451 prime spiral)
だったよ。
出力は全部unsigned int(32bit)。
ちなみに俺は>>488,490の人。

個人的には今のところ、周期が短すぎ、遅すぎというのを除けば
テーブルの初期化が適切であると言う前提ならそこそこの品質には思える。
でもテーブルに完全に依存しているから、
mtのような多次元均等分布は不可能なんじゃないかな？
テーブルを大きくすればするほど遅くなっていくし。(指数関数的に)
唯一のいいところはテーブルの状態が分かっていてもカウンタが
分からない限り過去の出力からは次が読めないところかな？

なるほど、次を予測しにくい乱数アルゴリズムなわけか。
初期化の問題は（MTもそうだけど）
どこかからエントロピー持ってくるAPI（CryptGenRondom）やら
物理乱数生成チップやらでどうにかならないか？

>>538
ソース出せ。こっちでも実験＆分析してやるから。
prime spiralが如何にゴミであるか証明してやるよ。

>>538
＞唯一のいいところはテーブルの状態が分かっていてもカウンタが
＞分からない限り過去の出力からは次が読めないところかな？

お前本人じゃねーの？
あれが「過去の出力からは次が読めない」って本気で思っているのか？
簡単にわかるぞ。あんなもの暗号に使ったら大変なことになる。

そんなボケかますのは本人以外ないと思うが、馬鹿がもう一人いるのかもしれんな。

予測不可能にするなら、MTにハッシュ(SHA)付ければ十分だ。

無闇にageんなや

>>538
#include <iostream>
#include "trickrng.h"

int
main()
{
tricklib::prime_spiral_entropy_pool g1;
unsigned const LOOP_MAX = 1 << 20;
for (unsigned i = 0; i < LOOP_MAX; ++i)
std::cout << g1.shuffle(i) << "\n";
}

できたテキストファイルを DB に取り込んで、グループ化かけて集計した。

>>539
> なるほど、次を予測しにくい乱数アルゴリズムなわけか。
んなわけない。

内部状態が 32bit しかないので、周期は必然的に 2^32 以下。brute force でも
2^32 回の出力を見て記録していおいたら確実に次は予測可能なので、賢い
解析アルゴリズムを考えるまでもない。

#define X ( 1 << 20 )
#define uint unsigned int

uint *buf = (uint *)malloc( X * sizeof(uint) );
if ( buf == NULL ) return;
tricklib::prime_spiral_dice dice( 100 );
for (uint i=X; i--; ) buf[ i ] = dice.roll();
sort( buf, X );//なんでもいい。シェルソート使った。
uint cnt[ 32 ], same = 0, p = buf[ X - 1 ];
for (uint i=X-1; i--; ) {
uint t = buf[ i ];
if ( t == p ) {
same++;
} else {
if ( same > 31 ) same = 31;//オーバーフロー対策
cnt[ same ]++;
same = 0;
}
p = t;
}
メモリに全部書き出してソートして前と同じならカウンタをインクリメント。
>>529
それ多分使い方違う。
テーブルが初期化されてない。
まあ、テーブル次第で悲惨な結果になるという見本ではある。

分かると思うけど作者じゃないよ。
アルゴリズム的に穴が多いから自分は使う気はないし。

ごめんコピペじゃないんで一部ミスってる。
cnt[ 32 ]はstaticつけて0で初期化してね。

それだとちゃんとカウントできんだろ。
最大の残したりできないから、上書きされるんじゃないか。

>>547
上書き？はされないと思うけど。
最多31でカンストするようにはしたけど。
よく読んでおくれ。
同じのが3回以上出ることはなかったよ。

>>548
いいから、出力結果をテキストファイルに出して、目で読んでみろ。

>>549
あんたはなんで俺にからんでんの？
>>529,543のコードはどういうわけか
構造体のインスタンスを生成して実験してるから
テーブルが初期化されてなくてゴミが詰まった状態なんだっての。
テーブル次第で2^20の試行で、0が2^11も出たりすることもあるけど、
デフォルトのテーブルではそんなことはなかったって話だよ。
落ち着きなよ。

>>550
だったら、この発言を取り下げろ。

↓

唯一のいいところはテーブルの状態が分かっていてもカウンタが
分からない限り過去の出力からは次が読めないところかな？

唯一のいいところがなくなったら、
いいところゼロのゴミであることに同意するんだな？

>>551
はいはい取り消すよ。
別に俺が作ったわけじゃないし。
少なくとも一周すれば確実に次が読めるね。間違いない。

>>552
ゴミだとは思わんけどな。
そういう考え方もあるのかってくらいのもんだよ。
ただ自分は使わないだけ。

>>545
テーブルダンプしてみたら、確かに初期化されてなさげ。

00000000 00000000 00509146 00000008 00000000 00000000 005271a0 00000008
ffffe630 00007fff 00000000 00000000 00000001 00000000 078e530f 00000000
004004d1 00000000 00509270 00000008 00000001 00000000 00528600 00000008
ffffe628 00007fff 00000000 00000000 ffffe670 00007fff 00000000 00000000
00000001 00000000 078e530f 00000000 004004d1 00000000 00509369 00000008
00528000 00000008 00528200 00000008 00528400 00000008 00528600 00000008
00528000 00000008 00528200 00000008 00528400 00000008 00528600 00000008
00528800 00000008 00528600 00000008 00503a88 01000008 ffffe690 00007fff
00528000 00000008 00528600 00000008 ffffe5c0 00007fff 00000005 00000004
00528000 00000008 00000000 00000000 00000013 00000000 00000001 00000000
004003e0 00000000 004004d1 00000000 00528000 00000008 0050964a 00000008
00400368 00000000 ffffe6d8 00007fff 00528600 00000008 00528000 00000008
00500e40 00000000 00000001 00000000 00000000 00000000 0050bae9 00000008
00950880 00000008 005097bb 00000008 00000000 00000000 00528600 00000008
00000001 00000000 ffffe7d8 00007fff ffffe7c8 00007fff 0050747d 00000008
00000246 00000000 ffffffff 00000000 ffffe4e8 00007fff 00000000 00000000
00500b08 00000000 00500ea0 00000000 00c61910 00000008 00000001 00000000
00400764 00000000 00000206 00000000 00000000 00000000 00528000 00000008
00000001 00000000 0040088d 00000000 00000001 00000000

>>555
あ、やっぱそうでしょ？
でもテーブルがこんなことになってしまう可能性もあるわけで
アルゴリズム的には問題ありなのは事実ですな。
統計的にも不安だし。

なんか盛り上がってきたようだが…

そういや作者の人は MT のコード読み終わったの？

>>554
でも唯一のいいところもないってことだね。

>>558
唯一のいいところ＝自己満足

で良いじゃないの？　俺言語とか俺DBとか俺ステートマシンとか、いろいろ HDD に
眠ってるぜ orz

>>559
それは構わないけど、それは作った本人にとってであって、
第三者として利用するのに、自己満足も糞もないんだが。

>>560
まぁねぇ。俺も使う気ないし。

ML で延々やられるよりは、2ch で自己満足に浸ってくれてた方が害が少ないので、
ここに閉じ込めておくのが吉かと。

MTにもバージョンがあるからな。
最初のバージョンは結構素直だが、
今のは微妙に最適化されてたり
そのくせ古いバージョンの名残の変数名が使われてたりしてちょっと読みにくい。

あとはコーディングスタイルがCらしすぎてちょっとアレ。
下手すると第三者の最適化版とかのほうが読みやすくなってたりする。
（ダンゴが同じようなことを上の方で言ってた気がする）

>>543
prime_spiral_entropy_pool ではなく prime_spiral_dice を使うのが正しいんじゃ?
って550にもう書いてあるか。

つか、環境依存マクロで内部実装が何ヶ所か切り替わってしまうんで
同条件での比較ができてないんじゃないかという気もする。
そのせいで偏ったとか偏ってないとか話がすれ違ってるんでは。

次のコードでやってみた。環境はx86-linux、コンパイラはgcc-4.2.1。

#include <iomanip>
#include <iostream>
#include <ostream>
#include "trickrng.h"

int main(void)
{
　using namespace std;
　tricklib::prime_spiral_dice prng;
　const unsigned int n = 1 << 20;
　for (unsigned int i = 0; i < n; ++i) cout << prng.roll() << endl;
}

$ ./a.out | sort | uniq -c | awk '{print $1}' | sort | uniq -c
1048342 1
　　117 2

てことで、漏れの手元ではダメな偏りは観測されず。

書き忘れたんで補足。
最終結果の数値は、
「1回出現した値が1048342個、2回出現した値が117個。他はなし」って意味。

もちっとましな検定とその結果を見てみたいが、
漏れは乱数素人なんで方法がわからず。

まあでも、prime_spiral_diceクラスのインスタンスの「更新される内部状態」は
uint32_t型のメンバ変数"index"だけなんで、
疑似乱数の周期は>>544の指摘通り2^32以下。
あまりがんばる気にならんかも。

ソースには dynamic_prime_spiral_dice ってのもあるけど、誰か追った?

>>565
コンストラクタがテーブルを乱数で書き換えてるだけだよ。

そうそうカウンタが32bitしかないから
定期的に別の乱数でテーブルを書き換えた方がいいと思うんだ。
全部とは言わないけど一部だけでもね。
自身の出力を使って書き換えると意味がないから
別の系列の乱数でってことになるんだけど、
そこまでやるならやっぱMTとかをハッシュにかけたらいいじゃんて話なんだな。

>>566
thx。インスタンスごとに別々のテーブルを持ってるだけで、
初期化後はテーブルを書き換えないって点では prime_spiral_dice と同じか。
疑似乱数アルゴリズムの評価って意味では見なくていいね。

>>567
単に乱数を得るって意味では、時々 secure_dice_type を振って混ぜればいいかと。
疑似乱数とは呼べなくなるんだろうけど、うまくすれば使えるようになるか?
もっとも、テーブル更新をしない間の出力の性質がよくないとダメだけど。

自身の出力または内部状態を使って書き換える方法で性質がよくなるなら、
そっちの方がいいんだが。

>>568
> 単に乱数を得るって意味では、時々 secure_dice_type を振って混ぜればいいかと。
secure_dice_type の出力によってはテーブルが悲惨な状態になりかねんぞ。

統計的に不安定なアルゴリズムはいやん。

ふと思ったんだけど、
互いに疎な周期を持った二つの異なる系列の乱数をXORしたら
理論的な出力はどうなるんだろう？
周期が2^32と2^31とかなら間違いなく2^63になるはずだけど(互いに疎だから)、
予言可能性とかはどうなるのか？

>>570
> 周期が2^32と2^31
それ、互いに疎じゃない。GCD=2^31。

いや、そのくらいの周期でって意味。
2^19937-1はメルセンヌ数でしょ？
普通は2^19937の周期でって書くじゃん。
実際には1少なくても。

>>533
>>446
PDFだけど↓みたいなものも見つけた
ttp://www.fdk.co.jp/cyber-j/pdf/HM-RAJ103.pdf

>>563
可読性に関しては言及してないよ。C++&マルチスレッドで使うには不便すぎますよねー、て感じ。
定数定義周りはマクロじゃなくてテンプレートでなんとかなりそうだが。boostみたいに。

>>572
既知の周期 m, n の二つの系列の乱数があった場合、m + n だけ XOR された
乱数を見れば、元の乱数列が計算可能だと思う。

周期 m の乱数 x(0), x(1), ..., x(m - 1)
周期 n の乱数 y(0), y(1), ..., y(n - 1)
XORされた乱数 z(0), z(1), ..., z(mn - 1)

これで最初の m+n 個の乱数が取得できれば

x(i mod m) ^ y(i mod n) = zi

という方程式が m + n 個作れる。右辺は全部既知なので、未知数 m + n 個に対して
方程式 m + n 個あるので、あとは計算すりゃ出るでしょ。

周期が未知の場合には、もう一捻りいるかも。

>>575
なるほどなるほど。
確かにそうだ。m+nまで分かれば残りが完全に予言できるね。
でもこれってx,yを特定するのは無理だよね。
一つだけでも分かれば後は芋づる式だけど。

>>570
周期3と周期5だったら
12312312312312312312..
12345123451234512345...
-----------------------------
246564356635468246...

XORじゃなくて足してるだけだけど普通に3*5=15の周期になるよね。
2^32の線形合同法を4つ組み合わせたら、普通に2^128周期になるんじゃないかな？
乱数性はともかく。

残念ながら最大公約数にしかなりません。

今ちょっと考えてたけど系列の違う乱数がいくつあっても
全ての系列の周期が分かってれば大きい方から2つの周期を加算した
ところまでみれば残りが全部予言できそう。
違うかな？

>>578
出力の周期のことだよ。

十干と十二支の組み合わせは120じゃなくて最大公約数の60にしかならないでしょ

2^32付近の素数調べてみた？

その付近の周期の乱数も。

>>576
> でもこれってx,yを特定するのは無理だよね。
特定する意味はないな。

x, y すべてに対してある数 n を xor しても、出力がまったく変わらんから、
出力を満たす x, y の組み合わせは無数にある。

あれ？互いに疎って両方素数って意味じゃなかったんだっけ？
ごめん両方素数の意味ね。
数学の知識が高1くらいで止まってるから訳分からん事言ってるな。
すまん。

>>582
>特定する意味はないな。
分かってるよ。確認したかっただけ。

互いに素ってのは

最大公約数＝１
最小公倍数＝積

疎ですた

>>579の続き
ちょっと違うかな。
周期3,5,7の乱数があったら3と5を組み合わせて
周期15と7の乱数があることになるから
この場合は15+7=22まで見ればいいんだな。
3,5,7,11なら(3*11)+(5*7)=68かな？
もっと短く出来るのかな？

>>587
3+5+7 = 15 で良いと思うが。

今実験したところ周期を全部足せば良いみたいだ。
周期3,5,7の場合はそのまま3+5+7=15
16番目の数字は2 3 4 7 8 10 11 14 15番目を全部XORすると出てくる。

以下ソース
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define uint unsigned int
int main( int argc, char *argv[] )
{
srand( (uint)time(NULL) );
uint a[ 3 ], b[ 5 ], c[ 7 ], x[ 3 * 5 * 7 ];
for (uint i=0; i<3; i++) a[ i ] = (uint)rand();
for (uint i=0; i<5; i++) b[ i ] = (uint)rand();
for (uint i=0; i<7; i++) c[ i ] = (uint)rand();
for (uint i=0; i<3*5*7; i++) {
x[ i ] = a[ i % 3 ] ^ b[ i % 5 ] ^ c[ i % 7 ];
}
uint x15 = x[ 1 ] ^ x[ 2 ] ^ x[ 3 ] ^ x[ 6 ] ^ x[ 7 ] ^ x[ 9 ] ^
x[ 10 ] ^ x[ 13 ] ^ x[ 14 ];
printf("%d\n%d\n", x[ 15 ], x15);
return 0;
}

>>588
まったくその通りです。

しつこいけど、もうひとつ。
15個まで分かれば次の数字が分かるということで
逆に直前の15個が分かっていれば残りも全部同じ式でいける。
というか一般項に出来る。
なんか面白かったんでもう一度ソース。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define uint unsigned int
int main( int argc, char *argv[] )
{
srand( (uint)time(NULL) );
uint a[ 3 ], b[ 5 ], c[ 7 ], x[ 3 * 5 * 7 ];
for (uint i=0; i<3; i++) a[ i ] = (uint)rand();
for (uint i=0; i<5; i++) b[ i ] = (uint)rand();
for (uint i=0; i<7; i++) c[ i ] = (uint)rand();
for (uint i=0; i<3*5*7; i++) {
x[ i ] = a[ i % 3 ] ^ b[ i % 5 ] ^ c[ i % 7 ];
}
for (uint i=15; i<3*5*7; i++) {
uint z = x[ i - 1 ] ^ x[ i - 2 ] ^ x[ i - 5 ] ^
x[ i - 6 ] ^ x[ i - 8 ] ^ x[ i - 9 ] ^
x[ i - 12 ] ^ x[ i - 13 ] ^ x[ i - 14 ];
printf("%3d: %10d %10d\n", i, x[ i ], z);
}
return 0;
}

いろいろ考えていてさらに気付いてしまったのだけど、
一般項の一番最後はi-14なんで実は15個でなくて14個目の時点で分かるようだ。
周期を足して分かるのは最悪でもここまで見ればという上限に過ぎないらしい。
どうやら単純なものではないみたいだ。
さらに系列が二つの場合、数列Xは周期をa,b(ともに素数)として
Xa+b = X0 ^ Xa ^ Xbと出来る(たぶん)
系列が三つ以上ある場合はそれほど簡単でもないらしい。
さらにこの漸化式表現だと合成後の周期までは分からないようだ。
3 * 5と2 * 3 * 5は同じ漸化式に出来るけど周期は違う。
ともにXi = Xi-3 ^ Xi-5 ^ Xi-8と書ける。

もう少し調査を続けるかも。

MT に関する見解を出せるのはもっと後になりそう。
いろいろ考えてるとMTの理屈そのものになんか辻褄の合わないところが見えてきたです。
多分、論文をちゃんと見ればその矛盾に対する但し書きがあるんじゃないかと思うです。

# 例えば MT の周期じゃ 623次元で均等分布するのは不可能。厳密な意味で 623次元
# で均等分布する為には周期が n^623 の倍数である必要があるけど MT の周期は
# そうではない。

次元の話に関しては prime spiral は"素数の合計値(150)"次元のデータを
"素数の積算値(6685349671)"次元のデータに変換するアルゴリズムと言え、
また prime spiral で 2^32 周期を実現する為には 2^32を超える 次元の
データ(への変換)が必要となるですよ。余った分は単に捨ててます。

で、150次元から6685349671次元への座標変換を行うんでその結果は当然スカスカ
で MT で言う均等分布にはなりません(先述の隙間が現れるってはこの意味)。

初期化の結果によっては悲惨の出力になるって点については...

・あり得ないような確率の元データが発生したのを受け忠実に
　そのあり得ない様を出力しているだけ。
・そもそも悲惨と感じるのは人間の主観の問題であって数学的
　には特別な意味を持たない。

...という見解ではあるんですが、そもそもの prime spiral の作成目的から
すると放置するべき問題じゃないと考えますので対策しておきます。

# 次回更新時に 2^63 周期版も追加しておきます。2^32 周期版よりもさらに
# 倍ちょっと重いようなしろものですが。

内部状態を変化させればって話がありますが、prime spiral の思想的にそれは
タブーでここを崩すと prime spiral の存在理由も崩れちゃいます。

あと、"得意分野があれば"って話がありましたけど、よくよく考えてみたら
乱数列に対して簡単にランダムアクセスができるって利点があるですね。

>>593

http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E3%83%BB%E3%83%84%E3%82%A4%E3%82%B9%E3%82%BF
>メルセンヌ・ツイスタでは、状態空間が長方形から1ビットだけ突き出した（あるいは31ビット欠けた）形をしている点に特徴がある

これのことかな。他にもまだ数字の辻褄があってないとこがあるんで論文読みます。

N次元空間に均等に分布ってのは >>564 みたいなテストをN個の連続サンプルによる
N次元ベクトルについて行って特に偏りが無いってことだよね？

全部の組み合わせを埋め尽くすって意味じゃないでしょ。そういう意味なら
均等に分布なんて言葉使わないはずだし。

>>580
最小公倍数

斉藤氏見てるここ？

>>446のDieHarderの使い方を調べてみた。

まず、調査対象の乱数をファイルに落とす。フォーマットはこんな感じ。

　type: u
　count: 10 ←要素数
　numbit: 32
　1663584611 ←1乱数につき1行。符号なし10進数。要素数分だけ列挙
　1565230341
　 674637926
　...

で、dieharderに食わせる。

　dieharder -a -g 65 -f ファイル名

`-a'は「一通りテストしろ」、`-g 65'は「ファイルから読め」の意。
65って数字はdieharderのバージョンによって違ったりするっぽいので、
`dieharder -g -1'で "file_input" がどの番号かを確認。

必要な要素数はテストによって異なるけど、1,000,000個ぐらいでいいらしい。

>>601のつづき。

検定内容は ttp://www.phy.duke.edu/~rgb/General/dieharder.php の後半の
"DieHarder Test Suite" あたりに列挙されている。ただし名前だけ。

で、識者に質問。この検定って質はどうなの?
各々、名の通った乱数検定を実装したものなのか、単にオレオレ検定なのかとか。
入力が少なくていいんで、周期は検定対象外ってことぐらいはわかるけど。

>>593
辻褄が合わないのは貴方の頭の中のでしょう。
変な書き込みを匿名でするくらいなら、数学を学びなおした方がいいですよ。
prime spiralでは、MTの足元にも及びません。

メルセンヌ素数の意味わかってないんじゃね。
松本教授の論文いっぺん読んでこないとね

というか、MTの仕組みを理解していなかったのに、
自己流の変なものを作ってしまい、あとからMTの問題が勘違いだと発覚。

でも、MTに問題がないと困るから今になって必死に粗探ししているようなものだろ。
人間性から腐っているよコイツは。

MTがいったいどれだけの年月と人によって検証されてきたものか理解していないんだろな。
自分が上に立てるとでも思っているのかこの馬鹿は。

ＭＴのソースだけ読んで、均等分布とか理解するのは無理。かといってＭＴの論文は
数学以前に英語で挫折するであろう。
でも、斎藤さんのページにこんなんあったよ。これで勉強すれば？

ttp://home.hiroshima-u.ac.jp/d073872/random/5bitmt.html

>>605
誰でも一度は通る道だから、そこまで言わんでも。まぁ、ふつーは中二ぐらいで済ませるが。

M系列の乱数って出力が規則的になってしまう区間が出来てしまうのだけど
これを回避する上手い方法ってないもんでしょうかね？
ハッシュとか以外で。

>>608
よくはわからんが、MTみたいに調律すればいいんかな。
でも適当じゃダメか。

>>601
単なるオレオレ検定ではない。

ところで、入力が少ないんで周期は検定対象外だろうって書いてるけど
どんだけ入力したら、周期が検定できると思っている？

>>607
自分がすごいもの作れると有頂天になるだけか、
既存のものに疑問を持って批判するだけか、どちらかならそれほど問題はない。
それなら理解もできる。

だが、自分が上に立ちたいとか、自分の存在意義のために、
間違っていないものを間違っているとしてでっちあげるのは最低だろ。

こいつが警官だったら、自分の評価を上げるために、
自分の勘違いで逮捕してしまっても、罪をでっちあげて犯罪者に仕立て上げかねん。

社員であれば、他人の足を引っ張ったり、失敗をかぶせたり、
浅はかな考えで周囲を振り回したりする、有害な存在であろう。

あんたそりゃいいすぎだべ

>>611
実社会で迷惑をかける代わりに、ここで落書きして気が済むなら、それで良いじゃん。
日本の治安向上に役立ってるなｗ　＞2ch

で、MT は理解できたのかな？

MT に関する見解ですがまず以下の点を訂正させてください。

>多倍精度高速カウンタ
→多倍精度高速カウンタとしては高速ではない。

># →で、そのデコーダがあれば 623 個の出力から MT のその後出力が全部わかるです。
→内部状態が全部 0 になっている場合を除き 623 個じゃ足りない。もう少し必要。

>ある出力値とその 623 回後の出力値は絶対同じ値にはならないなんてものもあります。
→そんなことはない。

以上の点については私の記憶違いを端に発してる勘違いです。
大変、お騒がせしました。

今回、MT に関して勉強させて頂き、MT の出力が昔ながらの擬似乱数列に
求められる条件を理想的な形で体現しているというのはよく理解できましたです。
が、それでもというか、だからこそやっぱり MT は少なくとも私が特別な前提
条件がない状態で求める擬似乱数とは違うですよ。

別のところでも述べましたけど prime spiral 自体はそのロジックが瓦解
しちゃっても全然構わないと考えてます。prime spiral に問題がないことが
より確実な形で検証されればそれに越したことはありませんが、私が大事
だと考えているのは prime spiral のエントロピーを引き延ばすアルゴリズム
なんかじゃなくて、エントロピーを大切にし、問題を引き起こしかねない
相関性を乱数列上から根本的に排除しようという思想です。

（みんなが騒いでるのってその部分についてだっけ…）

>>499
>恐らく一番ネックになってんのは剰余算やXORを
>何度もやってることじゃなくてテーブル参照だと思います。

あと、これ、間違ってました。ご指摘通り剰余算が一番ネックになってます。
パフォーマンス改善の為に試しにMODテーブルを用意して剰余算を行わず
に処理したらどうなるか試してみましたけども、パフォーマンス上特に有効な
差異は認められませんでした。


概ね、prime spiral に関するご意見等も一通り出尽くしたみたいですので
ここらで一度、ご意見を下さった方々、速度や出力される乱数列について
検証してくださった方々に改めてお礼申し上げますです。

>>615
アイディア倒れになると良くないから、
ちゃんと数学の勉強をしてみたほうがいいと思うよ。

>>615
君は相関性もまともにわかってないから今のままだと無理だよ。
MT以上に相関性無くすのは大変だから。
prime spiralは相関性ありまくりだし。

>>616
ちょっと読み返してみた。
>>593 のことなら、確かに言葉が悪かった。
暗号なんかを含め、この手の分野の厳密さはよく知ってるから、
評価されてる論文の絶大さも理解はしてるですよ。


>>618
いいものを自分の手で作ることができればいいなぁとは思ってますけど、
この分野を専攻していこうというまでの気概はありませんのでｗ

# 数学系の厳密さはいい加減な自分には肌が合わんとですよ。

>>619
今回、勉強させてもらったおかげでよく理解しましたけど、MT は本質的には相関性の塊ですよ。
ただ、MTの場合その周期やパターンの関係上、相関性が(少)ないように見えるってだけで。

prime spiral の相関性も知ってます。というか、ぶっちゃけ意図的に問題が
発生し得ないような方向に相関性をコントロールしてます。

>>620
真面目に数学もやる気がないなら、
変なライブラリは自己満足にして、公開するのはやめてくれんか？
正直、これ以上君のような馬鹿が増えると迷惑なんだが。

＞暗号なんかを含め、この手の分野の厳密さはよく知ってるから、

理解していないから、MTに文句たれて、ゴミのprime spiralを公開してるんだろ。
まあ、やめろって言ってもやるだろうけど、そのうち、もっと恥をかくことになるよ。

まーよくわからんが、言葉は定義してから使いましょ

>>621
＞今回、勉強させてもらったおかげでよく理解しましたけど、

まだ理解できていないと思われ。
理解しているなら試しにより周期の長いMTを作ってみてごらん。

＞MT は本質的には相関性の塊ですよ。
＞ただ、MTの場合その周期やパターンの関係上、相関性が(少)ないように見えるってだけで。

違うよ。疑似乱数だから相関性があるのは当然だが、
prime spiralのような劣悪な相関性はないのは君は理解していないだろ。

＞というか、ぶっちゃけ意図的に問題が
＞発生し得ないような方向に相関性をコントロールしてます。

できていませんが？どこでコントロールした気になってるの？

煽りには付き合う気は毛頭ないんで、ごめんあそばせ。

>>625
どうぞ。失せてくれ。
煽りでも何でもなく、欠陥の指摘をされても理解できないようだから。

>621
相関性って何？周期って何？
というのはトモカクだ、

本質的って何のこと？
パターンって何のこと？
問題って何のこと？
方向って何のこと？

を書いてくれないと議論できない。今更だけど。

まあ、しばらくしても続けているようだったら、
prime spiralが相関性ありまくりで最悪であることを証明して投稿してやるよ。
数学の世界を舐めてもらったら困るので。

>>624
MTFSは長いのやら短いのやら選択できたっけ。

>>628
>prime spiralが相関性ありまくりで最悪であることを証明して投稿してやるよ。

ごめん、これはぜひ、お願い。
検証にご協力頂けるのは助かります。

>>629
できる

>>630
> 検証にご協力頂けるのは助かります。
ふつーは専門家に検証を頼むなら、論文ぐらい書くもんだぞ…

言葉も明確に定義せず、参照論文や related work も示さずに、あまつさえ
タダで評価してもらおうなんて、虫がよすぎるとは思わんか？

>>630
>>625のように真面目に答える気がないなら、今はやだね。
君が自信もって発表して、恥をかくタイミングまでまってやるよ。

ちゃんと説明する気があるなら、協力してやらないこともないけど。

>>628
それは俺も楽しみにしてるわ

>>633
もう発表してるんだから、早く早く！

>>632
返す言葉もございません。m(_ _)m

>630
うーん、本来は逆だよな。

prime spiralがある切り口で最高であることを作者自身が証明する
のが筋じゃない？ それなしで検証とか言われてもなー。悪魔の証明
を思い出した。

折角作ったのに叩いて悪いんだけどさ。

プログラマは数学から距離を置く方がいい仕事ができると
ポールグレアムも言ってるだろ。。。

車輪の再発明どころか、車輪の再失敗をしてどうするのだろうね・・・。
斬新なアイデアでもなんでもないのに。

>>637
重ね重ね、返す言葉もございません。

>>637
例外に Knuth っつー巨人がいるから、みんな目を奪われちゃうんだよな。

（ところでこのスレ今何人いるんだろうね。4人位かな）

2!

>>640
ノイマンも

>>638
アイデアとして別に真新しいものじゃないのはわかってる。
ただ自分の欲しいモノを求めてそれが見つからなかったから自作してみただけ。
同じような思想のモノでいろいろとちゃんと検証済みのヤツがあったらそれを採用したい。

>>643
俺はノイマン型コンピュータは、エッカートとモックリーの業績だと思ってるので。

ノイマンはどっちかつうと論理屋
プログラマではないな

>>644
いままでの乱数の何が問題で、何を今回のは解決したのか、
定義不明な言葉を使わずに説明してよ。

>>644
いや、君が作ったものは君の欲しいものになってないから。
欲しいものと、実装できたものを、一度表にでもまとめてごらん。

/dev/randomから得た種と適当な一方向ハッシュ関数でも使っとけ。

（あー俺も大学時代に教授に>>647と同じようなこと言われたっけ…
懐かしいなあ）

>>647
>>451 で説明してる以上にはそれをちゃんとそれを説明できてないってのがまず問題だよね。
ちょっと今回はもう興がだいぶ削がれちゃってるからやらないけど、
また、こっち方面でうずうずしてきたら今度はちゃんと問題定義からやり直すように致します。

>>649は>>541で既出か。

>>628
しばらく続いたことだし、>>628 は悪魔の証明がんばってねｗ

>>651

>>451って何も説明していないし、根本的に間違ってるよ。
MT以上に相関性をなくすために、
いったいどれだけのプールが必要かわかってないみたいだし。

>>653
相関性あることに気が付いていない無いの？本人か？
出力値から簡単に逆算できるぞ、あれ。

>>655
算出式書いて。

>>656
数列とアルゴリズム書いたら逆算してやる。
アルゴリズムが同じだったら、数列だけでいいぞ。

>>637>>653
>>628は相関性がある事の一点を指摘すればいいわけだから別に悪魔の証明じゃないんだよ
http://ja.wikipedia.org/wiki/%E6%82%AA%E9%AD%94%E3%81%AE%E8%A8%BC%E6%98%8E
既に気づいてるそうだし

>>657
公開されてるんだから、自分で全部用意できるだろ？

>>658
>>637は、>>630の依頼の仕方が酷いといっているだけです。

>>658
相関性がちゃんと定義されてないから無駄。

>>661
628の定義・基準では相関性があるって事なんだろ
だから628がそういう定義も込みで証明を出してくるのを待つだけ

>>658 >>662 乙

>>659
逆算プログラムとアルゴリズムは教えるつもりはない。
そうすると、少し修正しただけのものを作ってくるだろうから。

ただ、逆算できることを証明してほしいならその手伝いをしてあげてもいい。

こっちが初期値を聞かずに、出力値から当てれば、その証明になるだろ。

>>663
正解

664ｶｺｲｲ

>>664
はい、じゃ、アルゴリズムは prime spiral で
出力は↓

8A1579636B2EC55D39F006AA24CC75860E20D48
B428C34B0E38C6C538F3EE4A1239889FCDBD459
8D80B40EF3EF1F0A5DB8B581D8F85497945E5FD
1C2BDC83C6FE1FB759C5EFB0CD83BCDA8E48BC0
172226BE2615F284C7C66DC6E9D07D4DF1203D2
0D27C584C79B99C79BAB7AAEA7C6AB6782DAB5F
FD586FCA9308922BAEC087A04F732D86E49880D
CC70BBCF3BACBCD4E212FA7FE5D7DAB81EE56D5
4EC7A0522645C6912D5E33F1A80C701B481DF86
2F3C587F2D49E2D10CE7D591A5E9209F72444FB
1FD8899C3F48749640924127B735FF79525C78E
226887745DAF96F3099E776724ACE45DED7B9B6
FA841B3433A0E6EDFB130F5D6D8F0270D4B80A3
028C1040FB5D2D2AD7D8916B93D2B1457E1D13A
C3B886870D16030DD2BA2973ECFE05A7425CAE5

>>667
それで足りるのか？　まぁ、いくつ必要なのか 664 が書いてないから
分からんが。

>>664
初期値がわかるのか。次に出る値がわかるのかとおもったよ。
まぁ、次に出る値を当てることはMTでも可能か。

>>667
32ビットずつちゃんと区切れよ。検証してもらう態度じゃないぞそれは。
それからデータはお前のサイトにおけ。本人以外に協力してやる気もないから。
数列の量はMTに文句言ったのだから、６２０個用意しとけ。

ヘラクレスの栄光III

盛り上がってまいりました！

wktk

>>670
ﾜﾗﾀｗ

tktk

さて
どっちが先にくたばるかな

>>670
ところで合ってたかどうかの証明はどうやるんだ？

>>677
こっちが逆算した数列見れば本人にはわかるだろ。

>>677
その初期値で、同じ出力が得られることを確認すれば良いんじゃね？

>>677
初期値使って自分で乱数生成してみりゃ自明
どんだけ生成すればでてくるのかは知らんが..

今牟板で一番熱いスレ

それは>>667が…
あ、そうか。だから本人のサイトにアップするなりして
確証を持たせる必要があるからか。


2ｃｈトリップを利用するのはどうだ？
トリ解析器を使われると一方向性がちょっと怪しいけど

わっふるわっふる

>>681
ほんとだよｗ
もう夏休みも終ったというのに…
あ、大学生はまだしばらく休みだな。

さて、社会人の俺はもう寝る。
明日どうなっているのか楽しみだ……

>>679
それじゃ証明にならんぞ。ある一定部分が同じでもその後の出力は異なるパターンがいくつもあるし。
ん？　てか、だとしたらそうならない量のデータが必要なわけだが、620で本当に足りるんか？

まさか初期値を求めるのに何万年掛かるとかそういうのは無いよね

>>682
確かに乱数生成ルーチンにもなるよな。あんまり効率よくないが。

ダンゴさんが来るとスレが引き締まるな。

まあ全部俺の自演だけどな

数学なんてわからんっすう

自演厨乙 いか臭せーｗ

結果まだかな

>>670
あと何万年ー？

仮性人ﾊﾞﾛｽ

乾杯モンテカルロ〜♪
好きよ貴方が楽園〜〜

あーおもしれぇスレ

>>670
釣り宣言ﾏﾀﾞｰ?

>>697
釣りじゃないよ。
なんつーか、本人以外は逆算できることに気が付いている奴が多いんじゃないの？
前の方のレス読んだら、ヒントが書き込まれているし。
初期値がわかると言っても、正確には同じ結果を出す、初期値のうちの一つの解になるんだけどね。
次に出る値も当然わかるよ。

あと、６２０個も本当はいらないんだけどね。
未知数の数がいくつか考えれば、必要なデータ数が遙かに少ないことは、わかるやつにはわかると思う。

ちなみに、XOR演算であるという点以外は、中学レベルの数学で十分求まるよ。

知ったかぶり乙

解ってる奴が前の方は見ないからなｗ

元のアルゴリズム見てないけど、
そこまで簡単ということはただの連立方程式
さらに恐らく1ビットずつ独立して計算できるとかかな。

>>701
当たり

>>698
>釣りじゃないよ。

じゃぁ、素で言ってるの？　どっちにしろ、お前にはガッカリだ。

エントロピープールがほとんどゼロで初期化されちゃったとかの極端なケースを除けば
その後の出力予測云々の話以前に、そもそもその程度の数じゃ、その後の出力が
１パターンに収束しないし、１パターンに収束するには何桁も出力が足りない。
いくらなんでも prime spiral の特性を理解してなさすぎ。

線形合同法よりマシならなんでもいいや

そう思う奴はこんなところに来なくていいや

>>703
収束するよ。

嘘だと思うなら、収束しない例を一例でいいから書いてごらん。

あと何時間かかるか教えてくれ

>>703
というかさ、お前本人だろ。
本人以外に、prime spiralに興味を持ち、特性を理解して、
かつ問題も見えず、収束していないことに気が付かない奴っているの？

知能が道化師レベルの癖に、問題点も見えずに特性を理解した気になって
過大評価できる奴なんて、あり得ないだろ。

もうこの流れ秋田
そろそろ隔離スレ作るか？

>>707
指示したものをサイトにアップしたらやるよ。

>>710
お前にはいい加減うんざりだし、他の人にも迷惑だから
お前がそれで引き下がるならお前がいうデータをサイトにアップしても構わんが、
その前にお前が俺じゃないことを、証明する方法を考えてくれんか？
お前のことだから、予測ができなかったことを今度は俺の自作自演だって騒ぐんだろ？

構ってちゃんみたいだから、こいつが俺じゃないことを証明する方法を明示しない限り
俺だけでも、このスレから去ることにするわ。

>>711
ん、少なくとも俺は迷惑じゃないぞ。
wktkして二人のやり取りを見てる。

>>711
> 他の人にも迷惑だから
迷惑な人の数 <<<<<<< ﾆﾔﾆﾔしながら展開を見守ってる人の数

prime spiral自体よりも、ｻｸｰｼｬのﾌｧﾋﾞｮりっぷりのほうが予測不可能だなｗ

>>711
どうせ他に話題が無くて過疎ってたのだからお気になさらずに＾＾

>>711
＞お前にはいい加減うんざりだし、他の人にも迷惑だから

根拠もなく勘違いでMTを批判したり、その一方で危険なライブラリを
配布しようとしている方が遙かに世の中に対して迷惑であろう。

＞その前にお前が俺じゃないことを、証明する方法を考えてくれんか？

なんでそんなものが必要なんだ？
別に俺の存在とは関係なくやればいいだろう。
お前が自分のサイトで、prime spiral が安全か検証してくれる人を募集する形で、
出力例をアップすればいいだろ。

そもそも乱数のアルゴリズムを発表するときは、
ライブラリを使用する人のためにチェック用に正規の出力例をつけるものだ。

それにプラスして、エントロピープールを秘密にしてある出力例を追加して、
乱数の予測や逆算の評価をお願いするというだけでいいだろう。

そうすれば、俺はお前に協力してやると言っているのだ。
口は悪いし、本気で馬鹿にしているが、いいか、これはお前のための善意だ。
下手をするとお前の一生の恥になり、信用を失う。

うるしあバールのようなもので叩くぞ

ソースを読んだところで理論的な説明をひとつ。

>>451のは結局のところGFSR(Generalized Feedback Shift Register)そのもの。
これはM系列の一種でつまるところ普通の線形漸化式。
indexというカウンタがindex_maskという変数でxorされてるので
具体的には分かりかねるが大きな多項式になっとる。
index_mask == list_a[ 0 ]のようなのでここを変えると多項式が変わる。
で、本人は勘違いしているようなのだけど、
適当に多項式を作っても原始多項式でないと周期は保証されないし、
場合によっては出現する組み合わせもかなり少なくなる可能性アリ。
つまり素数を全部掛けたものがそのまま周期になるわけじゃないので注意。
X^31 + X^29 + X^11 + 1とか適当に作っても実際に判定してみないとダメ。
上の方に書いてあったけど選んでxorしたものも最終的には漸化式の形になるよ。
ただ>>451のちょっと面白いところはランダムに多項式を作ってるってところかな。
でも動的に作ってるから何が出来るか分からんのが問題だが。
たまたま長周期になるかもしれんし全然ダメなのも出来るかもしれん。
多項式をどうするかは重要な問題だからな。

結局>>451のはGFSRというシンプルなものを難しく複雑に作っただけ。
index_mask==list_a[0]以外の配列を0と1で初期化すれば普通にW=1bitの線形漸化式になるよ。
MTはTGFSR(Twisted GFSR)といってこのWが32bitになってさらに
縦と横のベクトルが組み合わさって長周期を実現しててえらいこっちゃ。
さらに調律が加わって(これはいらない気もするが)分布も良くなってる。
>>451のは32bitの配列を使ってるけど結局GFSRのままなんで
縦と横が独立してるから周期も分布もいまいち。

勉強しましょう。

>>718
MTの調律は、分布じゃなくて
ビット毎の相関を減らすためのくふうで、
そこまでｲﾗﾈって場合は調律しなくてもいい。
（高速化するにも邪魔だし）

>>718
> 多項式をどうするかは重要な問題だからな。
もっともな意見なんだが、作者は >595 とか本気で返事してくるからなぁ

nynywktk

>>718
貴方の言うことはもっともだけど、彼の場合は多項式以前の問題。
その説明だって理解できているのか正直怪しい。

>>703
＞そもそもその程度の数じゃ、その後の出力が
＞１パターンに収束しないし、１パターンに収束するには何桁も出力が足りない。

理解できたなら、こういう間違った発言に気がつくと思うけど…

＞いくらなんでも prime spiral の特性を理解してなさすぎ。

作者が一番特性を理解していないんだから困ったもんだ。

で、初期値は？

>>723
>>710

というか、お前も、prime spiral の特性を理解していないのな。それとも本人？

尻馬に乗ってるだけで実際は何も言えて無いところがポイントだな。

それでも作者よりまともそうに見えるのがなんとも言えない。

ﾜﾛｽｗ

てかてか

>>724
ついに誰かれ構わず本人認定しだしたな。
末期症状。

ちなみに俺はもちろん作者なんかではない、ただの野次馬。

>>729
別に認定はしてないよ。
自分がするべきことをしないでそういうことを言いそうなやつだから、疑いがあったから聞いただけ。
気を悪くしたのならスマン。

それから、prime spiral の特性を理解していれば、
出力値から、同じ乱数列を出す初期値のうちの一つの解を求めることができるのはわかる。

とりあえず一つの判定基準を。

sageてない奴は同一人物。

＞作者
聞くは一時の恥、聞かぬは一生の恥。

そうだよな。ほんと。

>>731
あーあ。

C++関係から来た外部の者だけど、ここ数日間楽しかったよ！

否、まだ終わっていない

でも作者はもうダンマリする事にしてそうな気がするよ

>>737
ML アーカイブは残り続けるけどな。Webも魚拓とっとく？

作者が黙っているなら、MLの方でやってやろうかな。

もういいじゃん。
どこまで追い込むつもりだよ。

だね

>>740
危険なライブラリを気がつかずに配布していることは作者も望まないだろ。
間違いを証明するのは、作者も望んでいるはず。


468 名前：デフォルトの名無しさん 投稿日：2007/08/28(火) 21:03:55
この手のものはいろんな批判に耐えることができてなんぼって面もあるんで
いろんな批判もウェルカムですけど、この乱数アルゴリズムは本当に優れた
ばらつきの乱数列を出力できるんで、是非とも皆様、他とは異なるこの上品質
の乱数列を一度ご賞味くだされ。


499 名前：デフォルトの名無しさん 投稿日：2007/08/30(木) 22:37:32
prime spiral にあるのは「上質な乱数列」、ただそれだけです。


630 名前：デフォルトの名無しさん 投稿日：2007/09/04(火) 23:40:25
>>628
>prime spiralが相関性ありまくりで最悪であることを証明して投稿してやるよ。

ごめん、これはぜひ、お願い。
検証にご協力頂けるのは助かります。

その頃は大したダメ出しはされないだろうという自信があったんでないの

証明無しにここまで粘着されるとは思ってなかったんだろう。

>>742
危険ってここではどういう意味？
暗号用途に使えないのはMTも一緒だと思ったので。

作者は暗号用途にも使えるつもりでいる。
MTより「良い」乱数だと宣伝しているけど、実際は周期などの点で低品質。

信じて使うとろくなことにならないってことでしょ。

あれか、
十分に引き付けてから撃つ。

>>740
ここの内容が訂正されるまでじゃない？
ttp://www.trickpalace.net/column/random.htm

> この prime spiral のように問題を引き起こしかねない相関性を全て排除した擬似乱数アルゴリズムを無相関性擬似乱数アルゴリズム
> 「MTも所詮、線形合同法と五十歩百歩」

>>744
ほとんど証明に近い指摘はたくさんあるし、解き方のヒントも提示してきた。
これでわからないレベルなら、初期値の例を示して証明するしかないだろ。
そのためには、作者の協力も必要。だって作者にわからせるんだから。

>>745
作者自体が理解していないアルゴリズムで、品質に根拠がないばかりか、
まともな検証すらされていなく、問題点に気がつかず「良い」と宣伝され、
使った人間が騙されて被害を被るプログラムだから。

俺は作者のやっていることはテロに等しいと思っている。

本当に世のために公開しようとしているのなら、
無責任な宣伝をする前に、やるべきことがたくさんあるはず。

いや、でも、こんなの信じて使うバカが本当にいるのか？
本当によい疑似乱数が必要なら自分でチェックするもんだろ。

>>749-750
つ スルー力

スルーしたい奴はさっさと去ね

>749
作者に間違いを認めさせることと、
間違っていることを世間に証明することのどちらがゴールなのか判然と
しないな。落ち着け。

>>752
俺は元ネタのあれについては一貫してスルーしてるよ。
「君もスルーしてくれると良いな」と思ってるんだよ。

俺は今のところスルーしないほうが面白いと思ってるから。すまんね。

>>754
君、腐れ女子以下ｗ

このスレ立てた>>1ですが、
なんだか随分と盛り上がっているようで。
しかし、もっとましな方向で盛り上がってくれと思う。
MTFSとか、もっと美味しそうな話題がいくらでもあると思うんだがよ？

違った。FSMTか。
まあいいや

>>753
両方

>>757
気持はわかるが、MTに問題があるからもっといいものをといって出されたものが糞だったんだが。
で、その糞をサイトやMLでばら撒いている馬鹿がいるわけだが。

>760

そこまで口汚く罵れる精神構造がよくわからん。
別に作者に使うことを強要されているわけでもないし、
スルーしておけばよいだけのこと。
新しいものを出そうとする人間をたたいてばかりいると、
そのうち国が滅びるよ。
（あなたがMTの作者ならともかく）

技術的議論なら歓迎なんだがナー

>>761
＞新しいものを出そうとする人間をたたいてばかりいると、

そういう方向性なら歓迎するところだが、
MTに対する勘違いした間違った批判を行い、【同時に】、劣悪なものをそれよりも優れていると
主張する態度に問題を感じている。
彼はそこそこ手広い活動をしているのだから、わかっていない他人を間違った方向に進ませてしまう恐れもある。

それに、本当に新しく、良いものを作り出す人間は、彼のように思いあがってはいないよ。
ほとんどの優秀な人は、彼と全く正反対で、非常に謙虚で、慎重で、真摯だ。

俺は今回のことで彼が深く反省し、学問や技術に対する態度を改めることを祈っているよ。

>>761
> 新しいものを出そうとする人間
w

>> 「MTも所詮、線形合同法と五十歩百歩」

？

>>765
作者の批判の方が酷いってことだろ。
線形合同法と五十歩百歩なのは、prime spiralの方であり、MTはレベルが全く違う。

>>762
技術的な議論から逃げているのだから仕方ない

>>767
ここでつついても技術的な議論にならないのなら
ここでつつく意味もない

？

prime spiralを軽く眺めてみたが
%を除去すればゲームに使うのにはよさそうだ

>>770
xorshift で良いじゃん。

xorshiftのseedって自分で変更するとやばいよねえ
どうすればいいの

別にやばくない。
全部0じゃなきゃいいんだ。
適当に線形合同法でも使え。

レスありがとう
そうなんだ
1と0の数が同じほうがいいとかあるのかな

それはある。
出来るだけ均等な方が望ましい。
でも自分が調べた限り偏ってても大した問題は出てない。

>>770
mtでいいじゃん

ゲームなら高速で多次元分布が良くて再現可能なのがいいな
xorshiftで十分？

ゲームによる。
トランプ、麻雀なんかは階乗のオーダーなので
それなりにでかい周期がいる。
あと分布もよくないと。
mtなんかうってつけだな。
アクションとかは応答性が求められるからxorshiftみたいなのが良い。
レジスタに全部おさまるくらい小さくて速いやつ。

>>778
乱数の使用頻度はゲームのジャンルより、実はエフェクト出す数に
よらんか？　特にパーティクルを適当に飛び散らす系。

>>770
ダメだって。分布も周期も最悪に近い。
無駄に遅い分一般的な線形合同法よりも酷い。

>>767
中の人、結局、これを多少なりともマトモな体裁で書き直す気無いのかねぇ。
ttp://www.trickpalace.net/column/random.htm

まっとうに議論するためには、言葉の定義と評価基準を示して、これこれこういう点で
優れてると証明つきで出すのが最低ラインなんだが。

土俵にあがるつもりが無いんでしょ

土俵にあがったら負けかなと思ってる

>>783
作者は多分そう思ってる。
しかし、作者を批判してる人の方が、
作者が土俵に上がるまで手の内は見せないというか
わざと隙があるように振舞ってて
かなりえげつない。

>>783
思ってる時点ですでに負けじゃんｗ

「新しい」擬似乱数の質については学会にでも論文出してくればいいと思いますです。
ここの連中は評価しようがないから。


牟板発祥のソフトって何があったっけ？
DGCAくらいしか知らん。

査読に耐えられる質の論文を書けない疑惑

ダンゴさんの開発したソフトがあるじゃないか

設計当時はVIPに居座ってた。

>>784
確かにそうだな。
見る人間が見れば、詰んでいることはわかる筈だし。

>>784
同意。さっさと証明出してほしい。

>>791
でもその前に作者がやることをやらないとね。

>>792
作者の介在なし証明は書けるだろ。それだけで十分社会の役に立つから
よろ。

知ってるが
　　作者の態度が
　　　　気に食わない

場当たり的な対処で穴を隠されるのが気に入らないとかそういう理由だろうけど
少しでもよくなる可能性があるなら情報を出した方が良いんじゃないか

>>795
そんなことをしてもMTには勝てないから全くの無駄。
本人にとっては修行になるだろうが、第三者的には練習ライブラリなどいらないので。
利用者のことをまともに考えていない作者はプログラマ失格だと思う。

言い訳入りました

>>793
証明に対して、相関性の言葉の定義が違う、とか悪あがきをしだすに 3 ガノッサ。

結局やりたくないのでしょ?
できないとは思わんけど、もう作者もいないだろうし黙ったら。

俺はこの調子で続こうが構わんけどね
ってかやめさせたければ何か他のネタ提供すれば
ただ過疎らせたいのなら別だけど

今の流れはもうスレの趣旨から反してきてるでしょ。
これで続けるなら落としたほうがまだ良いよ。

っていうか、沈静化したいのは作者だけだろ。
どうどうとサイトで酷いプログラム公開していて、黙れというのは筋が通らない。

ここで続けるのが反対なら、俺が別のスレ立てる。だが、その前に、作者には選択肢をやろう。

・prime spiralの説明で使われている言葉の定義と評価基準を明確に示してサイトを修正する。
・検証のためのデータを提供する。
・MTに対する中傷を取り下げ、サイトとMLに謝罪文を載せ、prime spiralは間違いとして公開やめる。

以上のどれかが実行されないなら、今まで同様、ここで話題の一つとするか、
「問題のあるプログラムを載せているサイトとその議論」というようなスレを立てて、
第一弾といてprime spiralを紹介する。

選択の期限は９月１５日とする。

いくら作者が非協力的だからって何も落とさなくても。

これのどこが悪いのか、頭の悪いおいらにもわかるように書いてくれんかの…。
作者が動いたらやる、で止まってバッシングだけになってるのも別にいいけど、口だけにも見えちゃうお。

>>804
作者か？

さっさと>>802に応じろよ。

う、やっぱりそう思われちゃうかｗ
違うって言っても信憑性無いのでROMるね。

でももうスレ違いだしID出る板でやらない?
作者のブログにTB送っとけば伝わるでしょ。

>作者か？
ﾜﾛｽw

>>806
８０２だが、俺は（君が作者だとは）思ってないよ。

＞でももうスレ違いだしID出る板でやらない?

これは俺も賛成。でもいきなり行動に移す前に、まず作者の出方を待ち、
その間にやり方を検討したりしようと思っている。

prime spiralのダメ出しサイトでも作れば

おつ

誰が誰だかわかりませんが、もしかして意外と人いる?

>>808
そうですね、乱数スレなんでこのアルゴリズムに対する駄目だしができれば、別にここでもいいとは思うんですけど。

作者が何もしなくてもこれが駄目だって言う根拠を人の目に着くとこに置いとければ>>763で危惧してることも起きないだろうし。
まあ間違いがあるなら本人に認めてもらうってのも大事だとは思うんだけど、でも本人ここもう見てない可能性もあるので、
何かしらの手段で存在伝えた方がいいような。

>>809
よろ

論文が出てなかったり、世間でのまともな評判がない時点で、
prime spiralを使う人はほとんどいないだろう。
（使おうと思う人がいるなら、その程度も気にしないのレベルということ）

とりあえず>>802も含めてｳｻﾞｲのでとっとと別スレにでもいってほしいね

>>812
了解。一応、他の人の意見も聞いて、ここで技術的な議論ができないようなら、別スレ立てて誘導することにする。

>>801
趣旨なんてあったっけ。

専用スレに隔離は同意

どうでもいいけどprime spiralって名前、
mersenee twisterを意識しすぎてﾜﾀﾗ。

スレが伸びてるからもう他の話題で盛り上がってんのかと思ったらなにこの流れ？ (´Д｀；)

よくもまぁブラフでここまで引っ張るもんだ。
僅かな出力でその後の出力が予測可能ってのがブフラだってことを証明するコードやるからいい加減大人しくなれ。

#include <stdio.h>

#include "trickrng.h"

using namespace tricklib;

void tune_dice(uint32_t sync_length, dynamic_prime_spiral_dice *a, dynamic_prime_spiral_dice *b)
{
    //  *a の初期化状態が極端に酷い場合には同じ値が sync_length を大幅に上回る回数出力されます。
    //  *a の初期化状態が極端に酷くない場合でも、1/2^32の確率で同じ値が sync_length を上回る回数出力されます。

    assert(0 < sync_length);
    assert(sync_length < 0x80000000);

    //  sync_mask の算出。
    uint32_t sync_mask = 1;
    while(sync_mask < sync_length)
    {
        sync_mask <<= 1;
    }

    //  sync_length を精確に反映させる為に index を調整。
    *(((uint32_t*)(a +1)) -1) = sync_mask -sync_length;
    //  ↑この行は a->index = sync_mask -sync_length; の意。private なので本来はアクセスしちゃいけない所。

    //  *a を sync_mask で XOR したものを *b とする。
    for(int i = 0; i < sizeof(*a)/ sizeof(uint32_t); ++i)
    {
        ((uint32_t*)b)[i] = ((uint32_t*)a)[i] ^sync_mask;
    }
}

int main(int argc, char *args[])
{
    if (2 <= argc)
    {
        dynamic_prime_spiral_dice dice_a, dice_b;
        tune_dice(atoi(args[1]), &dice_a, &dice_b);
        uint32_t i = 0, a, b;
        do
        {
            a = dice_a.roll();
            b = dice_b.roll();
            printf("\r0x%08.8X:0x%08.8X:%010d\n", a, b, i++);
        }
        while(a == b);
    }

    return EXIT_SUCCESS;
}

「証明」の意味も分かってなかったのか・・・
(´A｀）

で、prime spiral の出力品質で盛り上がってくれてるとこ、悪いんだけど、

・乱数列にランダムアクセスが可能。
・出力の難収束性。
・tune_dice()みたいな処理が可能。

当初は"乱数列の品質"だと思ってたけど、これだけ売りがあれば出力品質が
悪いなんてことが多少証明されたところで、prime spiral はもうすでにひとつの
擬似乱数アルゴリズムとしてありだと思うですよ。(もちろん、それでは無相関性
擬似乱数アルゴリズムとは言えないんですけど。)
出力品質がよいということが証明されればさらに素晴らしいことなんでまた今度
dieharder でのテストぐらいはやっとこうと思うです。

じゃぁね。

>>820
×当初は"乱数列の品質"だと思ってたけど、
○当初は"乱数列の品質"だけだと思ってたけど、

続きは別スレ立ててやれよ。

そして過疎スレへ……

保守頼んだ。

>>816
＞よくもまぁブラフでここまで引っ張るもんだ。
＞僅かな出力でその後の出力が予測可能ってのがブフラだってことを証明するコードやるからいい加減大人しくなれ。

どう証明になっているか説明してくれんか。

もし僅かな出力でその後の出力の予測が不可能なら、
例えば、最初の６００個が一致して、６０１個目が一致しない例を示せばいい。

しかし、現実にはそういう例は出せない。これは予測可能であることのヒントだ。

>>820
「思うです」とか変な書いている馬鹿は本人か。

>>825
「思うです」とか変な日本語を書いている馬鹿は本人か。

>>824
そこのコードをコンパイルしてコマンドライン引数に600を指定してみｗ

>>820
> 乱数列にランダムアクセスが可能。
（擬似）乱数列にランダムアクセスできることの意義を見出せないんだが……。

>>820
> 無相関性擬似乱数アルゴリズム
超古典だが、LFSR で特性多項式が原始多項式（因数分解不可）の場合が
無相関と証明されてなかったっけ？

>>829
それは入力に対して出力に相関性があらわれないことだから、意味が違うんじゃね？

>>828
膨大なデータを扱うシミュレーションなんかで
乱数を元に作成した一時的にいらないデータを破棄して
後で必要になったときには再計算することができるとかそんな利点があると思うけど。

>>827
何かおかしいと思ったら、indexを後からいじってるじゃん。

>>831
初期ベクトル持っていれば再計算できる。

>>830
乱数が無相関という場合に、それ以外の意味があるの？　独立性を議論してる
わけじゃないよね。

>>832
それがなにか問題なのか？

>>833
可能か不可能かで言えばそうだけど、必要な計算量に雲泥の差がでるぞｗ

>>833
初期ベクトルではなく状態ベクトルじゃね？

>>836
再現ポイントの初期ベクトルなら同じだろ。

>>838
初期ベクトルではなく状態ベクトルじゃね？

>>835
index_maskとindexの組み合わせを同時に変えていいなら、そりゃ簡単に一部が一致する系列を作れる。index_mask^indexが同じ範囲は同じになるからな。

実際のところindex_maskは、各ビット位置が表す周期で系列を入れ替えているだけ。
だから、エントロピープールとindex_maskの組み合わせと、indexと出力系列の組み合わせは一対一に対応する。

だからindexと最低限の出力系列(各素数の和)が得られれば、逆算ができるわけだ。
ただ、indexがどこから始まっているからわからないなら、最小の出力系列で、その後が完全にわかるわけではない。
ただ、ランダムアクセス可ということでindexが0から始まるものなら最低限の出力系列から、すべてがわかる。
また、indexの開始が不明でも、その後に出てくる数列は入れ替わっているだけで同じものが同じ分布で出現する。

例えば、コマンドライン引数に2を指定して出力するとこうなる。●は同じところ、△はずれているだけのところ

0x331EE257:0x331EE257:0000000000 ●
0xAC31D68A:0xAC31D68A:0000000001 ●
0xCA4DAAEF:0x0A4D250D:0000000002 △
0x2CEE50F2:0xDD950B6E:0000000003 △
0x91448FED:0x91448FED:0000000004 ●
0x11C949BE:0x11C949BE:0000000005 ●
0x0A4D250D:0x563953EE:0000000006 △
0xDD950B6E:0x9C9C9179:0000000007 △
0x36D2A9DB:0x36D2A9DB:0000000008 ●
0x8B051CF8:0x8B051CF8:0000000009 ●
0x563953EE:0x9D3900E1:0000000010 △
0x9C9C9179:0x206E7721:0000000011 △
0xDC87B479:0xDC87B479:0000000012 ●
0x20D18FD0:0x20D18FD0:0000000013 ●
0x9D3900E1:0x7B1CC024:0000000014 △
0x206E7721:0x3F4B54FE:0000000015 △
0x1B94729E:0x1B94729E:0000000016 ●

>>839
MTの場合、初期ベクトルと状態ベクトルの違いなんてないだろ。

>>841
ないから、敢えて初期ベクトルとは呼ばずに状態ベクトルと呼ぶでしょ。
リファレンス実装でも state vector となってるし。

いずれにせよ、それ保存しとけば全然問題ないって主張には同意。

すまん、MTの乱数状態をバイナリデータに保存できるサンプルってある？

>>840
つまりindex_maskは何の役にも立っていないな。

MT の調律の逆変換。これで、出力から状態ベクトルを計算できる。
/* Tempering */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);

/* 逆変換 */
y ^= y >> 18;
y ^= y << 15 & 0xefc60000UL & (1L << 15*2) - 1;
y ^= y << 15 & 0xefc60000UL & - (1L << 15*2);
y ^= y << 7 & 0x9d2c5680UL & (1L << 7*2) - 1;
y ^= y << 7 & 0x9d2c5680UL & - (1L << 7*2) & (1L << 7*3) - 1;
y ^= y << 7 & 0x9d2c5680UL & - (1L << 7*3) & (1L << 7*4) - 1;
y ^= y << 7 & 0x9d2c5680UL & - (1L << 7*4);
y ^= y >> 11 & - (1L << (32 - 11*2));
y ^= y >> 11 & (1L << (32 - 11*2)) - 1;

セキュリティ関連には向かないわな。てか本当にセキュアな乱数使いたいならハードウェアノイズでいいと思う。

>>840
なに言ってんだ、おまえ？

>例えば、最初の６００個が一致して、６０１個目が一致しない例を示せばいい。

こんなことを言ってたのはお前自身だぞ、アホかｗ

お、昨夜は作者が発言したのか。
>>816-818を見てちょっと安心したんだろうな。

>>840
>だからindexと最低限の出力系列(各素数の和)が得られれば、逆算ができるわけだ。

>>816-818 のコードで1000000とか指定して1000001個目を予測してみてｗ
逆算できるんだろ？1000000もあれば十分すぎるだろ？

>>840
>index_maskとindexの組み合わせを同時に変えていいなら、そりゃ簡単に一部が一致する系列を作れる。index_mask^indexが同じ範囲は同じになるからな。

だからになにがいけないんだ？
どのみちそれは prime spiral の初期状態として存在するパターンだろ？

最悪板でお願いします

数学板にでも移転すれば？
あっちの乱数スレは落ちてるみたいだが

>>850
> どのみちそれは prime spiral の初期状態として存在するパターンだろ？
agree

ただ暗号の評価基準として「ある程度の長さの出力を見たときに、その内部状態が
ユニークに特定できる」というのは、かなり珍しい気がする。完全に特定できなくとも
範囲を絞り込めるなら、それで十分に辛い。

あとほかの品質基準として分布の良し悪しとかもあるんだが、その辺は統計的に
どうなんだろうな。独立性検定とかやってみた？

いつから暗号の話になったんだｗ

門外漢は黙ってろ

>>847
最初というのはindexで0からという意味だった。
書き方が足りないのは悪かった。

>>849
indexが0から始まるとう前提でOK？

>>850
最低限の出力系列で、全パターンに出現する値がわかってしまうから。
indexが不明なら、順番まではわからないかもしれないが、何が２回以上出て、
何が全く出ないかは、簡単にわかってしまう。indexが確定すれば、全部が分かる。
どういうことかというと、相関性が非常に高いってことだ。

>>858
実際のところ、出ない値が確定した時点で、乱数とはもはや呼べない。

MTが駄目って話が全くでなくなったけど、撤回するの?

>>858
理由になってないし、順番がシャッフルされている状態で本当に特定できるのか？

当たり前

>>861
indexとindex_maskが、系列の入れ替えだけで、分布を変えているわけではないことはわかるよな？

次に考えることは、index_mask=0で、indexが0から始まる場合。
この系列が、indexとindex_maskのあらゆる組み合わせの入れ替えと同じということから
分布だけに関しては、index_maskがないアルゴリズムに置き換えることができる。

あとは未知数（素数の和）の数の出力から連立方程式を解けばわかる。

値の分布を特定できない疑似乱数なんてあるの？

>>864
多くのものは、特定するまでに必要な情報量の差があり、
また、アルゴリズムの種類によっては、特定できないものもある。ググればわかると思うが。

似非乱数スレでも立てるか？

なんかもうグダグダだな。

>>866
ﾜﾗﾀ

擬似擬似乱数スレとか。

>>856-857
それって種の一部が分かればってことだろ？
出力だけから分かるってのと種の一部も必要ってのじゃ次元の違う話だ。
いくらなんでも見苦しすぎｗ

頼むからどっかヨソでタイマンしててくれ。

>>870
インデックスの初期値にシードを使っていたのは盲点だった。
そこは俺が悪いから謝る。俺は作者と違い、自分の間違いは認めるからな。

でも、目的は俺の評価ではなくprime spiralの評価であることを忘れてもらったら困る。

で、今回、

最低限の出力系列で、全パターンに出現する値がわかってしまうこと。
出ない値が確定した時点で、乱数とはもはや呼べない。

という問題点が明らかになったと思うが、そのことについてはどう思うの？

また、

MTが駄目って話が全くでなくなったけど、撤回するの?

とも言われているが、こういう都合の悪い点は見ないのか？

他所でやれマジで。

出力以前に周期が短すぎて話にならん。
素数で割ってるから周期を伸ばすのにとんでもなく苦労するぞ。
次元分布がどうこう言ってたがn次元で均等分布するためには
最低でもnビットの状態空間が必要だからな。

>>872
>>870が作者かどうかに疑問を感じるのだが

>>874
どっちでもいいだろ？
もうこんなぐだぐだな話、どっか他所でやれば？

>>875
別に他に話すネタがあるわけじゃないし、ぐだぐだでも誰も困らんだろ。作者以外はｗ
他にまともな議論があって、それが阻害されているのでないなら、続けて問題なし。

>>875
見たくないなら見なくてもいいんだよ？

でもやっぱりIDぐらいは出てほしいと思う俺

技術的な議論が続くなら歓迎なんだけどね

問題点が明らかになったら、急に静かになったな。ｗ

前回、騒ぐだけ騒いで大恥かいたから自重してんだろｗ

そもそもお前ら、32次元のことを 2^32 次元とtypoでもなく本気で
記述するようなｼﾄとよく対話する気になるな・・・
ネットウォッチ板のネタじゃないのかこれは。

ちょっとネタ投下してみる。
マジメな乱数アルゴリズム。
周期2^521-1で16次元に均等分布します。

class MLS521
{
private:
unsigned long st[ 16 ], x, y, p;
public:
MLS521( unsigned long seed ) {
x = 0x41C64E6D * seed + 0x3039, p = 0, y = 0;
for (unsigned long i=0, s=x, t=~x, u; i<16; i++) {
u = t, t = s, s = ( u << 1 ) ^ ( t >> 31 );
st[ i ] = s ^= ( u << 6 ) ^ ( t >> 26 );
}
for (unsigned long i=1; i<16; i++) {
y ^= st[ i ];
y = ( y << 2 ) ^ ( y >> 30 );
y ^= y >> 12;
}
y ^= x;
}
unsigned long next( void ) {
unsigned long r = y, s = r ^ ( r >> 21 );
unsigned long u = st[ p ], v = st[ ( p + 1 ) & 15 ];
st[ p ] = x, ++p &= 15;
x ^= ( u << 23 ) ^ ( v >> 9 );
r = ( r << 2 ) ^ ( r >> 30 );
y = r ^ ( r >> 12 ) ^ x ^ v;
return s ^ ( s << 6 ) ^ ( s << 13 );
}
};

>>881
その割には、MTがダメというのを取り下げていないし、サイトもそのままだし、
prime spiralの問題点も認めようとしないね。

取り下げたら負けかなと思ってる

美しい擬似乱数

>>883
x と y も状態空間なのかな？
どっちか片方だけ状態空間で十分のような気がするが。

ソースだけざっと見ても周期はわかんないけど、
2ベキ長の配列に変数を合わせてメルセンヌ指数ビットの状態空間を
実現しつつインデックスの更新を高速にしているのはわかった。
そこに工夫がある。

少なくともprimeなんちゃらよりはずっといい。

>>883
XorShiftに似てるね。
というか>>18の変数が4個なのを16個に拡大したような感じなのかな。

こういうのって周期は変数を減らして増やしていけば予想できそうなんだけど
均等分布、というのはどうやって分かるの？

というか作者もうここ見てないんじゃないのかな
なんかこのスレってバカが多いみたいだし

そうだね。そういうことにしとけばいいんじゃないかな。

はいはい

>>889
見ていると思うよ。作者ほどのバカもいなかったと思うけど。

うむ

オリジナルのMTの実装(mt19937ar.c)の初期化についてちょっと質問させてください。

mt19937ar.cは初期状態を線形合同法(の変形?)で与えていて、
>>38なんかにあるように「初期化が悪い」と言われていますが、
実際のところどうなんでしょう。根拠のある情報を見つけられないでいます。

SFMTやWELLの論文は、MT19937の0超過状態からの回復が遅いことを指摘してます
(実装ではなくMT19937のアルゴリズム・パラメータに対する指摘)。
が、mt19937ar.cでの初期状態は0超過ではないようで、
これらの論文はmt19937ar.cの初期化が悪いことを示してはいないようです。

0-1の出現確率については問題がないけど、別のどこかの分布が悪く、
それが解消されるまで結構時間がかかるとか、そういう話なんでしょうか。
当方計算機屋なんで数学はサパーリでして...

>>894
mt19937ar.cは初期化問題に対応したバージョンだから問題ないそうだ。
その前のコードは見たことないから分からんが。

>SFMTやWELLの論文は、MT19937の0超過状態からの回復が遅いことを指摘してます
こりゃ全くその通り。
三項式だし、マトリックスの掛け方の都合でそうなる。
でも現実的には超長周期だから意図的な初期ベクトルを与えない限りは
0超過の状態は出ない。

mt19937ar.cに関しては普通に使う限りは問題は全くないよ。

>その前のコードは見たことないから分からんが。
これが笑える（笑えない）ことに、
「アセンブラでMT高速化しますた！」
みたいな第三者のライブラリでたまに古い初期化コードが残ってたりするんだわ。
最適化MTライブラリを使うなら、おとなしくSFMT使え。

>>895-896
ありがとうございます。
現在のバージョンには問題がないということですね。参考になりました。

>>802
作者から反応がないようなので、そろそろMLへの突入と、スレ立てを実行する。

予告キター！！！！！！！！！！！！！！！！

ｗｋｔｋ

>>898
MLは入りたくないから内容ここで晒して欲しい

cppll ならウェブで見れる

>>900
心配するなｗ両方で晒すからｗ

なんというWeb1.0

祭りが始まるのか?

残り100レス切った現状じゃすぐ吹っ飛ぶな
今のうちさっさと祭り専用スレたててくれ>>898

作者が無視しつづけりゃ祭りにもならん
反応してくれることに期待

結局どっちも口だけか

疑似乱闘？

？

ちょっとした小ネタ。
一様乱数から正しくNの剰余を求める場合は
RAND_MAXからのNの剰余以下の数字は棄却しましょう。

unsigned int rand0toNminus1( unsigned int n )
{
unsigned int m, r;
if ( n == 0 ) return 0;
m = RAND_MAX % n;
do {
r = rand();
} while ( r <= m ) ;
return r % n;
}

それ改善できるよ

本当？
どうすればいいの？

>>910
n=3のときを考えればどこを修正すればいいかわかるな

unsigned int rand0toNminus1( unsigned int n )
{
　　unsigned int m, r;
　　if ( n == 0 ) return 0;
　　m = RAND_MAX - RAND_MAX % n;
　　do
　　{
　　　　r = rand();
　　} while ( r <= m ) ;
　　return r % n;
}

>>913
え？
RAND_MAXから剰余を引いても結果は同じだと思いますが。

今、仮にRAND_MAXが255でNが10だとした時に、
0-255が均等に1回ずつ出現したとした場合、
m=0-5が26回、m=6-9が25回出てしまうので
r=0-5の場合はやり直しにしようという考えなのですが…
こうするとm=0-9が均等に25回ずつ出ますよね？

ああそうかRAND_MAXが2^n-1とは限らないのか。
ちょっと考え直してみます。

>>914
m = RAND_MAX % n;//nが小さいとき、ここでmの値が小さくなるのでまずい(計算量がO(RAND_MAX / n))
m = RAND_MAX - RAND_MAX % n//こちらだとnが小さくても、大きくても大丈夫(計算量は定数オーダー)

>>913
ちょｗループ回数多すぎｗ

>>917
本当だ。不等号勘違いしてたやw
913は無視してくれ

unsigned int rand0toNminus1( unsigned int n )
{
unsigned int m, r;
if ( n == 0 ) return 0;
m = ( RAND_MAX % n ) * n;
do {
r = rand();
} while ( r >= m ) ;
return r % n;
}

これでいいですか？
これなら間違いないですよね。
なんか眠くて頭が回らなくなってきました。