C 语言随机数生成器的实现分析

本文是为了记录和澄清一个由来已久的关于C语言随机数生成器的误解。

目前所看到的所有公开的关于C随机数生成器的中文资料,都提到经典的线性同余法( LCG, linear congruential generator),并认为是默认的实现方法。这个说法并不准确。以GCC为例,GLIBC的确实现了线性同余法,但是实现的代码块分支在日常使用中不会执行到,线性同余法为C语言默认随机数生成器的说法已过时。

本文将以GLIBC源代码为例,结合掌握的文档,做一回搬运工,总结描述一下GLIBC中随机数生成器的实现。

线性同余法

线性同余法,LCG(linear congruential generator),是经典的伪随机数产生器算法,速度快,容易理解实现。 LCG 算法数学上基于公式:

X(n+1) = (a * X(n) + c) % m

其中,各系数为:模m, 系数a, 0 < a < m,增量c, 0 <= c < m,原始值(种子) 0 <= X(0) < m 。其中参数c, m, a比较敏感,或者说直接影响了伪随机数产生的质量。

GLIBC中对LCG的实现,取a = 1103515245, c = 12345, m = 134217728,即

X(n+1) = (1103515245 * X(n) + 12345) & 2147483647

由于LCG计算简单,极省内存,很适合内存和计算资源比较紧张的嵌入式环境。但LCG有一个严重的缺陷,即产生的伪随机数强依赖于上一次生成的随机数,且重复周期等于随机范围,不能用于随机数要求高的场合。

原因是单状态生成器在每次rand()调用时不会生成完全的伪随机数,实际做的是以伪随机的顺序遍历(0~2^31)范围内的数。意味着当获取到一个为伪随机数时,在当前周期内不会再获取到同一个数,只有在经过2^31次rand()调用之后,才会获取这个数(而且只会获取到这个数)。

线性累加反馈法

线性累加反馈法,即LAFM(linear additive feedback method),以下是GLIBC使用的线性累加反馈法的流程描述。其中,2147483647 = 2^31 – 1,4294967296 = 2^32. 所有变量都是整数。 对于给定的种子常量s, 初始化序列r0…r33通过以下步骤计算:

  1. r(0) = s
  2. r(i) = (16807 * r(i-1) ) % 2147483647 (i = 1…30)
  3. r(i) = r(i-31) (i = 31…33)

注意数乘16807的结果应该由足够大的整数类型存储,避免取模操作之前发生值溢出。r(i-1)在乘法操作已经是32位整数,r(i)计算结果确保是0到2147483646之间的正整数, 即使r(i-1)为负数。

从r34开始的伪随机序列,通过以下的线性反馈循环来计算:

4. r(i) = (r(i-3) + r(i-31)) % 4294967296 (i ≥ 34)

忽略掉r0…r343序列,rand()函数输出的伪随机数o(i)为:

5. o(i) = r(i+344) >> 1

r(i+344)的个位数字移除,生成31位随机数o(i)。

以下为模拟步骤1~4的代码:

GLIBC的实现

GLIBC实现了以上两种算法。LAFM生成器标记为 TYPE1TYPE2TYPE_3 和 TYPE4 类型,LCG 生成器标记为 TYPE0。相比LCG,LAFM生成器预先生成有很多初始状态,消除了LCG生成器的周期性遍历的属性,在同一个周期内,可以多次获取到相同的随机数。

为了提高随机数生成的时间和空间效率,在计算伪随机序列时GLIBC使用指针指向包含前驱随机值的数组,写法与按上述公式步骤直译的方式有所不同。

具体使用哪个生成器依赖于初始状态集合,由initstate()函数生成:

总结

LCG生成器在状态数组(buf->state)长度为8字节时才会使用。 状态数组长度更大时则会启用LAFM生成器。通常在使用rand()方法时,会使用srand()设置种子常量,这时状态数组默认就是128字节, 所以实际会启用LAFM生成器。

最后,以上分析如果有偏差,很可能是作者对资料或代码的理解问题,欢迎即时反馈。

参考资料:

  1. 纯线性同余随机数生成器介绍
    http://www.cnblogs.com/xkfz007/archive/2012/03/27/2420154.html
  2. random/initstate源代码
    https://github.com/lattera/glibc/blob/master/stdlib/random_r.c
  3. glibc rand function implementation
    http://stackoverflow.com/questions/18634079/glibc-rand-function-implementation
  4. The GLIBC random number generator
    http://www.mscs.dal.ca/~selinger/random/
1 2 收藏 1 评论

关于作者:卢亮

精益求精的技术员 个人主页 · 我的文章 · 5 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部