登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

随机数折叠问题  

2009-12-22 19:07:54|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    rand是C/C+经常使用的伪随机数发生器。假如系统需要随机执行A、B、C三种情况,则可以采用如下代码:
const int type = rand() % 3;
switch(type) 
{
    case 0: A(); break; 
    case 1: B(); break; 
    case 2: C(); break; 
    default: assert(0); break; 
}
    一般应用中,我们是假设rand给的随机数是足够随机的,这里就姑且认为是随机的。一直以来,我都错误的认为 rand() % 3 和 rand() 给出结果的随机性是同等级的,实际上离0、1、2等概率还差的很远!

 
    随机数折叠问题——当随机数发生器的值域不能整除以截取的目标值域范围时,会导致目标概率不等的现象。
    可用下图形象表示:
   随机数折叠问题 - 秒大刀 - 秒大刀的城堡
    设:随机数发生器的值域为m,并且随机数发生器理想随机;截取的目标值域为n
    则:在n范围内每个数值理想的取值概率为:1/n
        取到折叠左端大值的概率为:m%n / n
        取到折叠右端小值的概率为:1 - (m%n / n)
        取到折叠左端大值时误差为:(n/m * ceil(m/n) - 1) * 100%
        取到折叠右端小值时误差为:(n/m * floor(m/n) - 1) * 100%
    由此可得出:在m%n == 0时,不存在随机数折叠问题;否则,当m/n越大时,由随机数折叠问题造成的误差越小。实际应用中,应该有意选择值域更大的随机数发生器。

 
    rand函数值域范围为[0, RAND_MAX],一般的定义中RAND_MAX为32767(0x7FFF),为一个unsigned word的最大值,不应该武断的看到rand返回值签名为int就以为rand返回的值域在整个int范围内。运用上面的公式,可知本文开始给出例子的误差为:3/32768 * ceil(32768/3) - 1 ≈ 0.00006;当n为32767时,rand() % 32767 中取到0的概率是其他值概率的两倍,杯具。


    如果对A、B、C执行概率要求不甚严格也无所谓,但如果对概率问题比较敏感(如游戏中的道具爆率控制),则需对该现象特别注意。下面的实例代码再次证实了随机数折叠问题的存在:
 #include <vector>
 #include <iostream>
 #include <cassert>
 #include <algorithm>
 using std::cout;
 using std::endl;
 void rand_test(int n, int times)
 {
     std::vector<int> data;
     data.resize(n);
     for(int i = 0; i < times; ++i)
     {
         ++data[rand() % n];
     }
     for(size_t i = 0; i < data.size(); i++)
     {
         cout << i << " - " << data[i] << "\t";
     }
     cout << "min - " << std::distance(data.begin(), std::min_element(data.begin(), data.end()));
     cout << endl; 
 }
 void main()
 {
     assert(RAND_MAX == 0x7FFF);
     // 这里的0x7FFF是确保你所使用的rand函数最大值是32767(可以取到)
     const int n = 3;
     rand_test(n, 0x000FFFFF);
     rand_test(n, 0x001FFFFF);
     rand_test(n, 0x002FFFFF);
     rand_test(n, 0x003FFFFF);
     rand_test(n, 0x004FFFFF);
     rand_test(n, 0x005FFFFF);
     rand_test(n, 0x006FFFFF);
     rand_test(n, 0x007FFFFF);
     rand_test(n, 0x008FFFFF);
     rand_test(n, 0x009FFFFF);
     rand_test(n, 0x00AFFFFF);
     rand_test(n, 0x00BFFFFF);
     rand_test(n, 0x00CFFFFF);
     rand_test(n, 0x00DFFFFF);
     rand_test(n, 0x00EFFFFF);
     rand_test(n, 0x00FFFFFF);
 }
     在VS2008 sp1平台下的输出结果为:
0 - 349742      1 - 350201      2 - 348632      min - 2
0 - 699104      1 - 698089      2 - 699958      min - 1
0 - 1046530     1 - 1050468     2 - 1048729     min - 0
0 - 1398442     1 - 1399490     2 - 1396371     min - 2
0 - 1748016     1 - 1748998     2 - 1745865     min - 2
0 - 2097960     1 - 2097308     2 - 2096187     min - 2
0 - 2446782     1 - 2447505     2 - 2445744     min - 2
0 - 2797492     1 - 2796220     2 - 2794895     min - 2
0 - 3145117     1 - 3147283     2 - 3144783     min - 2
0 - 3494002     1 - 3496022     2 - 3495735     min - 0
0 - 3844733     1 - 3845287     2 - 3844315     min - 2
0 - 4194914     1 - 4194537     2 - 4193460     min - 2
0 - 4545303     1 - 4541730     2 - 4544454     min - 1
0 - 4892986     1 - 4894462     2 - 4892615     min - 2
0 - 5244394     1 - 5243212     2 - 5241033     min - 2
0 - 5594917     1 - 5591010     2 - 5591288     min - 1
    其中0最少的出现2次,1最少的出现3次,2最少高达11次。因为随机数折叠的存在,使得rand()%3为2的概率明显的低于为0和1的概率。

结论:
    要对 rand() % n 保持足够的敏感度
    在随机敏感的环境下应该尽量选择随机值域比较大的随机数发生器

注:
    某些linux环境的RAND_MAX值为0x7FFFFFFF,在此平台下应用 rand() % n 可以保证在一般应用下足够精确。
    微软.net framework中的Random类是一个比较好的随机数实现,想看源码的话可以用.NET Reflector对.net类库进行反汇编。当前实现是基于 Donald E. Knuth 的减随机数生成器算法的。有关更多信息,请参见 D. E. Knuth.“The Art of Computer Programming, volume 2: Seminumerical Algorithms”。Addison-Wesley,Reading,MA,second edition,1981。


20100112

    ENT随机数质量测试算法:http://www.fourmilab.ch/random/

  评论这张
 
阅读(1257)| 评论(3)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018