大數運算入門：突破類型限制，用數組實現任意精度計算

大數運算入門：突破類型限制，用數組實現任意精度計算

痛點：long long 僅 64 位（約 19 位十進制），不足以應對加密、組合數、高精度科學計算。

核心思想：數組模擬手算

• 每個元素存儲 1 位（十進制）或 4 位（萬進制，基數 10000）
• 低位對齊：a[0] 存個位，a[1] 存十位…
• 逐位運算 + 進位/借位，邏輯與手算完全一致

基本操作框架

// 高精度加法：C = A + B
void add(int *A, int *B, int *C, int len) {
    int carry = 0;
    for (int i = 0; i < len; i++) {
        int sum = A[i] + B[i] + carry;
        C[i] = sum % BASE;
        carry = sum / BASE;
    }
}

進階方向

• FFT/NTT 加速大整數乘法（O(n log n)）
• Montgomery 模乘用於 RSA 加密
• 現成庫：GMP、OpenSSL BIGNUM、Boost.Multiprecision（C++）

掌握數組模擬大數，是理解任意精度算法的基石。