c - glibc rand函数实现

Question

我正在阅读 c standard library rand() function implementation与 glibc 源代码。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;
}

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

Answer 1

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

1. 一个简单的线性同余生成器 (LCG)，由以下等式定义:

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

   (& 0x7fffffff 丢弃最不随机的最高有效位)

   这是一个非常简单的单状态 LCG。它有一些缺点。最重要的是，因为它是一个单一的状态生成器，它不会在每个单独的 rand() 上生成完全伪随机数。称呼。它真正做的是它以伪随机顺序遍历整个范围 (2^31)。这有一个有意义的含义:当你获得某个数字时，意味着你将不会在当前期间再次获得该数字。您将在接下来的 2^31 rand() 中再次获得该数字。打电话，不早不晚。

   这个生成器叫做 TYPE_0在glibc来源。

2. 稍微更高级的附加反馈生成器。那个生成器有很多状态，这意味着它不具有上面描述的“遍历属性”。您可以在同一时期两次(或更多次)获得相同的数字。

   您可以找到该算法的出色描述 here .

   这个生成器叫做 TYPE_1 , TYPE_2 , TYPE_3或 TYPE_4在glibc来源。

   回到你的问题，这就是它产生值(value)的方式:

   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 之后的代码在你的问题中只是上面的代码，但是以不同的方式编写(使用指向包含先前值的数组的指针)。

使用哪个生成器取决于使用 initstate() 设置的初始状态的大小功能。第一个 (LCG) 生成器仅在状态大小为 8 字节时使用。当它更大时，使用第二个生成器。当您使用 srand() 设置种子时状态的大小默认为 128 字节，因此使用第二个生成器。一切都写在 glibc 的评论中您在问题中引用的源文件。