为什么在类型转换之前要先除以一个变量？

Question

我正在查看K&R2 2.7类型转换中的RNG：

unsigned long int next = 1;

/* rand:  return pseudo-random integer on 0..32767 */
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

/* srand:  set seed for rand() */
void srand(unsigned int seed)
{
    next = seed;
}

为什么在进行类型转换之前，next 要被 65536 整除后再转换为 unsigned int？

我最初的直觉是与 int 是16位或者 RAND_MAX 当时是32767 有关，但是即使在当前我的机器上，int 是32位且 RAND_MAX 是2147483647，我仍然得到相同的结果（https://oeis.org/A061364）。

如果我遗漏了一些显而易见的东西，或者对于认为 K&R2 已经过时的人向大家道歉 - 这个例子仍然出现在 C 标准中，C17 7.22.2.2 The srand function，所以我假设我的问题在今天仍然有效。

- rsarson

---

这只是他们编写用于使用的随机数生成器公式的一部分。如果没有它，您将拥有一个具有较差特性的线性同余生成器。 - Raymond Chen

@RaymondChen：这确实是一个线性同余生成器，只返回重复值的上位比特，并且始终丢弃熵较小的低16位。 - Chris Dodd

@rsarson 为了看到所讨论的效果，请尝试将return语句更改为返回next％32768或仅返回next，然后编写一个循环打印几个连续的rand()％2值。 - Steve Summit

Answer 1

在进行类型转换之前进行除法运算，代码确保使用next的类型（即unsigned long，至少32位），而不是强制转换后的类型（unsigned int），后者可能只有16位。

请注意，实际上并不需要转换，只需加上括号即可。

return (next / 65536) % 32768;

它会执行相同的操作，只是使用32位类型进行模运算，但由于这只是屏蔽了上位比特（返回底部15位），因此结果是相同的。

- Chris Dodd

Answer 2

当int为（或可以为）16位时，在转换之前进行除法是必要的，而在int为32位时则不需要。

整个除以65536并取32768的余数序列是一种有点混淆的方法，用于提取next的第16到（独占）31位。将其作为第一步转换为16位类型会立即丢弃我们想要的位，因此不可行。将其转换为32位类型不会造成任何损害，我们想要的位仍然存在，将其作为第二步骤进行除法运算是可行的。

如果根本没有任何除法（或右移），无论是在转换之前还是之后，那么结果将是一个更差的PRNG：实际上，这将把它从“具有15位输出的31位PRNG”变成一个15位PRNG（因为更新公式具有信息只能通过数字向上流动的属性，高位永远不会影响低位，对其进行截断可以看作是具有较少状态位的PRNG，并且可以重写为此类）。与通常的线性同余生成器一样，高位“更好”，低位具有非常小的周期（最低有效位根本不随机，它只是交替出现）。

- harold

---

值得注意的是，在将BSD Unix首次移植到32位VAX处理器数年后，rand()函数的性能变得非常糟糕，因为有人粗心地改变了return语句，使其返回所有32位，也就是说，他们将其变成了一个纯LCRG，带有周期性。 - Steve Summit

@harold 跟进问题：https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/rand_r.c 中“扩展到32位”是什么意思？如果我测试K＆R2 2.7，它在2^31迭代后重复。如果测试rand_r（），则为2^27。我还注意到在https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use中，ANSI C的“种子输出位”是“30..16位”，而不是glibc的“30..0位”。此外，https://oeis.org/A096553是否相关，即“输出限于15位”？ - rsarson

另外，略微偏题，但@steve-summit，我有你的K＆R2 2015讲义 :) - rsarson

@rsarson所说的“扩展到32位”显然意味着“使用3个rand步骤来提取31个随机位并将它们粘在一起”（不是32位，正如您发现的那样）。A096553是生成器的状态而不是其输出。 - harold