伪随机数生成算法及性能检验
伪随机数生成算法及性能检验
电子科技大学 数学科学学院 **
摘要： 摘要：通过以系统时间为种子，使用线性同余和平方取中的方法生成伪随机数数 列，并以图像和统计数据的方式对算法进行检验。 关键字： 关键字：伪随机数 C/C++ 线性同余 平方取中 引言：在一些问题中，比如计算机仿真和模拟、密码学等应用中，需要产生一个 引言： 随机数数列来解决问题。随机数数列分为真随机数数列和伪随机数数列。真随机 数数列是完全不可预测的，可以通过放射性衰变、电子设备的热噪音、宇宙射线 的触发时间等物理过程得到，但无法通过单纯的软件方式获得；伪随机数数列是 可预测的，严格意义上不具有随机性质，通常用数学公式的方法获得。由于很多 应用当中对“随机”数列的要求并不十分严格，而且伪随机数的产生较真随机数 更为廉价、高效，所以在大多数情况下只要产生统计分布较好的伪随机数数列就 能够满足应用要求。早期的伪随机数生成算法以平方取中法为主，现在则以线性 同余法为主要方式。本文会就两种方式分别给出实例，并以数据统计和图形化的 方式对伪随机数生成算法的性能进行检验。
正文： 正文： 1.种子 种子 正如数列需要有首项，产生伪随机数需要一个初值用来计算整个序列，这个 初值被称为“种子” 。种子可以是一个固定的值，也可以是根据当前系统状态确 定的值。C 语言用来产生伪随机数的库函数 rand()的种子是固定的值，因此每次 调用该函数产生的随机数数列都是相同的。所以为了获得随机性更好的数列，种 子应为一个变量， 该变量可以与当前系统时间、 用户对键盘或鼠标操作情况***** 有关。本文将根据系统时间获得种子。C 代码如下： //编译环境：Code::Blocks 10.05 #include
time_t t; time(&t); struct tm *local; local=localtime(&t); local->tm_mon++; ssecond=(long)local->tm_sec*100+local->tm_sec+36923; nowtime=local->tm_sec + local->tm_min*100 + local->tm_hour*10000 + local->tm_mday*1000000 + local->tm_mon*100000000; return nowtime; } 在调用伪随机数生成函数之前通过 seed=gettime();语句就完成了种子的初始 化。
2.平方取中法（Middle-square method ） 平方取中法（ 平方取中法 平方取中法是由冯·诺依曼在 1946 年提出的，其基本思想为：将数列中的 第 ai 项（假设其有 m 位）平方，取得到的 2m 位数（若不足 2m 位，在最高位前 补 0）中间部分的 m 位数字，作为 ai 的下一项 ai +1 ，由此产生一个伪随机数数列。 以公式描述，即：
xi +1 = [10
? m 2
xi2 ](mod10 m )
平方取中法计算较快， 但在实际应用
时会发现该方法容易产生周期性明显的 数列，而且在某些情况下计算到一定步骤后始终产生相同的数甚至是零，或者产 生的数字位数越来越小直至始终产生零。 所以用平方取中法产生伪随机数数列时 不能单纯使用公式，应该在计算过程中认为加入更多变化因素，比如根据前一个 数的奇偶性进行不同的运算， 如果产生的数字位数减少时通过另一种运算使其恢 复成 m 位。 经过若干次尝试，本文作者找到了一种性能较好的改进后的平方取中算法，
C 代码如下： //编译环境：Code::Blocks 10.05 //生成的数字范围为[0,LENGTH-1] long intlen(long in) //整数 in 的长度 { long count=0; while(in!=0) { in/=10; count++;
} return count; } long power_10(long in) //10 的 in 次幂 { long i,out=1; for(i=0;i
95 65 79 98 53 55 27 52 57 89
97 4 1 60 15 54 86 89 21 32 3 6
25 42 62 56 54 46 13 33 77 44 4 1
8 76 97 53 67 24 81 7 90 33
重复数字的个数情况为： 重复次数 数字个数
该算法在连续计算 100 次时取到了 0~99 之间的 65 个不同的数。 为了直观的观察该算法产生随机数的均匀性和随机性，将以图形的方式展 示：
（1）LENGTH=500，以连续产生的两个数字作为平面上点的横坐标与纵坐 ） 标，计算 2000 次。
图1
（2）LENGTH=500，以产生的数字作为数轴上点的坐标（下方） ） ，计算 500 次。
图2
（3）LENGTH=500，以计算的次数为横坐标、产生的数字为纵坐标，绘制 ） 直方图，计算 200 次。
图3
（绘图使用软件：Microsoft Visual Studio 2010 - Visual C++ 2010）
从数据统计和所绘图形来看，该算法有较好的均匀性和随机性。 3.线性同余法（LCG） 线性同余法（ 线性同余法 ） 线性同余方法是目前应用广泛的伪随机数生成算法， 其基本思想是通过对前 一个数进行线性运算并取模从而得到下一个数。 以公式描述，即： ai +1 = (ai × b + c)(mod m) 其中 b 称为乘数， c 称为增量， m 称为模数。 b ， c ， m 均为常数。 乘数、增量和模数的选取可以多种多样，只要保证产生的随机数有较好的均 匀性和随机性即可。 线性同余法的最大周期是
m ，但一般情况下会小于 m 。要使周期达到最大， 应该满足以下条件： (1) c 和 m 互质； (2) m 的所有质因子的积能整除 b ? 1 ； (3) 若 m 是 4 的倍数，则 b ? 1 也是； (4) b ， c ， a0 （初值，一般即种子）都比 m 小； (5) b ， c 是正整数。 在 C 和 VC 中都定义有用于产生伪随机数的库函数 rand()，而且都是利用线 性同余法产生伪随机数。 在 C 中的 rand()函数定义如下：
#define RANDOM_MAX 0x7FFFFFFF static long do_rand(unsigned long *value) { long quotient, remainder, t; quotient = *value / 127773L; remainder = *value % 127773L; t = 16807L * remainder - 2836L * quotient; if (t <= 0) t += 0x7FFFFFFFL; return ((*value = t) % ((unsigned long)RANDOM_MAX + 1)); } static unsigned long next = 1; int rand(void) {
return do_rand(&next); } void srand(unsigned int seed) { next = seed; } 在 VC 中 rand()函数定义如下：
//赋初值为种子
int __cdecl rand (void) { return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff); } 文献[1]中给出了一种适于 C 的 rand()函数： unsigned long next=1; int rand(void) { next=next*1103515245+12345; return (unsigned int)(next/65536)%32768; } void srand(unsigned int seed) { next=seed; } 为了提高库函数 rand()的性能，可以通过以下函数进行再次运算产生数列： int rrand(int n) { return 1+(int)(n*rand()/(RAND_MAX+1)); } 为了产生范围在[0,LENGTH-1]范围内的随机数，可使用以下函数： int random(void) { return rand()%LENGTH; } 以下为 LENGTH=100，利用 C 的 rand()库函数产生的随机数序列： 41 5 91 47 3 47 67 45 4 26 11 44 34 81 2 71 22 62 0 27 53 38 33 57 69 61 92 69 73 37 24 91 82 12 64 59 78 95 21 67 41 23 58 42 16 99 11 41 62 27 18 35 53 29 64 36 95 94 68 78
16 46 29 44
35 5 23 39
90 90 84 26
42 29 54 23 1 36
88 70 56 37
6 50 40 38 2 23
40 6 66 18
42 1 76 82 3 3
64 93 31 29 4 2
48 48 8 41
重复数字的个数情况为： 重复次数 数字个数
表2
该算法在连续计算100次时取到了0~99之间的64个不同的数。 为了直观的观察该算法产生随机数的均匀性和随机性，将以图形的方式展 示： （1）LENGTH=500，以连续产生的两个数字作为平面上点的横坐标与纵坐 ） 标，计算 2000 次。
图4
，计算500 （2）LENGTH=500，以产生的数字作为数轴上点的坐标（下方） ） 次。
图5
（3）LENGTH=500，以计算的次数为横坐标、产生的数字为纵坐标，绘制 ） 直方图，计算200次。
图6
从数据统计和所绘图形来看，该算法均匀性和随机性欠佳。为了提高算法的 均匀性，本文作者找到了一种均匀度非常好的线性同余算法。C 代码如下： //编译环境：Code::Blocks 10.05 //与平方取中法类似，种子根据当前系统时间获取 unsigned long nowtime; unsigned long seed; long gettime() //获得当前时间 { time_t t; time(&t); struct tm *local; local=localtime(&
t); local->tm_mon++; nowtime=local->tm_sec + local->tm_min*100 + local->tm_hour*10000 + local->tm_mday*1000000 + local->tm_mon*100000000; return nowtime; } #define LENGTH 100 //生成的数字范围为[0,LENGTH-1] int rand_xxty(void) //线性同余法 { seed=(unsigned long)(seed*101+81)%LENGTH; return (int)seed; } 以下为在5月18日12时51分27秒时刻以 LENGTH=100产生的伪随机数： 56 37 18 99 80 61 42 23 4 85 66 47 28 9 90 71 52 33 14 95 76 57 38 19 0 81 62 43 24 5 86 67 48 29 10 91 72 53 34 15 96 77 58 39 20 1 82 63 44 25 6 87 68 49 30 11 92 73 54 35
16 26 36 46
97 7 17 27
78 88 98 8
59 69 79 89 1 100
40 50 60 70
21 31 41 51 2 0
2 12 22 32
83 93 3 13 3 0
64 74 84 94 4 0
45 55 65 75
重复数字的个数情况为： 重复次数 数字个数
表3
该算法在连续计算100次时取到了0~99之间的所有的数。 为了直观的观察该算法产生随机数的均匀性和随机性，将以图形的方式展 示： LENGTH=500， 以连续产生的两个数字作为平面上点的横坐标与纵坐标， （1） ） 计算 2000 次。
图7
，计算 500 （2）LENGTH=500，以产生的数字作为数轴上点的坐标（下方） ） 次。
图8
（3）LENGTH=500，以计算的次数为横坐标、产生的数字为纵坐标，绘制 ） 直方图，计算 200 次。
从数据统计和所绘图形来看，该算法有极好的均匀性，但规律性较强，随机 性较差，适合应用在对均匀度要求较高，而对随机性要求不高的问题中。
结论： 结论： 通过数据统计和图形化的方法可以看出，以上给出的几种伪随机数生成算法 各有优势，而且性能都能达到一般应用的要求，具有一定的实用价值。 参考文献： 参考文献： 1.Brian W. Kernighan, Dennis M. Ritchie. C 程序设计语言（第二版）. 北京. 机械 工业出版社. 2011年； 2.Francis S Hill,Jr. Stephen M Kelley. 计算机图形学（OpenGL 版 第三版）.北京. 清华大学出版社.2009年。