大整數算法系列（十二）：有符號乘法實作——融合 Karatsuba 與 Comba

前言

前兩篇分別實作了 Comba 乘法（O(n²) 但常數極小）與 Karatsuba 乘法（O(n^1.585) 適合大數）。本篇將兩者結合，實作高效的有符號大整數乘法。

設計策略：混合閾值切換

• 當兩個乘數的位數（used）皆 ≥ KARATSUBA_MUL_CUTOFF（通常 32~64 位元）時，使用 Karatsuba 遞迴
• 否則直接使用 Comba 乘法
• 遞迴基例自然落在 Comba，避免小數遞迴開銷

核心函數 bn_mul_bn 完整實作

int bn_mul_bn(bignum *z, const bignum *x, const bignum *y) {
    int ret = 0;
    bignum ta[1], tb[1];
    bn_init(ta); bn_init(tb);

    // 1. 判斷是否走 Karatsuba
    if (BN_MIN(x->used, y->used) >= KARATSUBA_MUL_CUTOFF) {
        BN_CHECK(bn_mul_karatsuba(z, x, y));
    } else {
        // 2. Comba 路徑：處理輸出與輸入重疊 (z == x 或 z == y)
        if (x == z) { BN_CHECK(bn_copy(ta, x)); x = ta; }
        if (y == z) { BN_CHECK(bn_copy(tb, y)); y = tb; }

        // 3. 擴充結果精度並歸零
        BN_CHECK(bn_grow(z, x->used + y->used));
        BN_CHECK(bn_set_word(z, 0));
        z->used = x->used + y->used;

        // 4. 呼叫 Comba 核心
        bn_mul_comba(z, x, y);

        // 5. 設定符號：同號為正，異號為負
        z->sign = (x->sign == y->sign) ? 1 : -1;
    }

clean:
    bn_free(ta); bn_free(tb);
    return ret;
}

關鍵細節解析

1. 臨時變數 ta、tb 的必要性

Comba 乘法一開始會將 z 歸零。若呼叫端傳入 bn_mul_bn(z, z, y)（即 z = z * y），直接操作會破壞輸入值。解法：偵測別名後，先 bn_copy 到臨時變數，再讓 x/y 指向臨時變數。

2. 符號位獨立處理

Comba/Karatsuba 僅計算絕對值乘積，最後依 x->sign、y->sign 設定 z->sign。這簡化了核心乘法邏輯（只需處理非負數）。

3. 記憶體管理

bn_init 僅初始化結構體，bn_free 安全釋放（即使未分配記憶體也安全）。clean 標籤確保所有路徑都釋放資源。

效能考量

• 切換閾值 需經實測調整：太小會增加遞迴開銷，太大則失去 Karatsuba 優勢
• 原地運算：若確定無別名，可省略 bn_copy 以提升效能
• 平台優化：Comba 核心可換裝內聯組語（x86/x64/ARM）進一步加速

系列回顧與展望

至此，大整數加減乘除核心已具備：

1. Comba 乘法（基礎 O(n²) 高效實作）
2. Karatsuba 乘法（分治降低複雜度）
3. 有符號乘法整合（混合閾值、別名處理、符號管理）

下一篇將探討單精度乘法優化：為何不直接用 Comba/Karatsuba，以及專用實作技巧。