c++ - LCG 中的 int 乘法溢出

Question

下面是从一个开源项目的rand()中复制过来的，它使用了LCG

rand_next = rand_next * 1103515245L + 12345L;  //unsigned long rand_next

经典的LCG是:

Next = (Next * a + c) mod M

显然，这里的 M 是 2^32。

让我感到困惑的是 rand_next * 1103515245L，我很确定这里会发生溢出!我看了几个 rand() 实现，除了使用不同的 a 和 c 之外，都采用这种方式。

溢出有害吗？如果不是，为什么？

谢谢

Answer 1

这很好。根据 C99 规范，对于无符号长运算，the result is the same but reduced modulo 2³² (§6.2.5) :

A computation involving unsigned operands can never overflow, because a result 
that cannot be represented by the resulting unsigned integer type is reduced 
modulo the number that is one greater than the largest value that can be 
represented by the resulting type.

所以这种行为实际上并不是“溢出”，但为了简单起见，我会在这个答案中称它为“溢出”。因为对于模运算我们有

a1 ≡ b1 (mod m)
a2 ≡ b2 (mod m)

暗示

a1 + a2 ≡ b1 + b2 (mod m)

我们有

Next * a ≡ k (mod 2^32)

其中 k 是带有“溢出”的 Next * a。所以由于 M = 2^32，

Next * a + c ≡ k + c (mod M)

有“溢出”的结果和没有“溢出”的结果在模运算下是等价的，所以公式没问题。一旦我们减少模 M = 2^32，它会给出相同的结果。