編集履歴

回答編集履歴

おまけを追加

2020/05/17 12:01

投稿

スコア21739

test CHANGED Viewed

@@ -266,4 +266,86 @@
-Nが3程度ではそれほど違いは見えないでしょう(乱数の周期を越えるぐらいの試行回数を重ねないと、ランダム性から出る誤差の方が大きすぎて、有意義な結果が見えない)。ですが、「0から99までの数を乱数で取得(1D100をふるイメージ)し、50未満なら成功」みたいなゲームのプログラムを組んだとき、成功確率はわずかに50%を越えます(低い数値のほうが出やすいので、SANチェックもきっと乗り越えられるぜ！)。乱数の取り方とその利用方法によっては僅かな差がちょっとの差としてあられる可能性があると言うことです。といっても、その差は変わらずちょっとなのでゲーム程度では些細な問題です。しかし、数学的な厳密さが必要とされる統計やシミュレーション等では問題になる可能性があります。(そもそも、rand()の実装は環境依存であり、良い乱数ではないことが多いので、厳密さが求められるものに使用するのは避けるべきではありますが。)
+Nが3程度ではそれほど違いは見えないでしょう(乱数の周期を越えるぐらいの試行回数を重ねないと、ランダム性から出る誤差の方が大きすぎて、有意義な結果が見えない)。ですが、「0から99までの数を乱数で取得(1D100をふるイメージ)し、50未満なら成功」みたいなゲームのプログラムを組んだとき、成功確率はわずかに50%を越えます(低い数値のほうが出やすいので、SANチェックもきっと乗り越えられるぜ！)。乱数の取り方とその利用方法によっては僅かな差がちょっとの差としてあられる可能性があると言うことです。といっても、その差は変わらずちょっとなのでゲーム程度では些細な問題です。しかし、数学的な厳密さが必要とされる統計やシミュレーション等では問題になる可能性があります。(そもそも、`rand()`の実装は環境依存であり、良い乱数ではないことが多いので、厳密さが求められるものに使用するのは避けるべきではありますが。)
+---
+【おまけ】
+`rand() % N`はそれぞれが現れる確率が等しいとは言えないという話でした。では、どうすれば良いのかというと、はみ出てしまっている部分を切ればいいと言うことです。たとえば、RAND_MAXが32767の場合、0から順番に0,1,2と入れておくと、最後の方は、32766が0、32767が1となって、2にいれるものが一つだけ足りません。なので、乱数が32766や32767の場合は結果を切り捨てて、乱数取得からやり直しすれば、いいとなります。
+では、早速、[GCCのlibstc++](https://github.com/gcc-mirror/gcc/blob/8d9254fc8aa32619f640efb01cfe87cc6cdc9ce1/libstdc%2B%2B-v3/include/bits/uniform_int_dist.h#L244-L253)を参考にしながら、100の場合のコードを書き換えて見ましょう。
+```C
+#include <stdio.h>
+#include <stdlib.h>
+#define TRIAL_NUMS 100000000
+#define N 100
+#define N_SCALING (RAND_MAX / N)
+#define N_PAST (N * N_SCALING)
+int main(void)
+{
+	srand(0);
+	long long count[N] = {0};
+	for (long long i = 0; i < TRIAL_NUMS; i++) {
+		int r;
+		do {
+			r = rand();
+		} while (r >= N_PAST);
+		count[r / N_SCALING]++;
+	}
+	printf("RAND_MAX: %d\n", RAND_MAX);
+	for (int i = 0; i < N; i++) {
+		printf("%d: %lld\n", i, count[i]);
+	}
+	return 0;
+}
+```
+今度は少ない数の方に1000000越えが偏るということは起きなかったと思います。
+さて、上のコードを見てみましょう。`do ～ while (...);`の部分は最初に言った切り捨て部分です。最後の切れ端みたいな乱数になった場合(`N_PAST`以上になった場合)はやり直ししています。そうして得られた乱数に対して、`N_SCALING`を割っています。そう、剰余ではなく商を使っています。
+なぜ、剰余ではなく商なのか？`r % N`でもいいのでは無いのか？という疑問はありますが、GCCの実装がそうだったので、今回はそうしました。では、なぜ、GCCがそのようにしているのかについては、すいませんが、もっと詳しい人に聞いていただくようお願いします。

以下じゃない未満だ

2020/05/17 12:01

投稿

raccy

スコア21739

test CHANGED Viewed

@@ -266,4 +266,4 @@
-Nが3程度ではそれほど違いは見えないでしょう(乱数の周期を越えるぐらいの試行回数を重ねないと、ランダム性から出る誤差の方が大きすぎて、有意義な結果が見えない)。ですが、「0から99までの数を乱数で取得(1D100をふるイメージ)し、50以下なら成功」みたいなゲームのプログラムを組んだとき、成功確率はわずかに50%を越えます(低い数値のほうが出やすいので、SANチェックもきっと乗り越えられるぜ！)。乱数の取り方とその利用方法によっては僅かな差がちょっとの差としてあられる可能性があると言うことです。といっても、その差は変わらずちょっとなのでゲーム程度では些細な問題です。しかし、数学的な厳密さが必要とされる統計やシミュレーション等では問題になる可能性があります。(そもそも、rand()の実装は環境依存であり、良い乱数ではないことが多いので、厳密さが求められるものに使用するのは避けるべきではありますが。)
+Nが3程度ではそれほど違いは見えないでしょう(乱数の周期を越えるぐらいの試行回数を重ねないと、ランダム性から出る誤差の方が大きすぎて、有意義な結果が見えない)。ですが、「0から99までの数を乱数で取得(1D100をふるイメージ)し、50未満なら成功」みたいなゲームのプログラムを組んだとき、成功確率はわずかに50%を越えます(低い数値のほうが出やすいので、SANチェックもきっと乗り越えられるぜ！)。乱数の取り方とその利用方法によっては僅かな差がちょっとの差としてあられる可能性があると言うことです。といっても、その差は変わらずちょっとなのでゲーム程度では些細な問題です。しかし、数学的な厳密さが必要とされる統計やシミュレーション等では問題になる可能性があります。(そもそも、rand()の実装は環境依存であり、良い乱数ではないことが多いので、厳密さが求められるものに使用するのは避けるべきではありますが。)