浅谈伪随机数的周期性

大学上C 语言课程的时候,我们就被教导计算机生成的随机数只能是伪随机数,并不是具有理论意义上的随机数,就我的理解,伪随机数可能指的是有周期性变化规律的随机数吧。

伪随机数的周期性

谈到周期性变化,想到了一个关于数学家和阿拉斯加一个赌场的故事,当时赌场有个赌博机使用了比较先进的计算机生成随机数,方法很简单,保存aN (a 的N 次方,a 和N 都是固定值,N 取的很大) 的结果,然后使用一个random 函数生成出不同值作为位置,再从aN 结果中对应的位置取出数字,这个方法破解难度就在于aN 计算复杂程度在当时能力很难有机器能够胜任,而一群数学家制造出专门计算乘方的机器,多次试验也还原了random 函数,进而百赌百赢。

既然伪随机数是具有周期性变化规律的,那么设计的伪随机数的周期越大固然越好(如果周期→无穷大,那么这个伪随机数也就越接近随机书了)。但并不是周期大的伪随机数就是好的伪随机数,还有每个随机数字的权重等性质。伪随机数随机性的理论也是很深的一个坑,有专著专门讨论了随机性。

上面赌博的周期不难看出不大于random 函数的周期乘以sizeof(aN)。

 

伪随机数周期的取舍

伪随机数字周期大小也要适合所使用的应用。如果应用中频繁的要生成随机数,那么就要考虑周期太小会不会满足所需要的随机性。随机性更好的随机数往往需要更大的计算量。

 

C++ 中生成伪随机数的方法

C++ 中没有random() ,只能使用rand() 和srand() 生成随机数,前者不需要生成种子,生成0-RAND_MAX 范围内数字,每次生成的随机序列一样,方便程序调试;后者需要生成种子,种子相同,生成的随机序列相同。常见生成随机数的方法有:

  1. 直接使用rand() ;
  2. 使用srand() ,种子由用户指定输入;
  3. 使用srand() ,种子取自当时时间;e.g.    srand( (unsigned)time( NULL ) );rand();
  4. 每次使用rand() 前都使用srand(),进一步随机化rand() 输出结果;
  5. 使用线性同余等方法实现满足自己需求的一个随机数生成器;

srand() 和rand() 使用起来非常简单,但用不好也会有些问题,下面是一个生成0-N 范围内的随机数的生成器,大家看看有什么问题:

   1: srand( seed );

   2: rand() % N;

随机数中种子的取舍也非常重要,这篇博文讲述了C++ 中如何使用内存的0040:006CH 时间地址作为种子的。

 

伪随机数生成方法

C++ 中的rand() 使用线性同余LCG(linear congruential generator)的方式生成随机数,简单而言线性同余使用下面方法生成0~MAX 之间随机数:

f(x)%MAX  (其中f() 函数是关于x 的线性函数)

x 即之前所说的种子,f(x) = anxn + an-1xn-1 + …… a2x2 + a1x + a0 就是一个关于x 的线性函数,其生成的随机数周期不大于f(xmax)。这里的周期和系数ai 的取值以及ai 与同余数 MAX 都有关系,一般取ai 与MAX 互素。

 

下面是在stackoverflow 上看到一则漫画,大体讲的就是,如果随机序列无穷大,也就无法判断这个随机序列是不是好的随机数序列。

Dilbert0001

浅谈伪随机数的周期性》上有6条评论

  1. 伪随机数并不是真正的随机数,由同样的种子算出的伪随机数一定相等,也就是说,伪随机数和种子是一一对应的关系,这就足见伪随机数不是随机产生的、事先不能确定数。

回复 yongchuan 取消回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据