c - 如何确保模数为正值

Question

给定这个简单的随机生成器:

int i, r = 0;
for (i = 0; i < 50; i++) {
    r = (1234 * r + 101) % (11000000);
    printf("%d\n", r);
}

令人惊讶的是，我得到负值!

101
124735
10923091
192507
6553739
-7620565
-10842517
-10763989
-1860437
8188139

不应该是正值吗？谁能解释一下？

Answer 1

你得到负值是因为你的程序有整数算术溢出。对于签名类型 int，该行为实际上是未定义的。您应该使用更大的类型来避免这种情况。 unsigned long long 类型保证至少有 64 个值位，这足以满足最大中间结果 1234 * 10999999 + 101。

int i;
unsigned long long r = 0;
for (i = 0; i < 50; i++) {
    r = (1234 * r + 101) % 11000000;
    printf("%llu\n", r);
}

rici 评论说 r 不需要是更大的类型，因为它的值在 0..10999999 范围内。这并不完全正确，因为 int 类型可能太小而无法处理此类值。 int 的范围可以小到 -32767..32767。

然而，中间计算必须使用更大的类型来执行，以避免算术溢出。下面是相应的代码:

int i, r = 0;  // assuming 32-bit ints
for (i = 0; i < 50; i++) {
    r = (1234ULL * r + 101) % 11000000;
    printf("%d\n", r);
}