大整數運算核心算法：任意精度乘法的數組模擬實現

算法核心思想

將大整數按十進制位拆分存入數組（低位在高下標），模擬手工豎式乘法：

1. 每位乘以乘數，結果暫存原位
2. 從低位向高位處理進位：arr[i-1] += arr[i] / 10; arr[i] %= 10

C# 參考實現

static int[] Multiply(int[] digits, int multiplier) {
    // 逐位相乘
    for (int i = 0; i < digits.Length; i++)
        digits[i] *= multiplier;
    
    // 統一進位處理（從個位向高位）
    for (int i = digits.Length - 1; i > 0; i--) {
        digits[i - 1] += digits[i] / 10;
        digits[i] %= 10;
    }
    return digits;
}

關鍵工程細節

• 數組方向：低位存高下標（digits[Length-1] 為個位），便於進位向低下標傳播
• 前導零處理：輸出時跳過高位連續零
• 擴容策略：乘法可能增加位數，預留足夠空間或動態擴容
• 負數支持：符號分離，絕對值運算後加符號

擴展：加法、除法、快速冪

/* 加法：對齊低位，逐位相加進位 */
static int[] Add(int[] a, int[] b) { ... }

/* 除法：試商法，從高位向低位 */
static int[] Divide(int[] dividend, int divisor, out int remainder) { ... }

/* 快速冪：二進制分解指數 */
static int[] Pow(int[] base, int exp) { ... }

性能優化方向

1. 基數升級：改用 10⁴ 或 2³² 為基，減少數組長度
2. FFT 乘法：極大整數（萬位以上）採用 Schönhage-Strassen 算法 O(n log n) 3. 原地運算：減少內存分配，復用緩衝區