rand関数について

[戻る]
はまち 2002/07/23(火) 07:44:40
////////////////////////////////////////////////////////////////////////////////
    
    開発環境 : Visual C++ 6.0 Service Pack 3
    動作環境 : Windows 98 Second Edition
    MFC使用 MDIベース

////////////////////////////////////////////////////////////////////////////////

rand()%10は
0〜9
までの擬似乱数を返すと思います。同様に、rand()%30000とすれば、
0〜29999
までの擬似乱数を返すと思います。今までは、意識してなかったのですが、
rand()が0から32767(RAND_MAX)までの数字を返すのだとしたら、rand()%30000だと
0〜2767
までの数字は
2768〜29999
までの数字よりも、2倍発生しやすいような気がするのですが、そうなのでしょうか。
rand()%10の場合なら、それぞれの数字の出る数字と確率の関係は

                 実際に出る数字             個数    確率
0    10    20    -    32750    32760    3277    1/3277
1    11    21    -    32751    32761    3277    1/3277
2    12    22    -    32752    32762    3277    1/3277
3    13    23    -    32753    32763    3277    1/3277
4    14    24    -    32754    32764    3277    1/3277
5    15    25    -    32755    32765    3277    1/3277
6    16    26    -    32756    32766    3277    1/3277
7    17    27    -    32757    32767    3277    1/3277
8    18    28    -    32758        3276    1/3276
9    19    29    -    32759        3276    1/3276

となって、0〜7と8〜9の数字の間にはそれほど差がないようなので、意識することもなかった
のですが、1/30000の確率である処理を行うような場合は、乱数の発生が一様でなくなって
しまう気がしました。
実は、このことを意識したのは、1/1000000の確率である処理を行いたいと思ったからです。
このように、RAND_MAXを超える確率でできるだけ一様な処理をするには、何かいい方法は
ないでしょうか。擬似乱数なので完全に一様なものは考えられないと思いますが、
どうしても、処理の過程でこのような1/1000000の処理が必要なので、できるだけ、それに
近い処理ができるだけでもかまわないので、何か教えていただきたいです。

よろしくお願いします。

はまち 2002/07/23(火) 07:51:40
すみません、表が崩れてしまいました。それぞれの数字と確率は次のようなものだと思います。

数字 確率
0    1/3277
1    1/3277
2    1/3277
3    1/3277
4    1/3277
5    1/3277
6    1/3277
7    1/3277
8    1/3276
9    1/3276

たいちう 2002/07/23(火) 09:15:58
疑似乱数であることに目をつぶるなら、
0〜999までの数字を等しい確率で返す関数は作れます。
これを2回呼び出し、2回とも0だった場合が1/1,000,000でしょう。

int func() //(動作確認なし)
{
    int r;    
    do {    
        r = rand();
    } while (r >= 32000);
    return r % 1000;    
}

1/1,000,000以外の確率、特に中途半端な数字が必要なら、
i = func() * 1000 + func(); として、
i = 0 〜 999,999 までの数字を取るので、
i >= 123,456 のときに、i を再計算することにすると
i = 0 〜 123,455 までとなり、1 / 123,456 が得られます。


#私の感覚では疑似乱数はあてになりません。
#モンテカルロ法でどんなに頑張ったって円周率の桁は上がらないでしょう。
#以下の使い方で少しましになるようですが。

http://www.catnet.ne.jp/kouno/c_faq/c13.html#0    13.16  13.18

kazuma 2002/07/23(火) 13:13:10
こんなものがあります。
http://www.math.keio.ac.jp/~matumoto/mt.html

くたくた 2002/07/24(水) 01:04:25
>0〜2767までの数字は2768〜29999までの数字よりも、
>2倍発生しやすいような気がするのですが、そうなのでしょうか。
そうです。但し2倍ではありません。詳細は たいちうさんが示してくれたURLか、
線形合同法 というキーワードを使って 検索エンジンで調べてみて下さい。

>1/1000000の処理が必要なので、できるだけ、それに
>近い処理ができるだけでもかまわないので、何か教えていただきたいです。
if( !((rand()>>5)%1000) && !((rand()>>5)%1000) ){
   // 1/10000000の処理
}
こんな感じでできるのではないでしょうか。

rand()を使わずに自前で乱数生成アルゴリズムを用意する方法もあります。
サイト検索するとゴロゴロひっかかりますよ。

はまち 2002/07/24(水) 22:49:52
[[解決]]
たいちうさん、kazumaさん、くたくたさん、お返事ありがとうございました。
みなさんのお返事にとても驚くばかりです。たいちうさんのと、くたくたさんのは、
とてもシンプルなのでいいですね。今作っているプログラムにもすぐに取り込めそうで、
助かります。とくに、たいちうさんの後半に書いてある方法なら、任意の確率も出せるので、
とても上手に感じます。(きっと、くたくたさんのもできるのだと思うのですが、これは
きっと、シフト演算と言うものでしょうか。僕は、シフト演算はやったことがなく、
今、解読しているところです)

ですが、みなさんの書込みや、サイトを見る限りだと、やはり、randが返す擬似乱数の振る舞
いに疑問が出てきました。ちゃんとしたことをやるなら、くたくたさんが言うように、自分で
用意するか、kazumaさんのサイトのを使ってみるか、などをやらなきゃいけないように
感じます。特にkazumaさんのは、論文で扱っている分、信頼がもてそうです。

たいちう 2002/07/25(木) 14:35:22
くたくたさま

> if( !((rand()>>5)%1000) && !((rand()>>5)%1000) ){
>    // 1/10000000の処理
> }
> こんな感じでできるのではないでしょうか。

>    // 1/10000000の処理
これは、「1/1000000の処理」の書き間違いでしょうが、

これだとおよそ1/250,000の確率になりませんか?
私の勘違いの場合は、お手数ですがご指摘下さい。

【理由】
(rand()>>5) は、0〜1023までの数値を取る。
1000で割り切れるのは0と1000の2通りなので、2/1024。
(2/1024)*(2/1024)=1/262144。

たいちう 2002/07/25(木) 15:31:29
ついでに実験しました。
私のやり方も気休めに過ぎないことがよくわかりました。

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

int func()
{
    int r;    
    do {    
        r = rand();
    } while (r >= 32000);
    return r % 1000;    
}

int main()
{
    __int64 n_try = 0, n_hit = 0, n_hit2 = 0;

    srand((unsigned int)time(NULL));
    while (1) {
        n_try++;
        if ( !((rand()>>5)%1000) && !((rand()>>5)%1000) )
            n_hit++;
        if (!func() && !func())
            n_hit2++;
        if (n_try % 10000 == 0) 
        printf("%I64d  :  1/%.3lf   1/%.3lf\n", n_try,
               (double)n_try / (double)n_hit,
               (double)n_try / (double)n_hit2);
    }

    return 0;
}

くたくた 2002/07/25(木) 18:45:45
>これは、「1/1000000の処理」の書き間違いでしょうが、
そうです。失礼致しました。

>これだとおよそ1/250,000の確率になりませんか?
ご指摘が無ければ、危うく素通りするところでした。ありがとうございます。

繰り返し周期の長い上位ビットを採用しようと、log2(32768)-log2(1024)ビット分
シフトしたのですが、それが試行回数減少になる事をうっかり忘れていました。

普通に !(rand()%1000) とすれば、理屈、実測値(ヒストグラムから分布状態を評価)
から 1/1000 を取得できました。

はまちさんがこれを見てくれていればいいのですが...

はまち 2002/07/27(土) 01:07:47
とんでもないです、くたくたさん、お返事ありがとうございます。

あの後、紹介されたサイトや書籍などを読むことで、だいぶ処理の意味がわかってきました。
たいちうさんの紹介されたサイトなでも書かれて合ったのですが、下位ビットはランダムさは
あまりよくないのですね。そういう意味でくたくたさんのはとても上手だと思ったのですが、
残念です。
 僕も、たいちうさんのを参考に、if (!func() && !func())の処理をやってみたのですが、
1800000回の処理でも、まだ、一回目の処理が行われないようでした。
 サイトをあっちこっち、回った感じだと、kazumaさんの紹介していた、MTがいくつか見つか
り、
このアルゴリズムのすばらしさを感じました。とりあえずは、今回は、
if (!func() && !func())の処理で行って、MTを少しずつ勉強していこうと思います。

古いスレッドには追加発言できません。