大數運算演算法詳解：以 C# 實作大整數乘法為例

問題背景

標準整數型別（int/long）範圍有限。大數運算將數字拆解為位元組/十進位陣列，模擬手算過程實現任意精度運算。

核心思想：模擬豎式乘法

    5 0 3 7  (被乘數，低位在右)
  ×     4 8  (乘數)
  ----------
    4 0 2 9 6  (×8)
  2 0 1 4 8 0  (×40，左移一位)
  ----------
  2 4 1 7 7 6

陣列儲存策略

• 陣列索引 0 為最高位，或索引 0 為最低位（兩種慣例皆可）
• 範例採用：arr[99] 為個位，arr[98] 為十位...（低位在高索引）
• 優點：進位自然向低索引傳遞，符合直覺

完整 C# 實作解析

using System;

namespace 大數 {
    class Program {
        static void Main(string[] args) {
            int[] arr = new int[100];
            // 初始化：5037 存為 ... 5,0,3,7 (arr[96]=5, arr[97]=0, arr[98]=3, arr[99]=7)
            arr[99] = 5;   // 這裡範例似乎有誤，應為 7
            arr[98] = 0;
            arr[97] = 3;
            arr[96] = 7;
            // 正確應為：arr[99]=7, arr[98]=3, arr[97]=0, arr[96]=5 代表 5037
            
            Opration(arr, 48);
            
            for (int i = 0; i < arr.Length; i++)
                Console.Write(arr[i]);
            Console.ReadKey();
        }
        
        static int[] Opration(int[] arr, int num) {
            // 步驟 1：每位乘以 num
            for (int i = 0; i < arr.Length; i++) {
                arr[i] *= num;
            }
            
            // 步驟 2：從低位向高位處理進位
            for (int i = arr.Length - 1; i > 0; i--) {
                arr[i - 1] += arr[i] / 10;  // 進位給高位
                arr[i] = arr[i] % 10;       // 保留當前位
            }
            return arr;
        }
    }
}

關鍵邏輯修正與優化

1. 初始化順序：範例註解與賦值不符，正確對應關係：

   數字 5037 → arr[96]=5, arr[97]=0, arr[98]=3, arr[99]=7 (高位在低索引)

2. 進位迴圈方向：`for (i = len-1; i > 0; i--)` 從最低位（高索引）向最高位（低索引）處理，正確
3. 最高位溢位：`i=0` 時不處理進位，若最高位產生進位會丟失。需擴展陣列或檢查 `arr[0] >= 10`

改良版：支援任意大整數乘法

static List Multiply(List num1, List num2) {
    // num1, num2 低位在前 (index 0 = 個位)
    List result = new List(new int[num1.Count + num2.Count]);
    
    for (int i = 0; i < num1.Count; i++) {
        int carry = 0;
        for (int j = 0; j < num2.Count; j++) {
            int mul = num1[i] * num2[j] + result[i+j] + carry;
            result[i+j] = mul % 10;
            carry = mul / 10;
        }
        result[i + num2.Count] = carry;
    }
    
    // 移除前導零
    while (result.Count > 1 && result[result.Count-1] == 0)
        result.RemoveAt(result.Count-1);
    return result;
}

大數運算完整體系

實務應用場景

• 密碼學：RSA 大質數運算、橢圓曲線加密
• 科學計算：高精度常數（π、e）、金融利息精確計算
• 競程題目：階乘大數、斐波那契大數、組合數計算
• 區塊鏈：256-bit 整數運算

主流語言支援

• Python：內建 `int` 任意精度
• Java：`BigInteger`, `BigDecimal`
• C++：Boost.Multiprecision / GMP
• C#：.NET Core 2.1+ `System.Numerics.BigInteger`
• Go：`math/big`
• JavaScript：`BigInt` (ES2020)

理解大數運算底層邏輯，有助於在無內建支援環境下實作，也能更深入理解電腦如何處理超越硬體位寬的數值。