大整數算法系列（十一）：Karatsuba 乘法原理與實作詳解

動機：打破 O(n²) 的瓶頸

Comba 乘法雖常數小，但時間複雜度仍為 O(n²)。當位數達到數千位以上，耗時急劇增長。Karatsuba 以**分治法**將複雜度降至 O(n^log₂3) ≈ O(n^1.585)。

數學原理

設兩大整數 X、Y，以基底 B 切成高低兩半：

X = X₁·B + X₀
Y = Y₁·B + Y₀

乘積：

Z = X·Y = X₁Y₁·B² + (X₁Y₀ + X₀Y₁)·B + X₀Y₀

直接計算需 4 次半大小乘法。Karatsuba 觀察到：

X₁Y₀ + X₀Y₁ = (X₁ + X₀)(Y₁ + Y₀) - X₁Y₁ - X₀Y₀

只需 **3 次** 半大小乘法（X₁Y₁、X₀Y₀、(X₁+X₀)(Y₁+Y₀)）加上若干加減法與位移。

遞迴複雜度分析

T(n) = 3·T(n/2) + O(n)   →   T(n) = O(n^log₂3) ≈ O(n^1.585)

優於 O(n²)，但遞迴開銷使小數反而較慢。

實作關鍵步驟

1. 切分點：B = min(x.used, y.used) / 2
2. 拆分高低半部：複製位元到臨時 bignum
3. 三次遞迴乘法：x0y0、x1y1、(x0+x1)(y0+y1)
4. 計算中間項：mid = (x0+x1)(y0+y1) - x0y0 - x1y1
5. 合併結果：z = x0y0 + (mid << B) + (x1y1 << 2B)

核心代碼片段

static int bn_mul_karatsuba(bignum *z, const bignum *x, const bignum *y) {
    size_t B = BN_MIN(x->used, y->used) >> 1; // 切分點
    bignum x0, x1, y0, y1, t1, x0y0, x1y1;
    // ... 初始化並複製高低半部 ...

    bn_mul_bn(x0y0, &x0, &y0);           // 遞迴
    bn_mul_bn(x1y1, &x1, &y1);
    bn_add_abs(&t1, &x0, &x1);           // x0+x1
    bn_add_abs(&x0, &y0, &y1);           // 復用 x0 空間存 y0+y1
    bn_mul_bn(&t1, &x0, &t1);            // (x0+x1)(y0+y1)

    bn_add_abs(&x0, x0y0, x1y1);         // x0y0 + x1y1
    bn_sub_abs(&t1, &t1, &x0);           // mid = (x0+x1)(y0+y1) - x0y0 - x1y1
    bn_lshd(&t1, B);                     // mid << B
    bn_lshd(x1y1, B << 1);               // x1y1 << 2B
    bn_add_abs(&t1, x0y0, &t1);          // x0y0 + mid
    bn_add_abs(z, &t1, x1y1);            // 最終結果

    // 清理臨時變數
    return 0;
}

切換閾值 KARATSUBA_MUL_CUTOFF

• 32 位元基底：通常 32~64 位
• 64 位元基底：通常 16~32 位
• 實測調整：太小增加遞迴開銷，太大失去優勢

延伸：Toom-Cook 與 FFT 乘法

實務上，密碼學常用 2048~4096 位，Karatsuba + Comba 混合已足夠。

1. 上一篇文章： C 語言函數呼叫參數入棧順序：x86 vs x64、呼叫慣例深度解析
2. 下一篇文章： C 語言合法識別字判斷：規則解析與 OJ 題解

關於C語言

C語言實作：學生程式設計成績統計系統（總分、平均、標準差、最高最低分）

學生成績統計完整實作 本程式模擬某小組 C++ 程式設計課程

C# 圖形中級篇啟動：需求分析與架構設計（第六講·序）

系列定位 「C# 發現之旅」專為 Web 資料庫開發者設計，

C# 型別系統核心：值型別 vs 參考型別、裝箱與拆箱機制圖解

兩大型別分類 值型別：內建基本型別（char、in

C# 開發 WPF/Silverlight 動畫與遊戲教學 (42-1)：打造通用 ChildWindow 控件 (上)

遊戲通用懸浮視窗控件設計與實現 RPG、SLG、養成類遊戲大