LevelDB 随机数

C语言中伪随机数生成算法实际上是采用的 "线性同余法"：

其中 A C M 都是常数（一般会取质数），当时，叫做乘同余法。
假设我们定义：

void rand(int &seed)
{
    seed = (seed * A + C ) % M;
}

每次调用rand函数都会产生一个随机值赋值给seed，可以看出实际上用rand函数生成的是一个递推的序列，一切值都来源于最初的 seed 种子。所以当初始的 seed 取一样的时候，得到的序列都相同。

一个伪随机数常用的原则就是M尽可能的大，例如，对于32位的机器来说，选择：

时可以取得最佳效果。

class Random
{
public:
    explicit Random(uint32_t s) : seed_(s & 0x7fffffffu)
    {
        // seed_不能为零或M，否则所有的后续计算的值将为零或M
        if (seed_ == 0 || seed_ == 2147483647L)
        {
            seed_ = 1;
        }
    }

    uint32_t Next()
    {
        static const uint32_t M = 2147483647L; // 2^31-1
        static const uint64_t A = 16807;       // bits 14, 8, 7, 5, 2, 1, 0

        // We are computing
        //       seed_ = (seed_ * A) % M,    where M = 2^31-1
        //
        // seed_ must not be zero or M, or else all subsequent computed values
        // will be zero or M respectively.  For all other values, seed_ will end
        // up cycling through every number in [1,M-1]
        uint64_t product = seed_ * A;
        // Compute (product % M) using the fact that ((x << 31) % M) == x.
        seed_ = static_cast<uint32_t>((product >> 31) + (product & M));
       
        // The first reduction may overflow by 1 bit, so we may need to
        // repeat.  mod == M is not possible; using > allows the faster
        // sign-bit-based test.
        if (seed_ > M)
        {
            seed_ -= M;
        }

        return seed_;
    }
    
    // 返回分布均匀的数，在 [0 ... n-1]
    uint32_t Uniform(int n)  {  return Next() % n;  }

    bool OneIn(int n)  {  return (Next() % n) == 0;  }

    uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1));

private:
    uint32_t seed_;
}

源码这里：

uint64_t product = seed_ * A;
seed_ = static_cast<uint32_t>((product >> 31) + (product & M));
   
if (seed_ > M)
{
    seed_ -= M;
}

参考资料
1、https://developer.aliyun.com/article/2271
2、http://www.voidcn.com/article/p-hoatydif-brn.html