阶乘循环变为0

Question

我用一种编译语言运行了一个简单的程序，计算自然数的阶乘，使用两个简单的循环，一个外部循环来跟踪我们正在计算阶乘的数字，一个内部循环来通过将从1到该数字本身的每个自然数相乘来计算阶乘。该程序对于前几个自然数的阶乘计算完美无误，但是从第13个值开始，计算出的阶乘明显错误。这是由于现代计算机实现的整数算术，我可以理解为什么会出现负值。

不过，我不明白的是，为什么，在不断测试的不同计算机上，只计算了很少的阶乘之后，总是会出现数字零。当然，如果第n个阶乘被评估为0，则(n + 1) -th阶乘也将被评估为0，依此类推，但为什么在很少的阶乘计算后总是出现数字0？

编辑：您可能想知道为什么我使用了两个不同的循环而不是只有一个...我这样做是为了强制计算机从头开始重新计算每个阶乘，以测试确实阶乘始终变为0而不是偶然发生。

以下是我的输出：

- John

---

编译语言是什么意思？你似乎了解术语，但你的“现代计算机”仍然会遭受整数溢出的问题。 - OneCricketeer

请展示你的代码。 - Mazz

Answer 1

从34开始，所有的阶乘都可以被2^32整除。因此，当你的计算机程序计算结果对2^32取模时（虽然你没有说你使用什么编程语言，但很可能是这样），结果总是0。

以下是一个Python程序，用于计算阶乘对2^32取模的结果：

def sint(r):
    r %= (1 << 32)
    return r if r < (1 << 31) else r - (1 << 32)

r = 1
for i in xrange(1, 40):
    r *= i
    print '%d! = %d mod 2^32' % (i, sint(r))

这将得到以下输出，与您自己程序的输出一致：

1! = 1 mod 2^32
2! = 2 mod 2^32
3! = 6 mod 2^32
4! = 24 mod 2^32
5! = 120 mod 2^32
6! = 720 mod 2^32
7! = 5040 mod 2^32
8! = 40320 mod 2^32
9! = 362880 mod 2^32
10! = 3628800 mod 2^32
11! = 39916800 mod 2^32
12! = 479001600 mod 2^32
13! = 1932053504 mod 2^32
14! = 1278945280 mod 2^32
15! = 2004310016 mod 2^32
16! = 2004189184 mod 2^32
17! = -288522240 mod 2^32
18! = -898433024 mod 2^32
19! = 109641728 mod 2^32
20! = -2102132736 mod 2^32
21! = -1195114496 mod 2^32
22! = -522715136 mod 2^32
23! = 862453760 mod 2^32
24! = -775946240 mod 2^32
25! = 2076180480 mod 2^32
26! = -1853882368 mod 2^32
27! = 1484783616 mod 2^32
28! = -1375731712 mod 2^32
29! = -1241513984 mod 2^32
30! = 1409286144 mod 2^32
31! = 738197504 mod 2^32
32! = -2147483648 mod 2^32
33! = -2147483648 mod 2^32
34! = 0 mod 2^32
35! = 0 mod 2^32
36! = 0 mod 2^32
37! = 0 mod 2^32
38! = 0 mod 2^32
39! = 0 mod 2^32

以下是这个阶乘范围的精确值表格，显示每个阶乘包含多少个2的幂次方：

1! = 1. Divisible by 2^0
2! = 2. Divisible by 2^1
3! = 6. Divisible by 2^1
4! = 24. Divisible by 2^3
5! = 120. Divisible by 2^3
6! = 720. Divisible by 2^4
7! = 5040. Divisible by 2^4
8! = 40320. Divisible by 2^7
9! = 362880. Divisible by 2^7
10! = 3628800. Divisible by 2^8
11! = 39916800. Divisible by 2^8
12! = 479001600. Divisible by 2^10
13! = 6227020800. Divisible by 2^10
14! = 87178291200. Divisible by 2^11
15! = 1307674368000. Divisible by 2^11
16! = 20922789888000. Divisible by 2^15
17! = 355687428096000. Divisible by 2^15
18! = 6402373705728000. Divisible by 2^16
19! = 121645100408832000. Divisible by 2^16
20! = 2432902008176640000. Divisible by 2^18
21! = 51090942171709440000. Divisible by 2^18
22! = 1124000727777607680000. Divisible by 2^19
23! = 25852016738884976640000. Divisible by 2^19
24! = 620448401733239439360000. Divisible by 2^22
25! = 15511210043330985984000000. Divisible by 2^22
26! = 403291461126605635584000000. Divisible by 2^23
27! = 10888869450418352160768000000. Divisible by 2^23
28! = 304888344611713860501504000000. Divisible by 2^25
29! = 8841761993739701954543616000000. Divisible by 2^25
30! = 265252859812191058636308480000000. Divisible by 2^26
31! = 8222838654177922817725562880000000. Divisible by 2^26
32! = 263130836933693530167218012160000000. Divisible by 2^31
33! = 8683317618811886495518194401280000000. Divisible by 2^31
34! = 295232799039604140847618609643520000000. Divisible by 2^32
35! = 10333147966386144929666651337523200000000. Divisible by 2^32
36! = 371993326789901217467999448150835200000000. Divisible by 2^34
37! = 13763753091226345046315979581580902400000000. Divisible by 2^34
38! = 523022617466601111760007224100074291200000000. Divisible by 2^35
39! = 20397882081197443358640281739902897356800000000. Divisible by 2^35

- Paul Hankin

---

我之前没有听说过这个事实。你有证明的链接吗？ - paddy

@paddy 你可以只计算2的因子。在1到34之间，有floor(34/2)个可被2整除的数字，floor(34/4)个可被4整除的数字，floor(34/8)个可被8整除的数字，以此类推。(34 // 2) + (34 // 4) + (34 // 8) + (34 // 16) + (34 // 32) = 32。 - Paul Hankin

一个整数的符号（+或-）不是使用了1位吗？那么如果这个数字能被2^31整除，它的符号位不应该已经是0了吗？ - John

@John，现代大多数编程语言实现使用二进制补码表示固定大小的32位整数，因为这是现代处理器的工作方式。这对应于模2^32算术。 - Paul Hankin

哦，我现在明白了，但还有一个最后的问题，如果阶乘的计算从13!开始就已经出错了，那么我们怎么能确信计算机确实知道34!中有2^32这个因子呢？ - John

不要认为它们是错误的——把这个程序看作是在计算 $2^{32}$ 取模下的阶乘结果。 - Paul Hankin

Answer 2

每次乘法运算都会从右侧添加零位，直到某个迭代因为溢出而丢弃左侧最高位的位数。

效果如下：

    int i, x=1;
    for (i=1; i <=50; i++) {
        x *= i;
        for (int i = 31; i >= 0; --i) {
            printf("%i",(x >> i) & 1);
        }
        printf("\n");
    }

输出的比特位：

00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000110
00000000000000000000000000011000
00000000000000000000000001111000
00000000000000000000001011010000
00000000000000000001001110110000
00000000000000001001110110000000
00000000000001011000100110000000
00000000001101110101111100000000
00000010011000010001010100000000
00011100100011001111110000000000
01110011001010001100110000000000
01001100001110110010100000000000
01110111011101110101100000000000
01110111011101011000000000000000
11101110110011011000000000000000
11001010011100110000000000000000
00000110100010010000000000000000
10000010101101000000000000000000
10111000110001000000000000000000
11100000110110000000000000000000
00110011100000000000000000000000
11010000000000000000000000000000
10000000000000000000000000000000
00000000000000000000000000000000

请注意，在获取零之前，我们会得到 INT_MIN 。附加另一个零位-丢弃符号位，因此从INT_MIN我们得到简单的零。

- Agnius Vasiliauskas

---

很好的可视化！ - Paul Hankin

你的图像在我读到文字之前就已经清楚地解释了这个想法。谢谢。 - undefined