关于随机数那点事

提起随机数，大家一定都不陌生。无论是在计算机科学领域，还是现实生活中，随机数的作用都不可小觑。 但随机数究竟是怎么一会事？它的作用是什么？它有事如何产生的？ 说实话这个概念比较虚，不是很好讲，笔者也只能~~随便水水~~尽力解释一下。能不能懂就不怪我了... 先预告一下，本文偏理论类。对于随机数算法并不会过多讲解。 （如果只想看实货的可以直接空降最后一个专题） # 随机数定义及其性质 想要讨论随机数，首先应该明确一下随机数的定义。毕竟这个东西比较虚，并不像算法那样明确。在各大网上也没有给出很好的定义。 那...就不死抠定义了。 随机数一般来说符合下面这几个性质。 1. 它产生时后面那个数与前面的毫无关系 1. 给定样本的一部分和随机算法，无法推出样本的剩余部分 1. 其随机样本不可重现 本文的大部分论述都会建立在以上三条的基础上。 continue-> # 伪随机数 伪随机数，也就是我们c++中常用的随机数。为什么说它是“伪”随机呢？其实只要稍微详细的了解过c++ rand函数的人应该都能懂得这一点。 我们看回到前面的三条总结，就能明白c++的随机数某种意义上来说只满足那三条中的第一条。 因为c++的rand函数实际上只是根据你提供的种子计算出来的一组循环节很长的数。只要两次提供的种子是一样的，那么rand函数提供的随机数也是一样的。 可能有好奇的小伙伴就要问了，你说循环节很长，那到底长到什么程度呢？ 为解决这个问题，笔者做了一个有趣的小测试。 ### 有趣的小测试 ： （ 根据网上的资料，rand函数循环节一般是2^32或2^64 ） ``` #include<iostream> #include<stdlib.h> #define MAXN 4294967296 using namespace std ; int a ; long long countn ; int main ( ) { countn = 0 ; for( int i = 1 ; i <= 6 ; i ++ ){ a = rand ( ) ; cout << a << endl ; } for( int i = 1 ; i <= 16 ; i ++ ){ countn ++ ; cout << countn << " / 16 "<< endl ; // 用来跟踪进度的 for( int i = 6 ; i <= MAXN / 16 ; i ++ ){ a = rand ( ) ; } } for( int i = 1 ; i <= 6 ; i ++ ){ a = rand ( ) ; cout << a << endl ; } return 0 ; } ``` （ 其中4294967296是2的32次方 ） 这个程序你们可以自己拷到电脑上去试，不会把电脑弄崩溃的。 最后的输出结果是：  很遗憾，经过2的32次方次调用，rand函数仍然没出现循环... （ 你们别问我为什么不去测试2^64次方，要测自己测，我没这个时间 ） 当然，笔者是不会那么容易死心的。通过网上查资料，我成功弄到了rand函数在linux系统下的实现： ``` static unsigned long next = 1; /* RAND_MAX assumed to be 32767 */ int myrand(void) { next = next * 1103515245 + 12345; return((unsigned)(next/65536) % 32768); } void mysrand(unsigned seed) { next = seed; } ``` （ 该代码摘自CSDN [原文链接](https://blog.csdn.net/Cashey1991/article/details/45042291)） 通过这个算法我们可以推知，rand函数的循环节应该是在32768（2的15次方）以内。 （ 所以我白测试了是吗 ） 做这些测试实际上就是想说，在计算机方面。目前来说，如果不借助外部帮助，是无法达到真随机的。 # 真随机数 讲完了伪随机，就该讲真随机了。 根据我们前面达成的共识，真随机数的产生一定会满足前面那三个标准。 为了防止你们往回翻，我特地拷了一份过来 1. 它产生时后面那个数与前面的毫无关系 1. 给定样本的一部分和随机算法，无法推出样本的剩余部分 1. 其随机样本不可重现 我们一条一条来分析看。 首先是第一条，产生时与前面的数毫无关系。那么就是说，真随机数的产生是一个完全独立的过程，与之前的任何状态无关。（ 这个应该不难理解 ）或者说，你如果要产生一个真随机数，那么你什么都不能利用，就用你的脑子瞎想一个就完事了。其实即使是瞎想也不能算作是真随机数，因为你的思想时时刻刻受着周围环境的影响，而真随机的产生是一个完全与世隔绝的。 然后是第二条... 等等！ 第二条，和第三条。 其实好像不用证明了。 因为只要第一条的情况,也就是完全与世隔绝存在。那么第二条和第三条也就自然而然地成立了。 那么经过了我的~~妖言惑众~~严谨推导。真随机数的性质也就浮出水面了。那么我就再总结一下： （ 我咋就那么喜欢总结 ） **真随机数是在一种广义真空的环境下自然产生，并且毫无规律的数字。同时这种产生是唯一不可重现的** 看到这里如果你还能理解的话，那说明~~我忽悠的够好~~你的悟性足够高。 还是稍微解释一下上面的一些用词，“广义的真空”指的是一种与外界环境相分隔的环境，如同太空一样，无论大气层中发生了什么事，由于太空中与地球是相对隔绝的，所以都几乎影响不到太空。“自然”这个词想表达的是真随机数产生的无原因与无目的性，所以就用了这个词，大家可以用语文思维体会一下。 笔者友情提示：不要把这篇文章当做是理性论证文看，用感性思维去抽象理解会更好些。 continue-> # 计算机的随机数 计算机随机数的产生，我在讲伪随机时已经~~烧过CPU~~做过介绍了，也就不多说。 你以为我会帮忙把前面的代码拷过来吗？想太多了，自己翻页去。 （ 本来想放点图可能可以增加可读性，但好像放不了什么... ） 这里我主要想讲的是关于计算机在没有外界帮助下为什么不能产生真随机数。 真随机数的产生应该是与之前的数是没有任何关联的（ 论证过 ），那么在计算机中想对应的就是产生随机数的函数应该不需要调用任何参数（ 因为一旦调用了的参数，那么这个随机数的产生就会与参数相关 ）那么对于计算机来说，如何不调用任何参数并且产生不同的数呢？ 这个...好像做不到。 这个换一个思维来解释好一点。因为计算机是一个绝对理智的存在，也就是说，计算机的一切行为都是可预测可推导的。而这恰恰违背了我们随机数标准中的第二条，即不可推断。对于计算机的任何程序，如果使用完全相同的参数来调用，它所输出的结果一定是完全一样的 农夫山泉不生产水，他们只是大自然的搬运工  计算机不生产数据，它只是数据的加工厂。  # 自然界的随机数 讲完计算的随机数~~感觉字数不够再水水~~，那就自然而然的讲到了自然随机数。 还记得我之前说过计算机在没有外界帮助下无法产生真随机数吗？这句话中的“外界帮助”实际上指的就是自然随机数。 自然随机是目前人类能够获得的最接近真随机数的方法。它通过接受外界中一些能够视为不可重现的信号来产生对应随机数。 这样说可能有点绕，举一个比较形象的例子。现在大多数软件所使用的随机数是通过当时调用随机函数的时间来作为随机数运算种子。（ 时间大概精确到毫秒 ）这样在函数调用完成时，它的样本——时间，已经产生了变化，并且这种变化是不可重现的。 当然你也可以说如果我们用一个规律的时间去不断调用随机函数，那么每次调用时它的时间流逝时相等的，我们可以一次算出下一个随机数。但这种方法也只是理论上可行，因为即使是同一个函数，它没调用所需的时间也是会有微小差距的，哪怕只是一个printf。 这种“不可重现”的时间不只是时间。温度（ 只要测量地足够细 ） 电脑运行时产生的微小的电波误差。或者是分子间的布朗运动，只要能够测量，都可以用来产生随机数。 这里我给“不可重现”打上了引号是因为所谓不可重现是建立人类目前手段不能达到的基础上的。你可以说一股水流流过你的面前是不可重现的，因为无论你怎么去重现，拿股水流永远会有微小的偏差。但如果有一天人类的科技足够发达，我们能够分析出水流的每一个分子的状态，没准还真能重现。 所以说不可重现其实只是人类目前无法重现。 随机数也是一样 或许真随机数永远不存在，所谓“真随机”只是人类还未发现其规律。 随机的定义是没有规律 而没有规律却不能被证明 只能说因为我们目前没有发现规律，所以它没有规律 对于规律的讨论，可能就要设计到哲学领域了。本文在此也就不多论述了，有兴趣的可以自己查阅一些哲学著作，自己思考。 在那之前，要多想。 （ 说一下笔者的观点吧，经供参考。我认为世界上是有真随机存在的，不要问我为什么，唯心主义不需要解释 ） # 随机数的应用 讲了这么多随机数的事，最后总该讲讲随机数的应用。 首先是用于检验程序。 估计这是大部分OIer的用法，拿一个随机数生成器去验证程序的速度,以及是否会RE（ 正确率是测不了的，毕竟自己手推答案比较慢 ）。 然后的话是某些算法的需要 被大家熟知的平衡树treap就是通过随机数权值来调整自身达到平衡的。然后的话，就是退火也需要随机数来不断调整当前解。另外使用到随机数的算法我在这里就不一一枚举了。 （ 感觉随机数好像也就这么点用，在密码学统计学中用的比较多 ） 本文到这里应该就 ~~水完~~ 结束了，当然，既然你好不容易看到了这里，我就给一个彩蛋吧（ 有点勉强 ）。 关于rand函数为什么是用1103515245和12345这两个数...你可以理解为玄学。 不过真是原因是用这两个数推算出来的的随机数分布相对平均。更符合伪随机数的特性。（ 这个我尽力用实验来论证，目前还在构思，也可能正在实验 ） # 如何生成优质随机数 讲了这么多概念内容，最后还是要塞一点实货。 ~~主要是管理员的要求~~ 当时管理员说希望我加一点生成优质随机数的方法。 我... 当时就是一个疑问 什么叫“优质”随机数 关于伪随机数，至今还没有一个统一的判断标准... 那我怎么讲啊！ 经过了三天三夜的深思熟虑。 终于自己给出了一个“优质随机数”的定义。 既然我们试用随机数是用来辅助算法的。那么针对不同的算法，能够将它的特点发挥的最好的随机数就是这个算法的优质随机数。 这样就好讲多了。 那我就用四个比较有代表性的算法来讲我们常见两种优质随机数。 ### 来回摆动式 这种随机数主要是针对退火算法之类的需要用随机数来修正答案的。 既然是修正答案，那么我们希望最好是来回摆动，一正一负的。 这种随机数的特点便是通过一部分人工处理，将原本的rand函数产生的随机数变成正负交替的。 ```cpp int f = 3000 ; int change = 0.999 ; // f和change是用来控制随机数幅度不断变小的 int con = -1 ; int g = 1 ; // 控制正负交替 int newrand ( ) { f *= change ; g *= con ; int tmp = f * g * rand ( ) ; return tmp ; } ``` 这种随机数的产生引入了退火的思路，当然，你也可以直接使用算法中现成的温度来控制。 ### 平均式 这种主要是用于平衡树treap的，特点就是在保证单个数随机的情况下在整体上保证分布比较平均。 实现原理也没什么好讲的，上代码就完事了。 ```cpp int p ; // 希望的分布位置 int newrand ( ) { int tmp = ( p + rand ( ) ) / 2 ; // 通过取于分布位置的平均数，是产生的数更加靠近希望分布 return tmp ; } ``` ### 多次调用不重复式 当然，如果有人真的需要非常接近真随机的数。也就是多次运行程序也不会出现相同的情况。那就需要用到一定的外部干扰了。 首先是clock函数，上文已经说过，一个程序在不断调用期间。每一次的运行时间都会有细小的变化。我们就可以利用好这个变化。每次调用完后都重置一次随机数种子。 还有一个可能大家都会忽视的方法。计算机本身的误差。众所周知，计算机在做浮点运算时是会产生精度损失的，那么我们也可以利用这个特点辅助clock调整种子（毕竟程序调用时间相同其实可能性也不小，毕竟clock只精确到s/1000）。 ```cpp int count ; int realrand ( ) { count ++ ; int t = clock ( ) + 1 ; // 使用当前时间 for ( int i = 1 ; i < 12121307 ; i ++ ) { // 降速（如果放到具体代码里面使用可以将此参数调低） t += rand ( ) ; } t += clock ( ) ; // 降速后扩大时间变化 t *= -1234 ; srand ( t * count + rand ( ) ) ; // 重置随机数种子 return rand ( ) ; } ``` 笔者经过大量实验，发现该函数前三个数出现重复几率相对会比较大（7~9%）建议从第四个开始使用。 上面的代码我并没用用精度损失来随机化，因为我发现同一个式子的进度损失值太小，以至于几乎不会发生什么改变，所以并没有使用。 ### 梅森旋转算法（MT19337） 这个是目前产生优质伪随机数的普遍算法 在C++11，python等多种语言中都有使用 讲起来有点长 我就放到了我的另外一篇博客中 [梅森~~螺旋~~算法](https://www.luogu.org/blog/muxii/ni-ke-neng-mei-ting-shuo-guo-di-mei-sen-xuan-zhuai-sui-ji-shuo-suan-fa) （@ =@） （ > o < ) 最后非常感谢你能有耐心读到这里。 感谢@[qbu666666](https://www.luogu.org/space/show?uid=157598)和@[dgklr](https://www.luogu.org/space/show?uid=157598)大佬对本文文字错误以及论述缺陷的指出。 大家都很强，可与之共勉。