因子循環變爲0

我運行了一個編譯語言的簡單程序，它使用兩個簡單循環計算前幾個自然數的階乘，外部記錄一個是我們計算階乘的數字，內部一個通過乘以從1到數字本身的每個自然數來計算階乘。該程序適用於第一個自然數，然後大約從第13個值開始計算的因子顯然是錯誤的。這是由於在現代計算機中實現的整數運算，我可以理解爲什麼會出現負值。我不明白的是，爲什麼，這是我在不同的計算機上測試過的東西，經過非常少量的階乘計算後，總是會達到零。當然，如果第n個因子被評估爲0，第（n + 1）個因子將被評估爲0等等，但爲什麼數字0總是出現在非常少量的階乘計算？因子循環變爲0

編輯：您可能想知道爲什麼我使用了兩個不同的週期而不是隻有一個...我這樣做是爲了強制計算機重新計算每個因子從開始，只是爲了測試事實，確實因子成爲永遠0，這並非偶然。

這是我的輸出：

Output of my program

來源

2017-04-12 John

「一種編譯語言」...意義？你似乎知道術語，但你的「現代計算機」仍然遭受整數溢出 –

請顯示你的代碼。 – Mazz

從34開始！所有階乘是由2^32整除。所以當你的計算機程序計算結果模2^32（其中，儘管你沒有說你正在使用什麼編程語言，這很可能），那麼結果總是0.

這是一個程序，計算階乘MOD 2^32的Python：

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

來源

2017-04-12 12:43:10

我以前沒聽說過這個事實。你有證據鏈接嗎？ – paddy

@paddy你可以只計算2的因子。在1 ... 34中，有可以被2整除的樓層（34/2）數字，可以被4整除的樓層（34/4）數字，可以被整除的樓層（34/8）數字8，等等。（34 // 2）+（34 // 4）+（34 // 8）+（34 // 16）+（34 // 32）= 32'。 –

是不是1位用於整數的符號（+或 - ）？那麼當數字可以被2^31整除時，它不應該始終爲0嗎？ – John

每個乘法追加從右側零位，直到在某個迭代最左位被丟棄，因爲溢出。的影響作用：

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我們得到純粹的零。

來源

2017-04-12 13:59:58

很好的可視化！ –

因子循環變爲0

回答

相關問題