glibc rand函数实现 [英] glibc rand function implementation
问题描述
我正在阅读 c标准库rand()函数实现带有glibc源代码. stdlib/random_r.c，第359行
I'm reading c standard library rand() function implementation with glibc source code. stdlib/random_r.c, line 359
int
__random_r (buf, result)
struct random_data *buf;
int32_t *result;
{
int32_t *state;
if (buf == NULL || result == NULL)
goto fail;
state = buf->state;
if (buf->rand_type == TYPE_0)
{
int32_t val = 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_t val;
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;
}
return 0;
fail:
__set_errno (EINVAL);
return -1;
}
我不明白(buf->rand_type != TYPE_0)时random_r如何生成随机数，请问有人解释吗?谢谢.
I don't understand how random_r generate random number when (buf->rand_type != TYPE_0), anyone please explain? Thanks.
推荐答案
glibc rand()具有两种不同的生成器实现:
glibc rand() has two different generator implementations:
-
一个简单的线性同余生成器(LCG)，由以下等式定义:
A simple linear congruential generator (LCG), defined by the following equation:
val = ((state * 1103515245) + 12345) & 0x7fffffff
(& 0x7fffffff丢弃最小随机最高有效位)
(& 0x7fffffff throws away the least random most significant bit)
这是一个非常简单的单状态LCG.它有一些缺点.最重要的是，因为它是一个状态生成器，所以不会在每个单独的rand()调用上生成完全伪随机数.真正的作用是它以伪随机顺序遍历整个范围(2 ^ 31).这有一个有意义的含义:当您获取某个号码时，这意味着您将不在当前期间再次获取该号码.您将在下一个2 ^ 31 rand()调用中再次准确地获得该号码，而不会再迟了.
This is a very simple, single state LCG. It has some drawbacks. The most important one is that, because it is a single state generator, it does not generate a fully pseudorandom number on each separate rand() call. What it really does is that it traverses the whole range (2^31) in a pseudorandom order. This has a meaningful implication: when you obtain some number it means that you will not obtain that number again in the present period. You will obtain that number again exactly in the next 2^31 rand() call, no sooner, no later.
此生成器在glibc源中称为TYPE_0.
稍微高级一点的加性反馈生成器.该生成器具有许多状态，这意味着它不具有上述的遍历属性".您可以在同一时期内两次(或多次)获得相同的数字.
A slightly more advanced, additive feedback generator. That generator has many states, which means that it does not have the "traverse property" described above. You can get the same number twice (or more times) during the same period.
您可以在此处找到一个很好的描述.
You can find an excellent description of that algorithm here.
此生成器在glibc源中称为TYPE_1，TYPE_2，TYPE_3或TYPE_4.
This generator is called the TYPE_1, TYPE_2, TYPE_3 or TYPE_4 in the glibc source.
回到您的问题，即它如何生成值:
Coming back to your question, that is how it generates values:
seeding_stage() // (code omitted here, see the description from above link)
for (i=344; i<MAX; i++)
{
r[i] = r[i-31] + r[i-3];
val = ((unsigned int) r[i]) >> 1;
}
您问题中的else之后的代码只是上面的代码，但是以不同的方式编写(使用指向包含先前值的数组的指针).
The code after the else in your question is simply the above code, but written in a different way (using pointers to the array containing previous values).
Which generator is used depends on the size of the initial state set with the initstate() function. The first (LCG) generator is used only when state size is 8 bytes. When it is bigger, the second generator is used. When you set your seed using srand() the size of the state is 128 bytes by default, so the second generator is used. Everything is written in comments in the glibc source file referenced by you in your question.
这篇关于glibc rand函数实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
