伪随机数使用之误(一)

给定一个伪随机数生成器rand(),假定它已达到一个理想状态,即输出的值满足0到RAND_MAX上的均匀分布。

对于小于RAND_MAX的正整数n,如何通过rand()得到一个0到n之间的随机数?

常规方法是这样的:

result = rand()%(n+1);

事实上,得到的结果并非均匀分布。例如:当n=RAND_MAX*2/3时,result为0 — n/2中某个数的概率是其为n/2+1 — n中某个数的概率的两倍。(这是差距最大的一种情况)

应该使用这种方法:

do{

    result = rand();

}while( result > n );

但这种方法有个缺点:rand()的运算次数满足几何分布,故期望为:(RAND_MAX+1)/(n+1)。当n较小时,效率太低。

一种折中方案是:

do{

    result = rand();

}while( result >= (RAND_MAX+1)/(n+1)*(n+1) );

result = result%(n+1);

这种算法具有较好的效率,唯一的缺点是:在实际使用时,需考虑RAND_MAX+1是否会造成溢出。

我们的下一个问题是:

对于大于RAND_MAX的正整数n,如何通过rand()得到一个0到n之间的随机数?

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注