glibc rand函数实现

Question

我正在阅读带有glibc源代码的标准库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()通话中再次获得该号码,不久之后,不会更晚.

   这个生成器TYPE_0在glibc源代码中被称为.

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

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

   该发电机被称为TYPE_1,TYPE_2,TYPE_3或TYPE_4在glibc源.

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

   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在您的问题中引用的源文件中,所有内容都写在注释中.

Answer 2

如果其他人需要简单地重新实现 GNU C 库的 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);
        }
    }
}