誰說Python慢來著？不用Python，這個問題難倒了無數的程式員

圍棋是全世界最古老的棋種（沒有之一），也是古代哲學思想和中國傳統文化的物質載體，小小紋枰，不過一尺見方，竟蘊藏著萬千氣象，著實令人為之著迷，少年時代的我，曾經有一段時間醉心于圍棋，

標準的圍棋盤由橫豎各19道線組成網格，共有361個交叉點，每個交叉點上有白子、黑子和無子等三種可能的狀態，那么問題來了：圍棋總共有多少種不同的局面呢？

稍微思考一下，所有的程式員都會給出正確的答案： 3 361 3^{361} 3361（3的361次方），可是，這究竟是一個多大的數字呢？算一下就知道了，

Python程式員隨手寫了一行代碼，敲個回車，計算就結束了，

>>> pow(3,361)
174089650659031927907188238070
564367946602724950263541194828
118706801051676184649841162792
889887149386120969888163207806
137549871813550931295148033696
60572893075468180597603

C/C++程式員看完Python程式員的操作，不以為然，心里想，別看你寫起來簡單，速度肯定沒我快，講效率，還得看我C/C++的，

long result = 1
int i
for(i=0; i<361; i++) {
	result *= 3;
}

寫到這里，C/C++程式員忽然意識到，long int恐怕不夠用，即使long long int也只有8個位元組，最大只能到 2 64 ? 1 2^{64}-1 264?1，計算 3 361 3^{361} 3361肯定會溢位的，比long long更大的整型沒有了，要是臨時定義一個結構保存超大整數，再為超大整數的計算寫一堆函式，恐怕一時半會兒搞不定，這可如何是好？要不用改用double float試試？趕緊上網查了一下，double可以表示-1.79E+308 ~ +1.79E+308之間的任意數，可是 3 361 3^{361} 3361在這個范圍內嗎？

這時，C/C++程式員心里有點慌了，幸好有點數學功底，簡單計算一下:

l o g 10 3 361 = 361 × l o g 10 3 ≈ 172.24077295379814 log_{10}{3^{361}}=361\times log_{10}3\approx172.24077295379814 log10?3361=361×log10?3≈172.24077295379814

3 361 3^{361} 3361大約有173位長，總算還在double覆寫的范圍之內，也不用回圈了，直接使用數學庫中的pow函式吧，

#include <stdio.h>
#include <math.h>

int main(void) {
    double result = pow(3,361);
    printf("%Lf\n", result);

    return 0;
}

最后，C/C++程式員給出了一個浮點型別的答案，雖然精度略有損失，但也不算離譜，我用的是CodeBlocks，顯示耗時28毫秒，這里面應當包括了編譯連接的時間，否則C不至于慢到這個程度，

174089650659031910000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
00000000000000000000000.000000

Process returned 0 (0x0)
Execution time : 0.028 s

看完C/C++程式員的這番折騰，Java程式員擦擦額頭的冷汗，心中暗自慶幸：多虧我大Java有BigInteger這樣的神器，不然真要出丑了，

import java.math.BigInteger;

BigInteger result = new BigInteger("1");
for(int i=1; i<=361; i++) {  
	result.multiply(new BigInteger("3")));
}

BigInteger用起來很方便，計算 3 361 3^{361} 3361毫無壓力，只是不能兼容普通整型的那些運算子號，所有的運算都需要顯式地呼叫函式，比如，這里的乘法就得呼叫multiply函式，

以上場景，純屬臆測，絕無褒貶任何編程語言之意，請各位明察，實際上，Python的超大整數計算也是C語言實作的，只不過采用了非常精妙的方案，最終經過各種優化，性能遠超我們自己寫出來的C代碼，

Python的超大整數計算方案，精妙在哪兒呢？僅舉存盤一例：普通的Python整型采用4個位元組存盤，當處理超大整數時，每4個位元組一個存盤單元，單元之間采用 2 30 2^{30} 230即1073741824進制，一個單元滿1073741824即向上一單元進位，

采用1073741824進制的Python的超大整數計算方案的效率如何呢？還是以計算 3 361 3^{361} 3361為例，看Python代碼需要多長時間，

>>> import time
>>> def power(x, base=2):
	t0 = time.time()
	result = pow(base, x)
	print('耗時%.06f秒'%(time.time()-t0))
	return result

>>> power(361, base=3)
耗時0.000000秒
174089650659031927907188238070
564367946602724950263541194828
118706801051676184649841162792
889887149386120969888163207806
137549871813550931295148033696
60572893075468180597603

太神奇了！居然連1微秒都不到？我有點懷疑這個結論，繼續測驗更大的數字，2的1000次方，

>>> power(1000)
耗時0.000000秒
107150860718626732094842504906
000181056140481170553360744375
038837035105112493612249319837
881569585812759467291755314682
518714528569231404359845775746
985748039345677748242309854210
746050623711418779541821530464
749835819412673987675591655439
460770629145711964776865421676
604298316526243868372056680693
76

計算 2 1000 2^{1000} 21000所花時間同樣少于1微秒，但是顯示計算結果花費了較長時間，我把代碼修改了一下，不再顯示計算結果，只考察計算時間，

>>> def power(x, base=2):
	t0 = time.time()
	result = pow(base, x)
	print('耗時%.06f秒'%(time.time()-t0))
	#return result

	
>>> power(10000) # 2的1萬次方
耗時0.000000秒
>>> power(100000) # 2的10萬次方
耗時0.000000秒
>>> power(1000000) # 2的100萬次方
耗時0.005016秒
>>> power(10000000) # 2的1千萬次方
耗時0.048000秒
>>> power(100000000) # 2的1億次方
耗時0.620648秒
>>> power(1000000000) # 2的10億次方
耗時7.448035秒
>>> power(10000000000) # 2的100億次方
耗時77.881435秒

計算2的1萬次方和2的10萬次，所花時間仍然不足1微秒，直到計算2的100萬次方時，方才顯示耗時5毫秒，當算完2的100億次方之后，我沒有繼續下去——2的100億次方，這個數字實在是太過恐怖，我已經無法想象它的大小了，要知道，地球上全部物質的原子數量，也不過是1.28E47這個量級，大約是2的157次方，

那么，Python能夠計算的最大整數到底有多大呢？我沒有明確的概念，不過我在驗證費馬小定理的逆命題時，出現過一次超大整數計算錯誤，

a = 2
t = 2305843009213693951
s = 1152921504606846975
Traceback (most recent call last):
  File "huge.py", line 56, in <module>
    miller_rabin(x) # M61
  File "huge.py", line 42, in miller_rabin
    print((pow(a, t*pow(2,s)) - 1)%huge_num)
MemoryError

當我試圖計算pow(a, t*pow(2,s)時，發生了記憶體錯誤，這里a等于2，s大于115億億，t大于230億億，顯然，這個結果遠遠大于2的100億次方，