glibc rand函数实现

我正在阅读带有glibc源代码的c标准库rand（）函数实现 。 stdlib / random_r.c，第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; } 

我不明白random_r如何生成随机数(buf->rand_type != TYPE_0) ，有谁请解释一下？ 谢谢。

Answer 1

glibc rand()有两种不同的生成器实现：

1. 简单的线性同余生成器（LCG），由以下等式定义：

   val = ((state * 1103515245) + 12345) & 0x7fffffff

   （ & 0x7fffffff抛弃最随机最重要的位）

   这是一个非常简单的单状态LCG。 它有一些缺点。 最重要的一点是，因为它是单个状态生成器，所以它不会在每个单独的rand()调用上生成完全伪随机数。 它真正做的是它以伪随机顺序遍历整个范围（2 ^ 31） 。 这有一个有意义的含义：当你获得一些数字时，这意味着你不会在当前时期再次获得这个数字。 您将在下一次2 ^ 31 rand()调用中再次获得该号码，不久之后，不会更晚。

   该生成器在glibc源中称为TYPE_0 。

2. 一个稍微更先进的附加反馈发生器。 该生成器具有许多状态，这意味着它没有上述的“遍历属性”。 您可以在同一时期内获得相同的数字两次（或更多次）。

   您可以在此处找到该算法的绝佳描述。

   该生成器在glibc源中称为TYPE_1 ， TYPE_2 ， TYPE_3或TYPE_4 。

   回到你的问题，这就是它产生价值的方式：

    seeding_stage() // (code omitted here, see the description from above link) for (i=344; i> 1; } 

   你问题中else之后的代码只是上面的代码，但是以不同的方式编写（使用指向包含先前值的数组的指针）。

使用哪个生成器取决于使用initstate()函数设置的初始状态的大小。 第一个（LCG）生成器仅在状态大小为8个字节时使用。 当它更大时，使用第二个发生器。 使用srand()设置种子时，默认情况下状态的大小为128字节，因此使用第二个生成器。 在你的问题中引用的glibc源文件中，所有内容都写在注释中。

Answer 2

如果其他人需要对GNU C Library的srand（）/ rand（）函数进行简单的重新实现，那么这个C＃类将完全重现生成的随机数。 unchecked关键字是显式允许整数溢出。 （根据Piotr Jurkiewicz的回答。）

 public class GnuRand { private uint[] r; private int n; public GnuRand(uint seed) { r = new uint[344]; unchecked { r[0] = seed; for (int i = 1; i < 31; i++) { r[i] = (uint)((16807 * (ulong)r[i - 1]) % 2147483647); } for (int i = 31; i < 34; i++) { r[i] = r[i - 31]; } for (int i = 34; i < 344; i++) { r[i] = r[i - 31] + r[i - 3]; } } n = 0; } public int Next() { unchecked { uint x = r[n % 344] = r[(n + 313) % 344] + r[(n + 341) % 344]; n = (n + 1) % 344; return (int)(x >> 1); } } } 

Answer 3

这两种实现完全相同，只是它们使用不同的随机数据。

TYPE_0始终使用幻数1103515245和12345以及当前状态。

否则，它使用从随机数据池中获取的幻数。 每次调用它都会在游泳池中走得更远。 随着时间的推移，它会根据原始的伪随机数替换数据，以便在环绕并再次开始行走时获取新的数字。