C言語関係掲示板

過去ログ

No.429.一定区間の乱数を求める場合、RAND_MAXで除算すべきか

[戻る] [ホームページ]
No.2992

RAND_MAXを使うべきでしょうか
投稿者---ともじ(2002/10/18 16:40:58)


実は常々疑問に感じておりましたので、質問させてください。

一定区間の乱数を求める場合、かずまさんのご提示のプログラム(No.2975)
のように、RAND_MAXで除算すべきなのでしょうか。
C FAQ 日本語訳
http://www.asdf.jp/mirror/c_faq/C_FAQ_3.txt
にもRAND_MAXを使う方が良いと書いてあるのですが、
試してみるとRAND_MAXを使った場合も%を使った場合も
左程変わりがなく乱数が得られますので、わかりやすいほうがよいと、
%演算子を使っています。

実際、以下のプログラムを実行しても手持ちのどのコンパイラを用いても
同じように乱数が求められるのです。
実のところ%演算子を用いるのはよろしくないのでしょうか。
ご意見いただければと思います。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N      10000
#define LAST   100

int irandom_a(int n)
{
	return rand() / (RAND_MAX + 1.0) * n;
}

int irandom_b(int n)
{
	return rand() % n;
}

void minmax(int *tb, int *min, int *max)
{
	int i;
	
	*min = *max = *tb;
	for (i = 0; i < LAST; i++) {
		if (*max < *tb) *max = *tb;
		if (*min > *tb) *min = *tb;
		tb++;
	}
}

int main()
{
	int i, tb_a[100] = {0}, tb_b[100] = {0};
	int min, max;
		
	srand(time(0));

	for (i = 0; i < N; i++)
        	tb_a[irandom_a(LAST)]++;

	for (i = 0; i < N; i++)
        	tb_b[irandom_b(LAST)]++;

	printf("RAND_MAX\n");
	for (i = 0; i < LAST; i++)
	    printf("%3d ", tb_a[i]);
		
	printf("\n%%\n");
	for (i = 0; i < LAST; i++)
	    printf("%3d ", tb_a[i]);
	
	minmax(tb_a, &min, &max);
	printf("\nRAND_MAX min:%d max:%d\n", min, max);
	minmax(tb_b, &min, &max);
	printf("%%        min:%d max:%d\n", min, max);

	return 0;
}




No.2994

Re:RAND_MAXを使うべきでしょうか
投稿者---TDa(2002/10/18 17:22:06)


こんにちはともじさん。いつもお世話になっています。

Cfaqですがかかれていたのがだいぶ前ということもありますので最近のrand()
関数の実装は十分にランダムになっているということが考えられます。

私は実装詳細を知りませんし統計を取ったことも無いですが実用上
rand() % n
ではばらつかなくて困ると感じたことは無いです.

まぁ私も盲目的にCfaqのコードからパクッていろんなところで使うこともありますが初学者に対してはわかりやすさを優先してもよいと思います.

No.3001

Re:RAND_MAXを使うべきでしょうか
投稿者---かずま(2002/10/18 18:55:03)


>        printf("RAND_MAX\n");
>        for (i = 0; i < LAST; i++)
>            printf("%3d ", tb_a[i]);
>                
>        printf("\n%%\n");
>        for (i = 0; i < LAST; i++)
>            printf("%3d ", tb_a[i]);

2つ目は printf("%3d ", tb_b[i]); ですね。

----------------------------------------------------------------------
さて、RAND_MAX の値ですが、VC++、BC++、LSI C-86 では 32767(0x7fff)。
gcc では、2147483647(0x7fffffff) です。ここでは、32767 で考えてみましょう。
すなわち、rand() は、0〜32767 の 32768個の値を一様に返すものと仮定します。

0 〜 (n-1) の n 個の乱数を得たい場合、% を使うものは、n の値が小さい場合は
よいのですが、大きい場合に問題になります。

たとえば、n = 10000 としてみましょう。
0〜9999 の各値が 1/10000 = 0.01% の確率で出てほしいものです。

     rand()     | rand() % n
  --------------+-----------
      0 〜 9999 |  0 〜 9999
  10000 〜19999 |  0 〜 9999
  20000 〜29999 |  0 〜 9999
  30000 〜32767 |  0 〜 2767

   0〜2767 の出る確率は、4 / 32768 = 0.0122070312500%
2768〜9999 の出る確率は、3 / 32768 = 0.0091552734375%
前者は後者の 0.012207 / 0.009155 = 1.33337倍です。
これでは、一様な乱数とは言えません。

では、n = 10 の場合はどうでしょう。
0〜9 の各値が 1/10 = 10% の確率で出てほしいものです。

     rand()     | rand() % n
  --------------+-----------
      0 〜    9 |  0 〜 9
     10 〜   19 |  0 〜 9
        :       |    :
  32750 〜32759 |  0 〜 9
  32760 〜32767 |  0 〜 7

0〜7 の出る確率は、3277 / 32768 = 10.0006103515625%
8〜9 の出る確率は、3276 / 32768 =  9.9975585937500%
これなら、期待通りほぼ 10% の確率でどの値も出ると言えるでしょう。


一方、RAND_MAX + 1.0 で割って得られた 0.0以上 1.0未満の値を n 倍する
やり方では、一様な乱数が期待できます。
RAND_MAX + 1.0 = 32768.0 = 2の15乗ですから、この値で割っても、
浮動小数点の仮数部は、rand() が返した値そのままで、指数部のみが 15小さい
値になるだけですから、精度は保証されます。


No.3004

Re:RAND_MAXを使うべきでしょうか
投稿者---かずま(2002/10/18 19:07:16)


>    0〜2767 の出る確率は、4 / 32768 = 0.0122070312500%
> 2768〜9999 の出る確率は、3 / 32768 = 0.0091552734375%
> 前者は後者の 0.012207 / 0.009155 = 1.33337倍です。

訂正します。 前者は後者の 4 / 3 = 1.3333倍です。


No.3011

Re:RAND_MAXを使うべきでしょうか
投稿者---ともじ(2002/10/19 00:14:34)


いつもお世話になりありがとうございます。早速のお返事ありがとうございます。

> 2つ目は printf("%3d ", tb_b[i]); ですね。

相変わらず粗忽者ですみません・・・。
ついでに言えば、
 int i, tb_a[100] = {0}, tb_b[100] = {0};

 int i, tb_a[LAST] = {0}, tb_b[LAST] = {0};
にすべきでした。

> 0 〜 (n-1) の n 個の乱数を得たい場合、% を使うものは、n の値が小さい場合は
> よいのですが、大きい場合に問題になります。
> たとえば、n = 10000 としてみましょう。
> 0〜2767 の出る確率は、4 / 32768 = 0.0122070312500%
> 2768〜9999 の出る確率は、3 / 32768 = 0.0091552734375%
> 前者は後者の 0.012207 / 0.009155 = 1.33337倍です。
> これでは、一様な乱数とは言えません。

これはすごく納得のいく答えです。
n=10  0〜7:8〜9     = 3277/3276 = 1.00030525・・・
n=100  0〜67:68〜99    = 328/327  = 1.00305810・・・
n=1000 0〜767:768〜999  = 33/32   = 1.03125
n=10000 0〜2767:2768〜9999 = 4/3    = 1.33333333・・・
ということですね。%で許容できるのは、100くらいまででしょうか。

そういう意味ではFAQの
 rand() / (RAND_MAX / N + 1)
も問題があるのですね。
同じFAQにある
 (int)((double)rand() / ((double)RAND_MAX + 1) * N)
は、かずまさんのやり方と同じですが。

FAQの
> rand() % N /* タコ */
> (これは0からN-1までの数を返そうとする)は乱数の質が低い。なぜな
> ら乱数発生器の多くで下位のビットは悲しいほどランダムでない
の方は、最近のコンパイラではそのようなことはないのでは、
という疑問をずっと持っていました。
やっとすっきりしました。ありがとうございました。

>TDaさん
お返事ありがとうございました。

>Cfaqですがかかれていたのがだいぶ前ということもありますので最近のrand()
>関数の実装は十分にランダムになっているということが考えられます。

実のところそういうことなんでしょうね。

>初学者に対してはわかりやすさを優先してもよいと思います.

はい、nが十分に小さいときに限り%演算子は使って行きたいと思います。





No.3018

Re:RAND_MAXを使うべきでしょうか
投稿者---かずま(2002/10/19 19:26:40)


> 一方、RAND_MAX + 1.0 で割って得られた 0.0以上 1.0未満の値を n 倍する
> やり方では、一様な乱数が期待できます。

誤解されると困るので、補足説明をしておきます。

n = 10000 のとき、RAND_MAX+1 で割る方法なら、0〜9999 の 10000個の乱数が
同じ確率で出るということではありません。
rand() が返す 0〜32767 の 32768通りについて、
 0 〜 3 は、0.000000〜0.915527 となるので、0 になるのは 4個。
 4 〜 6 は、1.220703〜1.831055 となるので、1 になるのは 3個。
 7 〜 9 は、2.136230〜2.746582 となるので、2 になるのは 3個。
10 〜13 は、3.051578〜3.967285 となるので、3 になるのは 4個。
というように、3個になるものと 4個になるものがあります。
すなわち、0 は、1 の 1.3333倍出やすいと言うことになります。
ただ、4個になるものと、3個になるものが均等に散らばっている
ことが % による方法と異なります。

% で剰余を求める方法では、0〜2767 は 4個、2768〜9999 は 3個と
いうように、前半と後半にはっきり分かれるということが問題で、
これではモンテカルロ法などに利用できないと言うことです。