php - 为什么 mt_rand(1, PHP_INT_MAX) 总是返回奇数

Question

我刚刚遇到一个 interesting question来自 Hacker News 上的 ComputerGuru，没有任何评论似乎给出了令人信服的答案。

为什么 mt_rand(1, PHP_INT_MAX) 总是返回奇数？

我不是原始问题的作者。

http://3v4l.org/dMbat

for ($i=0;$i<10000;$i++)
{
    echo mt_rand(1, PHP_INT_MAX)."\n";
}

输出:

8571620074060775425
7401021871338029057
4351677773593444353
1801559362708176897
7848614552286527489
...

Answer 1

PHP_INT_MAX 这里是 2⁶³-1(64 位有符号整数最大值)。

但是，mt_rand() 无法处理这么大的值。 Mersenne twister 在内部生成 32 位字，而 PHP 的 mt_getrandmax() 只有 2³¹-1(它丢弃了最高位)。

要在您请求的 min 到 max 范围内生成一个值，mt_rand 首先获取 0 到 2³¹-1 个随机数，然后使用此公式对其进行缩放:

x = ((x / (mt_getrandmax() + 1)) * (max - min + 1)) + min;

(参见 rand.c 和 php_rand.h 的来源。)

基本上它会盲目缩放内部生成的数字以适应过大的范围，甚至不会发出警告。乘法以适应过大的范围会在低位生成大量零，然后添加 min(即 1)会使结果变成奇数。

问题在十六进制中更为显着，您可以看到每个数字的低 32 位完全是非随机的:

for ($i = 0; $i < 10000; $i++) {
    printf("%016x\n", mt_rand(1, PHP_INT_MAX));
}

输出:

41e0449b00000001
53d33d7c00000001
6ec8855700000001
234140e000000001
13a4581900000001
77547beb00000001
35a0660a00000001
0d0cd44200000001
...

有一个注释in the manual试图警告这一点，尽管它低估了问题:

The distribution of mt_rand() return values is biased towards even numbers on 64-bit builds of PHP when max is beyond 2³². This is because if max is greater than the value returned by mt_getrandmax(), the output of the random number generator must be scaled up.

(它说它偏向于偶数，但只有当 min 是偶数时才是正确的。)