这篇帖子源于群里的一个提问:
为什么srand((unsigned int)time())的种子要设置成unsigned?
最直接的回答就是因为在头文件里srand的函数定义里规定了参数类型是unsigned int吧,于是就去翻了一下glibc的源码。
Warnning: 这是一篇偏技术的文章,会涉及比较多的代码!
首先glibc的源码可以在这里拿到。
srand()是在stdlib库里的,所以先看stdlib/stdlib.h这个文件,在451~456行的地方(不同版本的库可能会不一样)可以找到srand()/rand()的定义:
/* Return a random integer between 0 and RAND_MAX inclusive. */
extern int rand (void) __THROW;
/* Seed the random number generator with the given number. */
extern void srand (unsigned int __seed) __THROW;
从定义就可以直接看出srand()传进去的seed是规定unsigned int类型的了。
然后找一下这两个函数的实现,发现没有找到,然后在stdlib.h的395~405行看到这样的一段东西:
/* These are the functions that actually do things. The `random', `srandom',
`initstate' and `setstate' functions are those from BSD Unices.
The `rand' and `srand' functions are required by the ANSI standard.
We provide both interfaces to the same random number generator. */
/* Return a random long integer between 0 and RAND_MAX inclusive. */
extern long int random (void) __THROW;
/* Seed the random number generator with the given number. */
extern void srandom (unsigned int __seed) __THROW;
大概意思是srand/rand是假的,srandom/random才是真正干事情的。用gdb跑了一下,发现真的是这样(图片大概意思是在call了srand函数后,马上就有一条jmp指令跳转到srandom函数了,rand函数也类似):
在stdlib/random.c里面可以找到函数的实现:
void __srandom (unsigned int x)
{
__libc_lock_lock (lock);
(void) __srandom_r (x, &unsafe_state);
__libc_lock_unlock (lock);
}
函数里面用到了锁,所以有用到多线程的怀疑(?),真正执行的是一个叫 __srandom_r 的递归函数,在文件stdlib/random_r.c里面可以找到(前方高能):
/* Initialize the random number generator based on the given seed. If the
type is the trivial no-state-information type, just remember the seed.
Otherwise, initializes state[] based on the given "seed" via a linear
congruential generator. Then, the pointers are set to known locations
that are exactly rand_sep places apart. Lastly, it cycles the state
information a given number of times to get rid of any initial dependencies
introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
for default usage relies on values produced by this routine. */
int __srandom_r (unsigned int seed, struct random_data *buf)
{
int type;
int32_t *state;
long int i;
int32_t word;
int32_t *dst;
int kc;
if (buf == NULL)
goto fail;
type = buf->rand_type;
if ((unsigned int) type >= MAX_TYPES)
goto fail;
state = buf->state;
/* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */
if (seed == 0)
seed = 1;
state[0] = seed;
if (type == TYPE_0)
goto done;
dst = state;
word = seed;
kc = buf->rand_deg;
for (i = 1; i < kc; ++i)
{
/* This does:
state[i] = (16807 * state[i - 1]) % 2147483647;
but avoids overflowing 31 bits. */
long int hi = word / 127773;
long int lo = word % 127773;
word = 16807 * lo - 2836 * hi;
if (word < 0)
word += 2147483647;
*++dst = word;
}
buf->fptr = &state[buf->rand_sep];
buf->rptr = &state[0];
kc *= 10;
while (--kc >= 0)
{
int32_t discard;
(void) __random_r (buf, &discard);
}
done:
return 0;
fail:
return -1;
}
首先,这个函数的作用是通过一个随机数种子生成一串随机数,存到buf->state(通过参数传入,在函数中是局部变量state)中。这一串数(state)的第一个为传入的种子(seed)。比较有意思的是seed是不能为0的,如果是0的话会强行变成1:
/* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */
if (seed == 0)
seed = 1;
可以用一下的一段代码进行一下测试:
/* test.c */
#include <stdlib.h>
#include <stdio.h>
void test(unsigned int seed){
srand(seed);
for(int i=0;i<10;i++){printf("%d ",rand()); }
printf("\n");
}
int main(){
test(0);
test(1);
return 0;
}
至于为什么不能是0可以接着往下看,函数主要作用的是这个for循环:
for (i = 1; i < kc; ++i)
{
/* This does:
state[i] = (16807 * state[i - 1]) % 2147483647;
but avoids overflowing 31 bits. */
long int hi = word / 127773;
long int lo = word % 127773;
word = 16807 * lo - 2836 * hi;
if (word < 0)
word += 2147483647;
*++dst = word;
}
如果seed是0的话,整个随机数序列就都是0了。这个循环做的其实就是一个递归式的运算
state[i] = (16807 * state[i - 1]) % 2147483647
但是就拆分成了几行代码(运算结果应该是一样的,但是却拆分成hi和lo两个部分计算后再合成word),估计就是考虑到提升速度的方面的:一个猜想是取余运算其实是用除法来做的,当数比较大的时候会花费比较多的时间,所以就拆分成两个较小的数来进行运算;另一个猜想是因为在汇编层面来看,进行除法运算后会产生两个结果,商和余数,分别放在两个不同的寄存器,所以回到C的层面看,做除法的话就是拿商的结果,做取余的话就是拿余数的结果,所以word / 127773和word % 127773其实只用进行一次除法运算就可以同时得到hi和lo的结果了。
由srand的实现可以看出C语言的随机数是伪随机数,只要种子确定了,根据上面的递归式生成的随机数序列就是确定的了。
对比一下C++11的random,翻了一下C++11的源码(看不懂- -,但是发现了/dev/urandom这个东西),发现C++11是通过随机熵来实现随机数的,(估计会比递归式的更好?)