C++ 高精度大整數乘除法實現（支持 10000 位）

前言

標準整數類型（long long 等）無法滿足超大整數運算需求。本文提供一套基於十進制數組模擬的高精度乘除法實現，支持 10000 位 整數運算，適合競賽、教學與嵌入式場景。

核心設計思路

數據表示

• 字符串輸入 → 逆序存儲於 int[]，每元素存 1 位（0-9）
• 低位在數組低索引，便於進位傳播
• 符號單獨處理，運算核心僅處理絕對值

關鍵函數架構

// 字符串轉數組（乘法用：逆序）
int turn(char s[], int num[]);

// 字符串轉數組（除法用：正序）
int turn2(char s[], int num[]);

// 核心乘法：模擬豎式乘法 + 即時進位
void mul(int *a, int *b, int *c, int len1, int len2);

// 大小比較：供除法試商使用
int cmp(int *a, int *b, int len1, int len2);

// 核心除法：模擬長除法 + 試商回溯
void div(int *a, int *b1, int *c, int len1, int len2);

乘法算法詳解

模擬豎式乘法

void mul(int *a, int *b, int *c, int len1, int len2) {
    for (int i = 0; i < len1; ++i) {
        for (int j = 0; j < len2; ++j) {
            c[i + j] += a[i] * b[j];           // 累加部分積
            if (c[i + j] >= 10) {              // 即時進位
                c[i + j + 1] += c[i + j] / 10;
                c[i + j] %= 10;
            }
        }
    }
}

複雜度：O(n²)，n 為位數。10000 位約 10⁸ 次操作，現代 CPU 毫秒級完成。

除法算法詳解

長除法 + 試商優化

核心邏輯：對被除數從高位向低位迭代，每步確定商的一位。

void div(int *a, int *b1, int *c, int len1, int len2) {
    for (int i = 1; i <= len1; ++i) {           // 處理被除數前 i 位
        for (int j = 1; ; ++j) {                // 試商 1~9
            // 構造 b1 * j 到暫存數組 chb
            // 比較 a[0..i-1] 與 chb
            if (a[0..i-1] <= chb) break;        // 找到最大商 j
        }
        c[i-1] = (a == chb) ? j : j-1;          // 確定商位
        // 被除數減去 除數 * 商位，處理借位
    }
}

關鍵優化點

• 線性試商：j 從 1 遞增至 9，利用上輪商作為下輪起始值可進一步優化
• 就地修改被除數：a 數組在循環中逐步縮減為餘數，節省空間
• 進位/借位統一處理：乘法進位、除法借位均用統一循環修正

完整導出接口

// 乘法：c = a * b
HIGHPRECDLL_API void Multiply(char* a, char* b, char* c);

// 除法：c = a / b（整數除法，截尾）
HIGHPRECDLL_API void Division(char* a, char* b, char* c);

特殊情況處理

• 零值檢測："0"、"-0" 直接返回 "0"
• 除零保護：返回 "Error"
• 符號運算：異號結果加負號，同號為正
• 前導零裁剪：結果最高位非零定位

性能與擴展建議

總結

• 十進制數組模擬是最直觀、可移植的高精度基礎實現
• 乘法 O(n²)、除法 O(n²) 滿足萬位級需求
• 代碼結構清晰，便於移植到無標準庫環境（嵌入式、內核）
• 進階場景建議接入成熟庫（GMP、Boost.Multiprecision）

完整代碼已包含邊界處理、符號邏輯、DLL 導出封裝，可直接集成項目。