C 語言大整數相乘溢出解決：高精度乘法（字符串模擬）

問題

兩個極大整數相乘，結果超出 long long、__int128 甚至任意內置類型範圍。

解決方案：字符串模擬手算乘法

將數字以字符串/數組形式存儲，每位對應一個十進制數字，模擬豎式乘法：

// 核心邏輯：result[i+j] += a[i] * b[j] + 進位
void multiply(char *a, char *b, char *result) {
    int lenA = strlen(a), lenB = strlen(b);
    int *temp = calloc(lenA + lenB, sizeof(int));
    for (int i = lenA - 1; i >= 0; i--)
        for (int j = lenB - 1; j >= 0; j--)
            temp[i + j + 1] += (a[i] - '0') * (b[j] - '0');
    // 處理進位
    for (int k = lenA + lenB - 1; k > 0; k--) {
        temp[k - 1] += temp[k] / 10;
        temp[k] %= 10;
    }
    // 轉字符串，跳過前導零
    int idx = 0;
    for (int k = 0; k < lenA + lenB; k++)
        if (idx > 0 || temp[k] > 0) result[idx++] = temp[k] + '0';
    result[idx] = '\0';
    free(temp);
}

優化方向

• 基數改為 10⁴ 或 10⁹（每數組元素存 4/9 位），減少循環次數。
• 使用 FFT/NTT 實現 O(n log n) 乘法，適合超大整數（萬位以上）。
• 現有成熟庫：GMP (mpz_t)、OpenSSL (BIGNUM)、Boost.Multiprecision (cpp_int)。

字符串高精度乘法無理論位數限制，只受內存約束，是解決溢出的通用方法。