疑似乱数２

1 ：デフォルトの名無しさん：2007/10/17(水) 22:34:59 .net

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

前スレ
擬似乱数
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

494 ：デフォルトの名無しさん：2016/10/06(木) 07:29:45.67 ID:iNNf2EsF.net

こういう厚かましい無能が現れるのも乱数性のなせるわざか。

495 ：デフォルトの名無しさん：2016/10/06(木) 08:30:59.70 ID:2aWpWU4C.net

三木さんに新しい疑似乱数生成方式を考案してほしい
三木乱数で

ミキさんに考えてもらって乱数ミキでもいい

496 ：デフォルトの名無しさん：2016/10/06(木) 12:12:14.44 ID:Yw0Cruyw.net

線形合同法は、下位ビットが偏る

メルセンヌツイスター、1996の方が、周期が長い

Xorshift、2003は高速

497 ：デフォルトの名無しさん：2016/10/08(土) 06:01:51.17 ID:KfBpvv2w.net

順番性のテストをしたことあるけど、
xorshiftは異常なほど結果が偏ってるよ。
逆に線形合同法は異常なほど分散する。

結局、統計学や確率論などの乱数の順番が重要になる処理では結局どちらも使えない。
例えば、rand(100)で 5回連続で 20以下が出るかどうか。などの処理確率の信憑性が極めて疑わしい。


ちなみにテストはいろいろやったけど、xorshiftのおかしさが一撃でわかるのが x座標y座標と順番に出して印をつけてく方式。
線形合同法に至っては、rand(100) を100個出すだけで十分。確率上あり得ないくらい重複が少なく綺麗に分散する。


線形合同法は、下位ビットのかたよりがすぐ話題になるが、1/max の精度で乱数を必要とすることがあまりないのでけっこうどうでもいい。


ちなみに俺はここ数年、線形合同法で最初のseed設定時に乱数を1024個プールして、
array[rand(max) % 1024];
みたいな感じでランダムで取り出して使う。(そしてそこに次の乱数をセットする)。
って感じの自作汎用dllを使ってる。
トランプだって、2度シャッフルすればもう最初の並び順との因果関係は誰にも発見出来ないってね。


まぁメモリは多少食うし速度も最速じゃないけど、別に最速最小を求めるような研究者じゃないし。俺は。

498 ：デフォルトの名無しさん：2016/10/08(土) 07:32:49.80 ID:U+ATce89.net

>>497
とりあえず、全bit使おうとするのは良くないというのは基本だと思うが

だからこそ、内部で32bitとかで種を持っているにもかかわらず、
標準Cでの要求が14bitとかそういう話になる

単純に割って使う(シフトでの下位bit切り捨てに相当)んじゃなく、上位もマスクして切り捨てて使うのが常識

499 ：デフォルトの名無しさん：2016/10/08(土) 07:47:16.98 ID:PgGGpXVn.net

>>497
>ちなみに俺はここ数年、線形合同法で最初のseed設定時に乱数を1024個プールして、
>array[rand(max) % 1024];
>みたいな感じでランダムで取り出して使う。(そしてそこに次の乱数をセットする)。

それはDonald Knuth先生のリオーダーアルゴリズムBに近いな
内部のバッファリングは256だけどC++のstd::knuth_b（シャッフルオーダーね）がある

500 ：デフォルトの名無しさん：2016/10/08(土) 14:10:54.10 ID:PgGGpXVn.net

>>497
>rand(max) % 1024
この部分は下位ビットの偏りが諸に関連しているよ
因みにstd::knuth_bではstd::minstd_rand0を元にバッファサイズで正規化して
値を取り出しているから、その演算のせいで他のに比べると重い
周期も数学的に不明だったかな

501 ：デフォルトの名無しさん：2016/10/08(土) 18:34:54.73 ID:KfBpvv2w.net

あんま深く考えてなかったけどそうかもね。
ただし検定は通ってるから、まあいいっちゃいいけど。

実用上の実質的な周期はそのまま線形合同法と同じだよ。
まあ300回くらいなら多く回しても実用上にも問題ないけど、そんなのは計算しない。

>rand(max) % 1024
これは素数にすることでノーコストで解決できるから気が向いた時にでもやっとくよ。
ただ、どんなに下位ビットが偏ってた所で、
araay[988]の中身 と araay[986]の中身の因果関係、もしくは共通点は何か、と聞かれても判明させるのは不可能に近いと思うけどね。

>上位もマスクして切り捨てて使うのが常識
ただ線形合同法はそれでいいとしてxorshiftは捨てるべきビットが特定できないような？


まあ俺はシャッフルして何も捨てないのが好きらしい。
全部が若干遅いんだけどね。特にseed植える時。

502 ：デフォルトの名無しさん：2016/10/26(水) 12:50:05.40 ID:X3TP1P6r.net

奥村先生のアルゴリズム事典にある乱数の改良法だぬ

xorshiftは生で使うと俺も気持ち悪さを感じるので線形合同法を足してる

503 ：デフォルトの名無しさん：2016/12/10(土) 11:46:44.94 ID:DCOx50tb.net

統計の知識は中高どまり（平均・中央値・分散程度か）なので
乱数用に内部状態が32ビットしか確保できないソフトに対して単にxorshiftを採用して「検定もいい結果らしいし」と気にしていなかった

思ったより良くないとなると，プールしておいてランダムに取り出す方法も使えないし悩むな

504 ：デフォルトの名無しさん：2016/12/14(水) 12:22:06.08 ID:7W6mxi0O.net

1個使ったら100個捨てるとか
RNGが保証してるのは周期だけだと割りきって頑張って調律するとか

505 ：デフォルトの名無しさん：2016/12/14(水) 23:07:36.84 ID:2UzQxrtp.net

素人の生半可なオレオレ乱数はやらない方が身のため

506 ：デフォルトの名無しさん：2016/12/31(土) 21:32:49.60 ID:VVtKGmEj.net

2017は素数か

507 ：デフォルトの名無しさん：2017/01/01(日) 11:37:31.32 ID:DY9bt0tG.net

あけましておめでとうございます
return x = x * 2017 + 1;

508 ：デフォルトの名無しさん：2017/01/05(木) 01:13:53.38 ID:yRe7g27Q.net

一個使って100個捨てるとか馬鹿の極み
コストを101倍にしてどうする。
コスト2倍も出せば問題のない乱数を作れるのに

509 ：デフォルトの名無しさん：2017/01/05(木) 06:28:07.10 ID:42rV0dht.net

S/N比最低の２ちゃんでドヤっってる場合じゃないよな

510 ：デフォルトの名無しさん：2017/01/05(木) 20:10:30.85 ID:atmVS5w4.net

S/N比最低というのは、乱数としては素晴らしいことだ。

511 ：デフォルトの名無しさん：2017/01/06(金) 09:49:58.47 ID:zAIptLYs.net

つまり2chの書き込みをもとに乱数列を作る生成器を作れば…？

512 ：デフォルトの名無しさん：2017/01/06(金) 12:01:18.30 ID:CHjfjTiP.net

片寄りが多くて一様じゃないからなあ……

513 ：デフォルトの名無しさん：2017/01/06(金) 14:32:25.52 ID:eb3De0HO.net

>>512
ワロタ
一様分布じゃなく、一応分布が2chらしい

514 ：デフォルトの名無しさん：2017/02/22(水) 09:39:50.93 ID:BVjvbr4Q.net

BIG 不正
いまGoogleで検索したら、すごいのがでますね

515 ：デフォルトの名無しさん：2017/02/22(水) 09:56:53.06 ID:BVjvbr4Q.net

「14試合×5口分の予想結果が2回続けて全く同じという極めて不自然な結果が出力され、
システムの不具合や不正ではないかと一騒動となっている（中略）
日本スポーツ振興センターと楽天から調査結果の発表がなされたのだが、
くじは確かに販売されたものである」

スポーツくじ「BIG」でランダムなはずの予測結果が2連続で一致するも「偶然」との回答 - エキサイトニュース
http://www.excite.co.jp/News/it_g/20170221/Slashdot_17_02_20_1619238.html
2017年2月22日 09時50分

516 ：デフォルトの名無しさん：2017/02/22(水) 12:02:19.51 ID:Acz49b5N.net

一人が予想して当たればその確率かもわからんけど、
1000人が予想した場合の期待値は1000倍になるんじゃね

517 ：デフォルトの名無しさん：2017/02/23(木) 07:14:10.76 ID:WFbVQHcp.net

２回とも当たったんならすごいけどな

518 ：デフォルトの名無しさん：2017/02/23(木) 07:17:16.12 ID:WFbVQHcp.net

数枚買ったうちの2枚が連続して同じだったのか
そりゃ金返せってなるな

最初から買わんけど

519 ：デフォルトの名無しさん：2017/02/23(木) 07:23:45.91 ID:WFbVQHcp.net

セキュリティ上の理由から
アルゴリズム公開しないって書いてあるけど
全組み合わせを逐次予想するんじゃなくて
元々予想したくじを用意してあって
そこから適当に買った枚数分選んでくるとかだったら
重複確率は上がりそうだな

たまたま購入者が気付いただけで
気付かずに捨てられた券で
過去の重複してたのもっとあるんじゃないか

520 ：デフォルトの名無しさん：2017/02/23(木) 08:54:22.37 ID:907E0Xet.net

どんな擬似乱数でも、内部的に状態を示す値を保持していて、それを元に次回の乱数を計算で出す
その値を初期化するのがsrand等だけど、その時に限らず常に値は持っているので
偶然内部の値が同じなんてこともよくある

ただし、普通は同じ値であっても、別の用途に乱数を使うので、同一であったことが問題になることはない

けれど、もし、14試合分の予想の直前の段階での内部的な値が、前回と全く同じ値だったとすると
そこから算出される各試合結果を示す乱数も、全く同じ値が出て
予想結果も全く同じものになる


偶然同じ状態値を持っている時に同じ買い方をしたために、全く同じ予想値になった

状態値のbit数が少ない(例えば普通に線形合同法だと32bitか)のを修正するか、
あるいはアルゴリズム的に同じ擬似乱数だけで順番に算出することを見直すか
そういうことをしないと、同じことが再び起こる可能性はある

擬似乱数だと防げないけどね


宇宙が始まるより低い確率云々ってのはナンセンス
擬似乱数の内部値が一致していて、単純に擬似乱数を利用するアルゴリズムだったというだけ
これは珍しいけど起こりうること

521 ：デフォルトの名無しさん：2017/02/23(木) 13:04:42.59 ID:UXkH84Wv.net

宇宙云々はあくまで真の乱数が使われていた場合でしょ

522 ：デフォルトの名無しさん：2017/02/23(木) 13:15:51.47 ID:eG9NqkD/.net

>>520
状態機械で内部の値が一緒だったらその次もその次もずっと同じ値を出し続けるんじゃね

523 ：デフォルトの名無しさん：2017/02/23(木) 13:37:51.43 ID:lN59Dhjm.net

真の乱数なら、種の設定は (少なくとも実用上は) いかなる場合も最初の一度きりで二度と結果がループすることはない

524 ：デフォルトの名無しさん：2017/02/23(木) 13:40:24.47 ID:lN59Dhjm.net

と言っても宇宙の何かの物理法則が真の乱数を作ることはないのだろうと思うけど。
全ては必ず有限らしいし、その中でのチューリング完全なんだろうだし。

525 ：デフォルトの名無しさん：2017/02/23(木) 13:59:17.36 ID:7wYQlXII.net

一つずつ乱数生成してないのかもね

526 ：デフォルトの名無しさん：2017/02/23(木) 16:45:07.24 ID:eG9NqkD/.net

>>523
真じゃない乱数は
ループの長さが長いか短いかだけで
いずれはループするんだよな

527 ：デフォルトの名無しさん：2017/02/23(木) 16:46:44.91 ID:WFbVQHcp.net

>>525
なんらかのバグで内部状態が変化しなくなって
２回連続で同じ値を出してしまったら
再起動がかかるシステムだったりするかもしれない

528 ：デフォルトの名無しさん：2017/02/23(木) 21:50:11.33 ID:5geihC2S.net

>>522
「前回(の乱数取得時)と同じ」という意味ではなく
「前回試合予想をした時と同じ」という意味ね

どちらも、同じ値から同じ試合の予想をして、
結果、前週と全く同じ予想が14試合x5口分で起きた

529 ：デフォルトの名無しさん：2017/02/24(金) 14:00:51.79 ID:xRGcfmim.net

メルセンヌツイスタ使ってなかったんだろ

530 ：デフォルトの名無しさん：2017/02/24(金) 19:02:56.20 ID:3z/u0Cfz.net

用途が用途だから暗号論的擬似乱数の適応だろ
/dev/urandomでもCryptGenRandomでも

531 ：デフォルトの名無しさん：2017/02/25(土) 15:09:25.02 ID:u8Ry8YI7.net

状態変数が同じになったから同じ数列が出たんじゃねーよ。
二セット分繰り返す数列を出力する状態変数だっただけだろ。

http://science3.2ch.net/test/read.cgi/math/1088351567/424-425
円周率の 93299341 桁目から 07214545 という数列が出るそうだ。
まあ大体その辺で出そうな桁数だ。
おそらく無限に調べれば 1/10,0000,000 より少しだけ少ない頻度で出現するだろう。
そしてそのうちの 1/10,0000,000 は二回続く、つまり 1/10+E16 程度で 0721454507214545 という数列が出現するであろう。

目立つ組み合わせだから話題だが、どの二セットを取っても、その組み合わせが発生する確率は同じだ。

532 ：デフォルトの名無しさん：2017/02/25(土) 16:57:29.92 ID:usTDxsWv.net

e なら割と早く出て来る

533 ：デフォルトの名無しさん：2017/03/10(金) 21:31:43.44 ID:ARsP6JfD.net

PCGってどうなん？
ttp://www.pcg-random.org/

説明読んだりビデオ観たりした限りでは優れているみたいなんだけども
アルゴリズム的には線形合同法とXorShiftのハイブリッドの様な感じで
結構単純な構造なんだけど、高速で良質な乱数を生成するとか

因みに2年前に発表されているみたいなんだけど知らんかったわ

534 ：デフォルトの名無しさん：2017/04/23(日) 03:06:26.50 ID:H8Cvp+NU.net

周期性と分布バランスが目的用途に特化できるならそれが最強だろ

535 ：デフォルトの名無しさん：2017/05/11(木) 11:22:40.04 ID:yPF7Zec4.net

最強(笑)

536 ：デフォルトの名無しさん：2018/01/01(月) 10:34:52.74 ID:Adreh4LC.net

Xn+1=Xn*201+8+1/1
Xn+1=Xn*(2018>>1)+1
あけおめ

537 ：デフォルトの名無しさん：2018/05/23(水) 20:53:42.20 ID:Au5e7VGg.net

僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

BZKM3

538 ：デフォルトの名無しさん：2018/07/05(木) 01:00:09.16 ID:RfoszcD2.net

5E7

539 ：Goldwasser：2019/01/03(木) 13:41:14.69 ID:r8gE2use.net

ご覧あれーw

#include "pch.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#define N 32

unsigned char x1[N], x2[N], x3[N];

void rp(unsigned char* a) {
int i, j, x;

for (i = 0; i < N; i++) {
a[i] = i;
}
for (i = 0; i < N - 2; i++) {
// rand from i+1 to N-1
j = (rand() % (N - 1 - i)) + i + 1;

// swap a[i] and a[j]
x = a[j];
a[j] = a[i];
a[i] = x;
}
if (a[N - 1] == N - 1) {
a[N - 1] = a[N - 2];
a[N - 2] = N - 1;
}
}

540 ：デフォルトの名無しさん：2019/01/03(木) 13:41:50.45 ID:r8gE2use.net

後半

int data() {
int i, j = 0, k = 0;
unsigned int a[N];
unsigned int z[N];
unsigned char w[N];

for (i = 0; i < N; i++)
a[i] = rand()%256;
for (i = 0; i < N; i++)
z[i] = 0;

k = 0;

while (k< 4000) {
for (i = 0; i < N; i++)
z[i] ^= a[x2[i]];
for (i = 0; i < N; i++)
a[i] ^= z[i];
for (i = 0; i < N; i++)
w[i] = x1[x2[x3[i]]];
*x2 = *w;
k++;
for(i=0;i<N;i++)
printf("%u,",a[i]);
}
printf("\n");

return 0;
}

541 ：Goldwasser：2019/01/03(木) 13:42:22.37 ID:r8gE2use.net

最後

int main() {

rp(x1);
rp(x2);
data();

return 0;
}

542 ：デフォルトの名無しさん：2019/01/06(日) 08:57:50.46 ID:kWOVO8kw.net

誰かTestU01の使い方を教えてください

543 ：デフォルトの名無しさん：2019/02/24(日) 02:35:20.31 ID:LCfXPkf7.net

>>542
http://www.pcg-random.org/posts/how-to-test-with-testu01.html