主题：[原创]二分概率发生器
euc
[专家分：4310] 发布于 2005-10-02 03:06:00
#include <stdlib.h>
typedef enum {ERROR, TRUE} status;
/*
先介绍3个式子：
① return rand() & 1; //以1/2的概率返回TRUE
② return (rand()&1) & (rand()&1); //以1/4的概率返回TRUE
③ return (rand()&1) | (rand()&1); //以3/4的概率返回TRUE
*/
status BinProb (int n)
//以1/2的n次幂的概率返回TRUE
{
if (n < 1) return ERROR; /*此句不美观，可以删掉*/
if (n == 1) return rand() & 1;
return BinProb (n - 1) & BinProb (n - 1); /*wrong*/
}
BinProb是对2式的扩展。也可以加上3式构成更多的写法，大家可以做做。但我觉得rand()对我这个应用太浪费了，能不能写一个随机产生0和1的程序，我有一个设想就是提取字节中的位？这样的小程序挺有趣。
想知道怎么实现真正的概率发生器吗？
参考：
http://www.programfan.com/blog/article.asp?id=3860
http://www.programfan.com/blog/article.asp?id=3890
http://www.programfan.com/club/showbbs.asp?id=84567
回复列表 （共3个回复）
沙发
euc [专家分：4310] 发布于 2005-10-01 22:44:00
再总结一下：
几种概率发生算法
return rand () & 1; //求1/2概率
return (rand () & 1) & (rand () & 1); //求1/4概率
return (rand () & 1) | (rand () & 1); //求3/4概率
return rand () % n == 0; //求1/n的概率,n∈Z
return m >= rand () % n + 1; //求m/n的概率,m,n ∈ Z
status prob (double p)
/*发生任意精度概率*/
{
double t;
if (p < 1.0 / RAND_MAX)
return p * RAND_MAX >= rand ();
t = sqrt (p);
return prob (t) && prob (t);
}
status binprob_bit (int n)
/*发生1/2的n次幂的概率，位算法*/
{
int i, wd;
status tag = 1;
for (i = 0; i < n; ++i) {
if (i % n == 0) wd = rand ();
tag &= wd & 1;
wd >>= 1;
}
return tag;
}
status BinProb (int n)
//以1/2的n次幂的概率返回TRUE， 递归算法
{
if (n < 1) return ERROR; /*此句不美观，可以删掉*/
if (n == 1) return rand() & 1;
return BinProb (n - 1) & BinProb (n - 1); /*wrong*/
}
板凳
euc [专家分：4310] 发布于 2005-10-02 03:06:00
晚上没事编写了一个测试小例，结果大出意料。
int main (void)
{
int i, j, s;
time_t t0, t1;
float av = 0.0;
randomize ();
t0 = clock ();
for (j = 0; j < 1000; ++j) {
for (i = s = 0; i < 1024; ++i)
s += binprob_bit (10); /*or binprob()*/
av += s * 1.0 / 1000;
}
t1 = clock ();
printf ("%f time %f .sec\n", av, (t1 - t0) / CLK_TCK);
getch ();
return 0;
}
首先发现binprob()写错了，我那个实际是返回0.5^(2^n)的概率；
修改后
status binprob (int n)
{
if (n == 1)
return rand () & 1;
return binprob (n - 1) & (rand () & 1);
}
然后跟binprob_bit对照测试，结果n到8就开始出问题了，递归不仅速度慢一倍而且精确度不好、不稳定，位移法却是一直很稳定的。
下面列出来比较：
binprob (1 ~ 10):
511.978851 time 0.164835 .sec
511.959137 time 0.054945 .sec
255.946747 time 0.219780 .sec
256.009796 time 0.219780 .sec
255.951477 time 0.219780 .sec
128.041946 time 0.329670 .sec
64.113037 time 0.439560 .sec
32.093998 time 0.494505 .sec
15.930998 time 0.604396 .sec
8.061000 time 0.659341 .sec
2.499999 time 0.824176 .sec
1.023995 time 0.879121 .sec
0.347999 time 0.989011 .sec
而binprob_bit (1 ~ 10):
511.942780 time 0.164835 .sec
255.931961 time 0.109890 .sec
127.969879 time 0.219780 .sec
128.081131 time 0.219780 .sec
63.950924 time 0.219780 .sec
32.038006 time 0.329670 .sec
15.981989 time 0.329670 .sec
8.059000 time 0.439560 .sec
4.071018 time 0.384615 .sec
4.088011 time 0.384615 .sec
2.084000 time 0.494505 .sec
1.051996 time 0.494505 .sec
最好的是prob()了，用prob (0.001)来测试，大约是
1.001995 time 0.164835 .sec
比位移法又快了一倍！但最多也只能精确到0.0001~0.001了
3 楼
rickone [专家分：15390] 发布于 2005-10-02 21:04:00
为什么要做二分概率发生器
我来回复
您所在位置：