1.3 大整數與精確計算#

概念說明#

C、Java 等語言的整數型別有固定寬度（如 64 位元整數最大約 9.2 × 10¹⁸），超過就「溢位」，可能得到荒謬的負數。Python 的整數沒有這個問題：Python 3 的 int 是任意精度的，100 位、1000 位、10000 位的整數都直接可算。背後的原理是：Python 把大整數存成一串 30 位元的「 limb 」，需要多少就配置多少，並以直式計算的方式實作加減乘除。

有了大整數，很多數學問題就能精確計算，而不是近似：計算 100! 的完整值、驗證費馬大定理的小規模反例檢查、密碼學中的大質數運算（第 2、3 章的主角）等等。除了大整數，Python 標準庫還提供兩個精確/高精度工具：

fractions.Fraction：用分子分母（兩個整數）表示有理數，四則運算完全精確。
decimal.Decimal：可自訂精度的十進位浮點數，適合金融計算與高精度實數。

演算法步驟#

處理大數問題的典型策略：

保持整數世界：只要題目答案是整數或有理數，盡量全程用 int 或 Fraction，不要中途轉成 float。
模運算縮小數字：密碼學與競賽題常要求「答案對 10⁹+7 取餘數」，因為模運算與加減乘可交換（(a·b) mod m = ((a mod m)·(b mod m)) mod m），可以在中間過程不斷取模，讓數字不爆炸。
避免不必要的精確運算：大數乘法遠比浮點乘法慢，能用模運算就不要算出天文數字。
需要實數高精度時用 decimal，把精度設夠高再做運算。

Python 程式碼範例#

import math
from fractions import Fraction
from decimal import Decimal, getcontext

# 1. 大整數直接計算：100!
fact100 = math.factorial(100)
print(f"100! 有 {len(str(fact100))} 位數")   # 158 位
print(fact100)

# 2. 精確分數：Fraction 避免浮點誤差
s = sum(Fraction(1, k) for k in range(1, 101))   # 調和級數
print(f"精確值 = {s}")
print(f"小數值 = {float(s):.15f}")

# 3. 模運算：計算 2^1000 的末 12 位（不直接算出 2^1000）
print(pow(2, 1000, 10**12))
# 驗證：真的算出 2^1000 再取末 12 位，結果相同
print(2**1000 % 10**12)

# 4. 大數快速冪：Python 內建 pow 就是快速冪
print(pow(7, 1000000, 65537))   # 瞬間完成

# 5. 高精度十進位：計算圓周率到 50 位（馬青公式）
getcontext().prec = 60
pi = Decimal(0)
k = 0
for k in range(100):
    pi += Decimal(-1)**k * (Decimal(16)/(2*k+1)/5**(2*k+1)
                            - Decimal(4)/(2*k+1)/239**(2*k+1))
print(pi)   # 3.14159265358979323846...  精確到 50 位左右

複雜度分析#

大整數運算的成本隨位數增長：設 n 為位元數，加減法是 O(n)；直式乘法是 O(n²)，而 Python 實際使用 Karatsuba 演算法，約 O(n^1.585)，3.11 之後更大數還有更快的實作。pow(a, b, m) 使用平方-乘法（square-and-multiply）技巧，只需 O(log b) 次模乘法——這是它能瞬間算出 7^1000000 mod 65537 的原因，也是第 2.3 節的主題。取模策略的威力在於：中間數字永遠不超過 m²，複雜度從「指數級位數增長」壓到「固定大小數字的對數次運算」。

練習#

用 math.factorial(1000) 計算 1000!，統計其位數，並用 Stirling 近似公式 n! ≈ √(2πn)(n/e)ⁿ 估計位數，比較兩者。
用 Fraction 精確計算 1/1 + 1/2² + 1/3² + … + 1/100²，並驗證它非常接近 π²/6（用 math.pi）。
不使用內建 pow，自己實作 my_pow(a, b, m)（平方-乘法），與 pow(a, b, m) 比對結果，並測量 b = 10⁷ 時兩者的速度差異。