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

柔光的暖阳◎ 2022-10-15 05:56 189阅读 0赞

原标题：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通过以下步骤计算：

r(0) = s

r(i) = (16807 \* r(i-1) ) % 2147483647 (i = 1…30)

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的代码：

r\[0\]=seed;

for(i=1;i<31;i++)\{

r\[i\]=(16807LL\*r\[i-1\])%2147483647;

if(r\[i\]<0)\{

r\[i\]+=2147483647;

for(i=31;i<34;i++)r\[i\]=r\[i-31\];

for(i=34;i<344;i++)r\[i\]=r\[i-31\]+r\[i-3\];

for(i=344;i

GLIBC 的实现

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

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

int\_\_random\_r(buf,result)

structrandom\_data \*buf;

int32\_t \*result;

int32\_t \*state;

if(buf==NULL||result==NULL)

gotofail;

state=buf->state;

if(buf->rand\_type==TYPE\_0)

int32\_tval=state\[0\];

val=((state\[0\]\*1103515245)+12345)&0x7fffffff;

state\[0\]=val;

\*result=val;

else

int32\_t \*fptr=buf->fptr;

int32\_t \*rptr=buf->rptr;

int32\_t \*end\_ptr=buf->end\_ptr;

int32\_tval;

val= \*fptr+= \*rptr;

/\* Chucking least random bit. \*/

\*result=(val>>1)&0x7fffffff;

\++fptr;

if(fptr>=end\_ptr)

fptr=state;

\++rptr;

else

\++rptr;

if(rptr>=end\_ptr)

rptr=state;

buf->fptr=fptr;

buf->rptr=rptr;

return0;

fail:

\_\_set\_errno(EINVAL);

return-1;

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

int\_\_initstate\_r(seed,arg\_state,n,buf)

unsignedintseed;

char\*arg\_state;

size\_tn;

structrandom\_data \*buf;

if(buf==NULL)

gotofail;

int32\_t \*old\_state=buf->state;

if(old\_state!=NULL)

intold\_type=buf->rand\_type;

if(old\_type==TYPE\_0)

old\_state\[-1\]=TYPE\_0;

else

old\_state\[-1\]=(MAX\_TYPES \*(buf->rptr-old\_state))+old\_type;

inttype;

if(n>=BREAK\_3)

type=n

elseif(n

if(n

gotofail;

type=TYPE\_0;

else

type=n

intdegree=random\_poly\_info.degrees\[type\];

intseparation=random\_poly\_info.seps\[type\];

buf->rand\_type=type;

buf->rand\_sep=separation;

buf->rand\_deg=degree;

int32\_t \*state= &((int32\_t \*)arg\_state)\[1\];/\* First location. \*/

/\* Must set END\_PTR before srandom. \*/

buf->end\_ptr= &state\[degree\];

buf->state=state;

\_\_srandom\_r(seed,buf);

state\[-1\]=TYPE\_0;

if(type!=TYPE\_0)

state\[-1\]=(buf->rptr-state)\*MAX\_TYPES+type;

return0;

fail:

\_\_set\_errno(EINVAL);

return-1;

总结

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

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

参考资料：

纯线性同余随机数生成器介绍

http://www.cnblogs.com/xkfz007/archive/2012/03/27/2420154.html

random/initstate源代码

https://github.com/lattera/glibc/blob/master/stdlib/random\_r.c

glibc rand function implementation

http://stackoverflow.com/questions/18634079/glibc-rand-function-implementation

The GLIBC random number generator

http://www.mscs.dal.ca/~selinger/random/

觉得本文有帮助？请分享给更多人

关注「CPP开发者」

看更多精选C/C++技术文章

责任编辑：

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

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【C语言编写随机数生成器】-经典C语言程序100例之十二

相关随机密码生成器

相关 c语言生成随机数(c语言生成随机数并排序)

相关 c 语言随机值的生成器,C 语言随机数生成器的实现分析

相关 c语言自定义随机种子,C++ 随机数与随机种子数的实例

相关 c语言非整形随机数生成,生成随机数（C语言，任意随机）

相关 C语言随机数

相关 C语言版RPG角色生成器

相关【C语言】模拟33选7的彩票生成器

相关 C语言——产生一个随机字符或者随机数