已有的 Math.random(),后来的 Math.random()

发布时间 · 标签: ECMAScript internals

Math.random() 返回一个带有正号的 Number 值,大于或等于 0 但小于 1,使用依赖于实现的算法或策略随机或伪随机选择并在该范围内近似均匀分布。这个函数没有参数。

ES 2015, section 20.2.2.27

Math.random() 是 Javascript 中最著名和最常用的随机源。在 V8 和大多数其他 Javascript 引擎中,它是使用伪随机数生成器 (pseudo-random number generator,PRNG) 实现的。与所有 PRNG 一样,随机数源自内部状态,对于每个新随机数,该状态由固定算法更改。所以对于给定的初始状态,随机数序列是确定性的。由于内部状态的位大小 n 是有限的,因此 PRNG 生成的数字最终会重复。这个置换循环(permutation cycle)周期长度的上限是 2n

有许多不同的 PRNG 算法;其中最著名的是 Mersenne-TwisterLCG。每个都有其特定的特点、优点和缺点。理想情况下,它会为初始状态使用尽可能少的内存,执行速度快,周期长度大,并提供高质量的随机分布。虽然可以轻松测量或计算内存使用、性能和周期长度,但质量更难确定。统计测试背后有很多数学运算来检查随机数的质量。事实上的标准 PRNG 测试套件 TestU01 实现了其中的许多测试。

直到最近(直到版本 4.9.40),V8 选择的 PRNG 还是 MWC1616(乘以进位,结合两个 16 位部分)。它使用 64 位内部状态,大致如下所示:

uint32_t state0 = 1;
uint32_t state1 = 2;
uint32_t mwc1616() {
state0 = 18030 * (state0 & 0xFFFF) + (state0 >> 16);
state1 = 30903 * (state1 & 0xFFFF) + (state1 >> 16);
return state0 << 16 + (state1 & 0xFFFF);
}

然后根据规范将 32 位值转换为介于 0 和 1 之间的浮点数。

MWC1616 使用很少的内存并且计算速度非常快,但不幸的是提供低于标准的质量:

  • 它可以生成的随机值的数量限制为 232 个,而双精度浮点数可以表示 0 到 1 之间的 252 个数字。
  • 结果的更重要的上半部分几乎完全取决于 state0 的值。周期长度最多为 232,但不是几个大的置换周期,而是许多短的置换周期。如果初始状态选择不当,周期长度可能小于 4000 万。
  • 它未能通过 TestU01 套件中的许多统计测试。

已经向我们指出了这一点,并且了解了问题并经过一些研究后,我们决定基于称为 xorshift128+ 的算法重新实现 Math.random。它使用 128 位内部状态,周期长度为 2128 - 1,并通过了 TestU01 套件的所有测试。

uint64_t state0 = 1;
uint64_t state1 = 2;
uint64_t xorshift128plus() {
uint64_t s1 = state0;
uint64_t s0 = state1;
state0 = s0;
s1 ^= s1 << 23;
s1 ^= s1 >> 17;
s1 ^= s0;
s1 ^= s0 >> 26;
state1 = s1;
return state0 + state1;
}

在我们意识到这个问题的几天内,新的实现就登陆了 V8 v4.9.41.0。它将在 Chrome 49 中可用。FirefoxSafari 也都切换到 xorshift128+。

但是请不要误会:尽管 xorshift128+ 是对 MWC1616 的巨大改进,但它仍然不是加密安全的。对于散列、签名生成和加密/解密等用例,普通的 PRNG 是不合适的。Web Cryptography API 引入了 window.crypto.getRandomValues,这是一种以性能为代价返回加密安全随机值的方法。

请记住,如果你发现 V8 和 Chrome 有改进的地方,即使是像这个这样的地方,也不会直接影响规范合规性、稳定性或安全性,请在我们的错误跟踪器上提交问题

作者:Yang Guo (@hashseed), software engineer and dice designer.