LevelDB 源码解析之 Random 随机数

举报
debugzhang 发表于 2021/03/20 23:41:07 2021/03/20
【摘要】 本文介绍了 LevelDB 的随机数类 Random。

GitHub: https://github.com/storagezhang

Emai: debugzhang@163.com

LevelDB: https://github.com/google/leveldb


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

s e e d = ( s e e d A + C ) % M seed = (seed * A + C ) \% M

其中 A , C , M A,C,M 都是常数(一般会取质数)。当 C = 0 C=0 时,叫做乘同余法。

假设定义随机数函数

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

每次调用 rand 函数都会产生一个随机值赋值给 seed,实际上 rand 函数生成的随机数是一个递推序列,初值为 seed。所以当初始的 seed 相同时,得到的递推序列也会相同。我们称 seed 为随机数种子,称 rand 生成的随机数为伪随机数,一个伪随机数常用的原则就是 M 尽可能的大。

在 LevelDB 的随机数类 Random 类中, A = 16807 , M = 2147483647 , C = 0 A=16807, M=2147483647, C=0

explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) {
  // Avoid bad seeds.
  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_;
}

源码中利用 (product >> 31) + (product & M) 来代替 product % M,主要是为了避免 64 位除法。

下面证明 p r o d u c t   %   M = ( p r o d u c t > > 31 ) + ( p r o d u c t   &   M ) product\ \%\ M = (product >> 31) + (product\ \&\ M)

将  p r o d u c t  分为高  33  位和低  31  位 将\ product\ 分为高\ 33\ 位和低\ 31\ 位

令高  33  位的值为  H ,低  31  位的值为  L 令高\ 33\ 位的值为\ H,低\ 31\ 位的值为\ L

则  p r o d u c t = H < < 31 + L = H 2 31 + L = H M + L 则\ product = H << 31 + L = H \cdot 2^{31}+L = H \cdot M + L

因为  p r o d u c t = s e e d A ,且  s e e d  和  A  都小于  M ,故  H  必小于  M 因为\ product = seed \cdot A, 且\ seed\ 和\ A\ 都小于\ M,故\ H\ 必小于\ M

等式左边 = p r o d u c t %   M = ( H M + L ) %   M = ( H + L ) %   M 等式左边 = product \%\ M = (H \cdot M+L) \%\ M = (H + L) \%\ M

等式右边 = ( p r o d u c t > > 31 ) + ( p r o d u c t   &   M ) = ( H 2 31 + L ) > > 31 + L = H + L 等式右边 = (product >> 31) + (product\ \&\ M) = (H \cdot 2^{31}+L)>>31 + L = H + L

此时考虑下方的 if 语句:

if (seed_ > M) {
  seed_ -= M;
}

由于 H H L L 都小于 M M ,故 H + M < 2 L H+M<2L

经过语句,等式右边也等于 ( H + L ) %   M (H + L) \%\ M  了。

综上,等式成立。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。