疑似乱数２

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん
垢版 |
2007/10/17(水) 22:34:59
擬似乱数発生器について語ろうか。その２

前スレ
擬似乱数
http://pc11.2ch.net/test/read.cgi/tech/1146071975/

関連スレ
【危険】とんでもプログラム告発スレッド【悪質】
http://pc11.2ch.net/test/read.cgi/tech/1191860116/


SIMD-oriented Fast Mersenne Twister (SFMT):
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
2010/01/11(月) 09:28:59
>>242
それは正しい処理だが、スレタイを翌嫁。
2010/01/11(月) 16:31:10
>>242,243
それだとテクスチャが沢山必要になるからi/oで引っかかって
擬似乱数より遅くなるよ
2010/01/11(月) 20:19:14
二次写像などのカオスの数値の下ビットを使うというのはどうだろう

でも実際に相関がないことを証明する必要があると面倒ですね。
plot(rand mod 640,rand mod 400,rand mod 16)
とかでとびとび直線が出てびっくりですよ
2010/01/11(月) 20:48:42
>>245
数理的な意味でのカオスってのは、テント写像に代表されるように
小数点以下を無限に汲みだす漸化式になっているから予測が難しいのであって、
種が有限桁数であっては成立しない。

むしろ、いかなる相関性のある入力に対しても、
周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。
2010/01/11(月) 20:48:48
こんなことを言い出すやつがいるとは…
それは線形合(ry
このスレは分かってる人とそうでない人のレベル差が妙に大きいな
2010/01/11(月) 20:57:18
>むしろ、いかなる相関性のある入力に対しても、
>周期は短くていいから高速に前ビットかき回して相関のない出力を出す関数があればいい気がする。
いいわけない、というかそれはただのハッシュ
等確率性・分布・周期を保証できないし
入力がずっと同じだったらどうにもならん
2010/01/11(月) 21:02:21
>>248
アンカが抜けてた

>228の
＞ 落としどころとしてはMTとか周期の長い乱数を使って
＞ 一定フレーム毎に各画素の状態を更新してしまえばいいと思うよ。
に対して、それなら各画素で回す周期は短くていいんじゃないかなと。
等確率性と分布は証明or検証する必要性があるとして。
2010/01/11(月) 21:36:24
>>246
頭悪そうな意見だな。周期が短い時点で相関性アリまくりだろうが。
↓こういう馬鹿(道化師)がいたことを思い出す。
【危険】とんでもプログラム告発スレッド【悪質】
http://pc11.2ch.net/test/read.cgi/tech/1191860116/
1 名前：デフォルトの名無しさん[] 投稿日：2007/10/09(火) 01:15:16
劣悪なプログラムやアルゴリズムを、恰も優れたものだと言い張り、
他人を騙しているサイトを告発、検証、監視することを目的としたスレッドです。
単純に技量不足だったり、稚拙であるもの、下らないものは対象としません。
第一弾として、
道化師氏のサイト(http://www.trickpalace.net/)の
疑似乱数アルゴリズム「無相関性擬似乱数アルゴリズム-prime spiral-」
http://www.trickpalace.net/column/random.htm
を紹介します。このアルゴリズムおよび作者の言動の問題点は以下のとおり。
・MT(Mersenne Twister)がダメだと主張しながら、具体的な問題点は指摘できていない。
・MTより劣悪な乱数を生成しながら、MTより優れていると主張する。
・周期がたったの2^32のしかない(線形合同法と同レベル)
・無駄にテーブル参照するため遅い(線形合同法より劣悪)
・優れていると主張しながら、言葉の定義と評価基準を示すことはしない。
・indexと最低限の出力系列(各素数の和)が得られると、初期ベクトルが逆算ができてしまう。
・最低限の出力系列で、全パターンに出現する値の分布が確定する。
indexが確定すれば出現順まで確定するほど相関性が非常に高く劣悪。
・出ない値が確定するという点で乱数とはもはや呼べない。
・作者は暗号用途にも使えるつもりでいる。MTより「良い」乱数だと宣伝しているが、
実際は周期、分布などの点で低品質。信じて使うとろくなことにならない。

アルゴリズムの問題点や作者の人間性が明らかになる過程はこちらのスレで読めます。
擬似乱数
http://pc11.2ch.net/test/read.cgi/tech/1146071975/
2010/01/12(火) 01:04:22
これは過去ログ見てみたかったな
まあ乱数弄ってりゃそのうち巡り会うこともあろう
2010/01/12(火) 01:25:44
>>426が言いたいのはハッシュ関数かと思われ
253デフォルトの名無しさん
垢版 |
2010/01/12(火) 03:31:52
>>251
過去ログ（1146071975.dat）うｐしたね
http://www.dotup.org/uploda/www.dotup.org553146.dat.html
よかたら見るね
2010/01/12(火) 11:59:26
>>226
ホワイトノイズ(一様分布)じゃなくてブルーノイズでも良いなら方法はある。
ブルーノイズはホワイトノイズの低周波成分を除いたもの。

ホワイトノイズではモアレのような模様が見えるがブルーノイズでは模様は見えない。
2010/01/12(火) 16:02:33
乱数をjpegなどのデコーダーに食べさせるって言うのはどうだろうか
2010/01/13(水) 01:01:39
>>253
頂きました！
どうもありがとう〜
俺，週末になったらこれ読むんだ…
257241
垢版 |
2010/01/13(水) 05:15:25
試してみたが、VC++2008EE の /O2 でコンパイルした MEXP=216091 の sfmt の gen_rand32() で
1920x1200 を 30 枚埋めるのに、2003年の CPU P4 2.6C で 600ms 弱くらい。
今なら余裕じゃない？
2010/09/14(火) 17:15:16
DIEHARDテストはp-valueが一つでも p < .025 or p> .975が
あると失格なのでしょうか？

>>148のは13個あるのに合格って書いてありますけど。
359行 - 0.97978
391行 - 0.01013
533行 - 0.9948
541行 - 0.9988
543行 - 0.9825
569行 - 0.0003
602行 - 0.0243
610行 - 0.9907
612行 - 0.0049
672行 - 0.985720
687行 - 0.007759
692行 - 0.987352
857行 - 0.009586
13個
259デフォルトの名無しさん
垢版 |
2010/09/30(木) 05:03:43
擬似乱数についてまとめた本とかってあります？
260デフォルトの名無しさん
垢版 |
2010/09/30(木) 05:07:25
http://sky.geocities.jp/tcshacina/grs.c
作ってみました。
2010/09/30(木) 05:13:08
g・r・s！
2010/09/30(木) 09:22:33
>>259 ちょっと内容が古いけど「乱数」という本がある。
あと定番としてはTAOCP2巻。
2010/10/01(金) 01:32:20
grsって何？
2010/10/01(金) 02:15:37
ggrks
265デフォルトの名無しさん
垢版 |
2010/10/01(金) 07:52:17
乱数生成generalized reed solomon(GRS)
コンパイルしてみてください。あらさがしもOK。
2010/10/01(金) 12:22:27
>>265
$ gcc grs.c -o ggg
grs.c: In function `main':
grs.c:614: error: `__m128i' undeclared (first use in this function)
grs.c:614: error: (Each undeclared identifier is reported only once
grs.c:614: error: for each function it appears in.)
grs.c:614: error: syntax error before ')' token
grs.c:615: error: syntax error before ')' token
2010/10/01(金) 12:26:55
インデントぐちゃぐちゃだわ、場所によってコーディングスタイル違うわで気持ち悪いソースだな
268デフォルトの名無しさん
垢版 |
2010/10/01(金) 17:22:01
C:\cygwin>gcc -O2 -ftree-vectorize -ftree-vectorizer-verbose=5 -msse2 -o hash ha
sh.c
269デフォルトの名無しさん
垢版 |
2010/10/01(金) 17:23:29
C:\cygwin>gcc -O2 -ftree-vectorize -ftree-vectorizer-verbose=5 -msse2 -o grs grs.c
2010/10/01(金) 18:26:44
gcc tmp.c -I/usr/local/include -L/usr/local/lib -lgmp -o tmp -O2
2010/10/21(木) 22:32:31
著作権の表記無しで使える優秀な疑似乱数生成アルゴリズムある？
2010/10/22(金) 09:44:29
アルゴリズムに著作権はないから
2010/10/22(金) 10:15:00
つまり、「著作権表記なしで使える実装」のある、「優秀な擬似乱数生成アルゴリズム」を所望しているのかな。
んなもん、自分で実装すれば選び放題だ。
2010/10/22(金) 23:22:08
例えばメルセンヌツイスタはBSDライセンスだけど
コードを参考にして自分で実装すればBSDライセンスに従う必要は無いってこと？
2010/10/22(金) 23:34:49
パクリ度による
2010/10/23(土) 08:59:29
メルセンヌ・ツイスターの性能に勝るとも劣らない優れたもの？?らしい。
ttp://ayusya.hp.infoseek.co.jp/AlgorithmRandom.html
2010/10/23(土) 09:51:07
XORSHIFTにちょっと似てる？

いずれにしろ、高次元での相関や周期について、なんの数理的保証もないので
（MTはどちらも数理的に保証している）比較対象になんないよ。
当人は2次元の分布の見た目で評価して同等とか言ってるけど。
2010/10/23(土) 12:52:34
ISAAC
ttp://burtleburtle.net/bob/rand/isaacafa.html

WELL
ttp://www.iro.umontreal.ca/~panneton/WELLRNG.html

KISS
ttp://www.math.niu.edu/~rusin/known-math/99/RNG

こんなとこかな。
2010/10/23(土) 19:50:35
>>276

最初の
0x65AC9365UL >> ( r & 3 )
とか、シフトの回数の方が動的なのがちょっと新鮮だった。
2010/10/23(土) 20:43:04
ちょっと乱数が欲しいというときの物としてなら受け入れられるだろうに、
MTと比較してと書かれるとイタいだけだな。
2010/10/23(土) 21:29:25
このアルゴリズムで同一値が2回連続して出現する事なんてあるのか？
2010/10/23(土) 22:13:45
0 が出ないんじゃないか
2010/10/24(日) 01:27:04
周期が55898とか出てるんだけど、なんか間違ってる？
0x65AC9360ULにしたら長くなったけど…
2010/10/24(日) 02:29:14
周期が明示されていない、または、作者もわからないような擬似乱数はゴミだろ。
あと、同じ値が連続して出ないようなものは、いくら一次分布が均一に見えても乱数として使えない。
2010/10/24(日) 07:41:43
線形合同法なんか、まさしくその「同じ値が連続して出ない」乱数なんだが。
誕生日検定に通らないわけだけどね。
2010/10/24(日) 07:44:47
同じ値が連続して出たらその瞬間から値の変化しない乱数に
2010/10/24(日) 08:28:08
ていうか、周期性があるものは、連続して内部的に同じ値(状態)をとるわけがない。
単に、特定の部分(bit)を取り出しているから、その部分では同じ値に見えるというだけ。

線形合同法を使っていても、例えば32bit中14bitを用いるのであれば
同じ値の連続は起こる。
2010/10/24(日) 08:58:30
所詮は有限個の整数の集合を同じサイズの整数集合に写像する関数だから、
内部的に2度続けて同じ状態をとるとしたら、その後は永久にその値になるからな。
物理乱数でもなければ窓を使うことで、その精度での乱数性を確保しているというだけだし。

MTはM系列系統だから有限個の整数を一つずつ漏れなくたどり、
一周した場合に一様分布であることはほぼ自明だが、
相関性についてはどうだったろう？
統計的に検定はしてるけど、なにがしかの証明はされてたっけ？
2010/10/24(日) 16:41:50
検索してみたら、乱数の誕生日検定について、情報がネットには全く存在してないでやんのw
「誕生日のパラドックス」が乱数列として期待される通りに成り立つかどうかの検定ね。
確かKnuthの本には書いてあった。
2010/11/06(土) 22:40:38
別スレで聞いたのですがこちらに誘導されたので質問します。
メルセンヌツイスタを使って0〜(n-1)までの乱数を作りたいのですが、
これだとダメって言われたんですがどこを直せばいいのでしょうか。
INT value;
do {value=genrand_int31()%n;}
while(value>=0x0fffffff-value%n);
291,,・´∀｀・,,）っ-○○○
垢版 |
2010/11/06(土) 23:03:00
いろいろひどいからエスパーしていい？

要件：
１．genrand_int31()の剰余をとる
２．分布を完全に均等化するために剰余をとる前の値がNの倍数通りになるように再実行する

んで、

#define INT31_MAX 0x7FFFFFFF // ←ここ重要

int value;
do { value = genrand_int31();
} while (value >= INT31_MAX - (INT31_MAX % n));
value %= n;


MTは下位ビットをとっても安全な疑似乱数だからどっちでもいい
2010/11/06(土) 23:19:31
>>291
ありがとうございます。
31ビットは0x0fffffffだと勘違いしてました。
2010/11/06(土) 23:29:53
勘違いの問題点はそこじゃないと思うw
2010/11/07(日) 12:16:05
もう終わったのかもしれんが
>>291
value = genrand_int31();
これはマイナスの値が返って来る可能性があるから
value = genrand_int31() & 0x7FFFFFFF;
にするべきじゃなかろか
2010/11/07(日) 13:42:16
int31なのに負の値が帰ってくるの？
2010/11/07(日) 13:45:36
名前で判断してはいけない
2010/11/07(日) 15:15:37
MTのソースってこんな感じじゃなかったか？最近読んでないけど。

int genrand_int31() { return genrand_int32() & 0x7FFFFFFF; }
2010/11/07(日) 15:17:20
自己解決

/* generates a random number on [0,0x7fffffff]-interval */
long genrand_int31(void)
{
return (long)(genrand_int32()>>1);
}

2010/11/07(日) 16:30:25
ほうほう
2010/11/07(日) 16:39:17
より厳密に言えば右シフトが論理になるか算術になるかはCの規格上は未定義だったりするのね
unsignedなら論理シフトになるってのはある程度のCPUでは共通してるだけの話
2010/11/07(日) 16:50:17
なんてこった
2010/11/07(日) 19:45:33
逆だろ。

Cの規格では、
unsignedの右シフト
及び、
signed型であっても保持している値が正である時の右シフト
これはいずれも論理シフトになることが決まってるんじゃなかったか。
2010/11/07(日) 19:58:33
規格書落としてきた。
失礼、unsignedの場合は論理シフトで保証されるんだね。
2010/11/07(日) 20:03:17
この辺かな
ttp://flash-gordon.me.uk/ansi.c.txt

   The result of E1 >> E2 is E1 right-shifted E2 bit positions.  If E1
has an unsigned type or if E1 has a signed type and a nonnegative
value, the value of the result is the integral part of the quotient of
E1 divided by the quantity, 2 raised to the power E2 .  If E1 has a
signed type and a negative value, the resulting value is
implementation-defined.
2010/11/08(月) 10:40:27
よかった、ほっとした
2010/11/08(月) 12:09:17
そりゃunsignedなのに上から1が降ってきたら誰だってビビるわ
2010/11/08(月) 12:14:17
算術シフトしかないCPUで、シフト演算はのんきに全部その命令を生成しちゃう
コンパイラだってあるかもしれんし、Cの仕様はそれすらimplementation-definedと
言っていそうな雰囲気がある。この場合は違ったわけだが。
2010/11/12(金) 23:22:51
たまにはキャリーさんのことも思い出してあげて
2010/11/13(土) 09:26:39
キャリーをさがせ
310デフォルトの名無しさん
垢版 |
2011/01/18(火) 01:52:26
NIST検査について質問です。乱数の統計的性質を調べるソフトなのですが、
このテストをすべて合格しないと乱数とは言えないのでしょうか？
特にFFT検査の場合に不合格になります。周期はないと思うのですが、なぜか
うまくいきません。それとも、これだけは絶対に通らなくてはいけないという
検査があるのでしょうか。どなたかご教示願います。
2011/01/19(水) 01:13:06
テストに合格しようがしまいが乱数は乱数じゃね？
2011/01/19(水) 01:42:36
二回（以上）続けて同じ数字が出ないものは乱数と呼びたくないな
2011/01/19(水) 09:31:42
>>312
>>284-288
2011/01/19(水) 16:52:17
疑似乱数に詳しくない俺が言うべきじゃないのかもしれないけど
乱数と疑似乱数を分けて考えてない人が居るような気がするんだ。
乱数、たとえばサイコロとかで作った乱数なら2回以上続けて6が出ることもあるでしょ。
でも線形合同法とかの疑似乱数は、同じ数が2回続けて出ることはないし、
循環しちゃうし乱数とは別物じゃない。だから、疑似と真の区別をはっきりさせないと
話がかみ合わなくなる気がするんだ。
2011/01/19(水) 17:03:32
本当にわかってないな
2011/01/19(水) 17:14:01
一気に糞スレ化したね。
2011/01/19(水) 17:53:20
>>315
何処がどう分かってないのかハッキリさせないと、その発言に意味はないと思いますよ。
意味のない発言の塊が２ｃｈなわけですけど
2011/01/19(水) 17:55:41
314は巨大な状態空間の一部だけ切り出してる擬似乱数が想像できないんだろ
2011/01/19(水) 18:20:58
>>317
>>313
2011/01/19(水) 18:39:02
>>318
そういうのは自分で考えさせないと
321314
垢版 |
2011/01/19(水) 19:16:42
>>318、320
よく分からないんですが、疑似と真乱数を分けて考える必要はないということですか？
2011/01/20(木) 00:03:34
何故区別する必要があると思ったの？
問題の出てくる例を挙げて欲しい。
2011/01/20(木) 00:15:30
えさを与えないでください
324314
垢版 |
2011/01/20(木) 01:23:19
>>322
そもそもこの2つは別物なのにその2つを同じ言葉で表すのが気持ち悪いと感じるんですよ。
>>310は疑似乱数のテストについて質問していて、>>311、312は真乱数を前提に
話してるみたいだし、>>313は疑似乱数を前提に発言してる。どうも疑似と真を分けてないから
話が噛合ってないように見えるんですよ
2011/01/20(木) 01:54:43
スルーしてください
2011/01/20(木) 05:00:53
スレタイも読めないヤツに何かが分かるなんて期待するヤツはいない。
327デフォルトの名無しさん
垢版 |
2011/01/20(木) 17:55:54
わざと答えをはぐらかしてるみたい
328デフォルトの名無しさん
垢版 |
2011/01/20(木) 18:03:55
324は正しい
2011/01/20(木) 18:06:56
乙です
2011/04/16(土) 11:03:07.44
George Marsaglia (1924 - 2011)
ttp://www.legacy.com/obituaries/tallahassee/obituary.aspx?n=george-marsaglia&pid=148777353
331デフォルトの名無しさん
垢版 |
2011/04/16(土) 11:16:55.91
age
2011/05/18(水) 23:19:05.17
乱数で数値nの約数の合計って使えないの？
結構バラバラなんだけど
2011/05/18(水) 23:21:48.27
とりあえず検定の結果を示してもらわんとなんとも。

それで線形合同法の推奨されてるパラメータを越える成績ならともかく。
2011/05/18(水) 23:58:05.10
数値nをどこから持ってくるのか詳しく聞かせてもらおうじゃないか
2011/05/19(木) 16:36:50.88
ぶっちゃけそこはn=n+(秒針)みたいなでいいと思う
あとn/2/(nの約数の合計)なら多分1〜0しかでない
2011/06/12(日) 19:32:33.48
RDRANDで疑似乱数ｵﾜﾀ?
2011/06/12(日) 21:41:33.09
>>336
http://software.intel.com/file/36945
>8.6
>RDRAND returns random numbers that are supplied by a cryptographically secure,
>deterministic random bit generator (DRBG). The DRBG is designed to meet the NIST
>SP 800-90 standard. The DRBG is re-seeded frequently from a on-chip non-deterministic
>entropy source to guarantee data returned by RDRAND is statistically
>uniform, non-periodic and non-deterministic.
超訳：
RDRAND 命令は、暗号論的に安全である**決定的な**ランダムビット生成器（DRBG)により供給される乱数を返す。
DRBG は NIST SP 800-90 http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf　に適合するように設計されている。
DRBG はチップに内蔵されている非決定的なエントロピー源により、定期的に初期値を再与されているため、
その結果、RDRAND命令は統計的に均一かつ非周期的、非決定的なデータを生成することが保証されている。

オンチップ-エントロピー源の出来如何に関わるという印象を受けますが、さて、どうでしょうか？
2011/06/12(日) 22:06:24.66
なんで擬似乱数が終わるんだよ？
分からない奴は黙っとけ
2011/06/12(日) 22:08:35.00
容易に再現できる乱数列が必要な応用があるとか全く知らないんだろ
2011/06/16(木) 00:25:21.98
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NUM_THREAD 8
void *th_main(void *arg){
unsigned i, sum = 0;
for(i = 0; i < 1000; i++) sum += rand();
printf("Thread#%d: sum = %u\n", pthread_self(), sum);
}
int main(){
int i;
pthread_t th[NUM_THREAD];
srand(time(NULL));
for(i = 0; i < NUM_THREAD; i++) pthread_create(&th[i], NULL, th_main, NULL);
for(i = 0; i < NUM_THREAD; i++) pthread_join(th[i], NULL);
return 0;
}

rand()ってスレッドごとに独立した系列の乱数列返すの？
既出だったらすいません。
環境はcygwin+gccです。
2011/06/16(木) 13:48:55.52
そもそもrandがスレッドセーフである保証がない。
スレッドセーフでない関数の読み出しにはロックをかけろ。

疑似乱数の実装がスレッドローカルならスレッドIDとタイムスタンプを組み合わせてseedに使うかな
2011/06/16(木) 21:37:26.52
>>340
rand_r()は実装されてないの？
シミュレーションとかに使うなら、当然もっとまともな乱数使うべきなんだけど
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況