ランダムな実数x,y(0 <= x <= 1, 0 <= y <= 1)の出力

Question

ランダムな実数x,y(0 <= x <= 1, 0 <= y <= 1)を出力する以下のプログラムを実行したところ、

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

int main(void) {
	double x, y, d;
	srand((unsigned)time(NULL));
	x = (double)rand() / RAND_MAX;
	y = (double)rand() / RAND_MAX;
	d = x * x + y * y;
	printf("(%lf, %lf)\n", x, y);
}

次のようになった。

(x, y) = (0.755291, 0.182222)

(x, y) = (0.755307, 0.445297)

(x, y) = (0.755307, 0.445297)

(x, y) = (0.755315, 0.576835)

(x, y) = (0.755323, 0.708373)

(x, y) = (0.755988, 0.889085)

(x, y) = (0.755996, 0.020622)

(x, y) = (0.756004, 0.152160)

(x, y) = (0.756011, 0.283698)

(x, y) = (0.756019, 0.415236)

x、y共にランダムになっているが、xの値は0.75から始まる実数しか出力されていない。なぜこのような結果になるのかわからない。
教えてください。

(補足)
プログラム全体を10回ほど数秒おきに実行した結果です。

Answer 1

C の標準ライブラリが提供する rand の性質について言語仕様では詳細が決められていないので各処理系 (に付随するライブラリ) によるのですが、伝統的に線形合同法が用いられることが多いです。

X[n+1] = (A*X[n]+B) mod M

一部の環境では定義通りの数式で処理した後に下位バイトを捨てる処理が入っています。 これによって乱数の最初の値はシードの差の影響が大幅に小さくなることになり、十秒ごと程度ではかなり近い値が出力されるわけです。

具体的には、 Windows の MSVCRT 内の rand は以下に相当する実装になっていました。

#define RAND_MAX  0x7fff

static unsigned long seed = 1;

int rand(void) {
    seed = seed * 214013 + 2531011;
    return (seed>>16) & RAND_MAX;
}

void srand(unsigned int x) {
    seed = x;
}

線形合同法では下位バイトの数学的性質が悪いことが知られているのでそれに対応するために下位バイトを捨てているのでしょう。

初期値の影響の強さを避けるには最初のほうの百個くらいは捨てるといった工夫が知られています。

---

その他、線形合同法は前後を組にして扱う (多次元空間にプロットする) と露骨な規則性が見える場合があることが知られており、色々と問題もあります。 乱数列の数学的性質というのはなかなか複雑な事情があるので用途に照らして問題がないかよく検証する必要があります。

Comments

[reha]

回答ありがとうございます。参考にします。

Answer 2

RAND_MAXが32767なC言語処理系で、srand((unsigned)time(NULL));でシードを設定すると、(秒が変わっても時刻が近いと)最初のrand()の値がよく似た値になってしまうようだ。

実際には、srandとrandを毎回セットで実行するような間違ったコードを書かなければ、それほど問題にはならない。あるいは、最初の(あるいは数回の)randの値を捨ててから実際に使う値を取り出せばいい。

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

int main(void)
{
    int x;
    printf("RAND_MAX: %d\n", RAND_MAX);
    while (1) {
        srand(time(NULL));
        printf("%d\n", rand());
        sleep(2);
    }
    return 0;
}

RAND_MAX: 32767
1945
1952
1958
1965
1971
1978
1984
1991
1997
2004
2010
2017
2024
2030

Answer 3

time(NULL)はある時刻(大抵は1970年1月1日午前0時)からの経過秒数を返します。
連続して実行した場合、srand()に渡される値はほとんどの場合下の数桁しか変化しません。
あなたの使用しているCコンパイラ付属のランタイム実装において
srand()にわたす値の下位の桁が、rand()の初回に返す値の上位の桁にあまり影響しないような乱数実装となっているのでしょう。

Answer 4

プログラム内に繰り返しはないので、このプログラム全体を何度も繰り返した場合ということでしょうか？

timeの返す値は秒単位なので、同じ秒の時に実行すると同じ値でsrandすることになり、同じ乱数が発生します。

対策としては、
・マイクロ秒単位の時刻を取得してそれを使う
・プロセスID等、実行ごとに異なる値を秒単位の時刻に足すなどして使う
など。

Comments

[reha]

回答ありがとうございます。プログラム全体を10回ほど数秒おきに実行した結果です。言葉足らずですみません。

[otn]

失礼。4つめ以降の出力を展開して見てませんでした。
そうすると、randサブルーチンの品質が良くないと言うことだと思います。
・別の乱数サブルーチンがあればそれを使う
・2つめは大丈夫そうなので、何回かrandを空呼び出してから使う
など。
回答に書いた方法も有効だと思います。PIDを使うなら足すのではなく掛ける方が良いかな。