計算機如何實現“乘法”

下面分層次把乘法在數據表示 → 整數硬件/軟件 → 大整數 → 浮點數 → 特殊場景里的主流實現方式講清楚，并給出取舍建議與簡單偽代碼。

---

0）前置：數的表示

• 無符號整數：按二進制位權求值。
• 有符號整數：幾乎都用二進制補碼；負數乘法與正數一樣用同一套電路（Booth 等方法天然支持）。
• 定點數：將小數放到整數域乘法里處理（先按整數乘，再按小數位數右移對齊）。
• 浮點數（IEEE-754）：把數拆成符號 S、階碼 E、尾數/有效數 M；乘法=尾數相乘、階碼相加、符號異或，隨后規格化與舍入。

---

1）整數乘法：從“移位相加”到并行樹

1.1 順序“移位-相加”（Shift-and-Add）

最樸素、面積小，常見于極簡 MCU 或需要省門電路的場合。
思想：被乘數 A 與乘數 B，從 B 的最低位起逐位檢查；若該位為 1，就把 A 左移相應位后加到累加器里。

偽代碼

acc = 0
for i in 0..(n-1):if (B[i] == 1): acc = acc + (A << i)
return acc

• 優點：電路/代碼簡單，面積與功耗低。
• 缺點：需要 n 次迭代，延遲大（O(n)）。

1.2 Booth 乘法（Radix-2 / Radix-4 / Radix-8）

減少部分積的經典方法；對補碼有效。把乘數按“比特跑動”分組，一串 1 相當于一次加減而不是多次相加：

• Radix-2 處理 ...01（+A）與 ...10（?A）邊界；
• Radix-4 一次看兩位（含重復位），只需 ±A、±2A 四種；
• Radix-8 再擴大基數，換更多編碼表。

優點：顯著減少部分積數量→縮短后端壓縮樹深度。
取舍：更高基數=更復雜的前端編碼與部分積生成，但往往更快/更省功耗。

1.3 陣列乘法器（Array Multiplier）

把所有部分積（AND 陣列產生）規則排布，用逐行進位加法器或**進位保存加法器（CSA）**消去。

• 優點：結構規則、易布局布線（FPGA/ASIC 友好）。
• 缺點：進位傳播鏈長，速度一般。

1.4 Wallace/Dadda 壓縮樹（CSA Tree）

高性能通用解法：

1. 并行生成部分積；
2. 用 3:2 壓縮器（全加器）或 4:2 壓縮器把多位列“壓縮”為兩行（和、進位），逐層減少高度；
3. 最后交給一次**進位傳播加法器（CPA，如 CLA/Brent-Kung/Kogge-Stone）**得到結果。

• 優點：并行度高，延遲近似 O(log n)；現代 CPU/GPU/FPGA DSP 塊常用（配合 改進 Booth）。
• 缺點：面積和布線復雜度較高。

1.5 位串行 / 字串行 / 流水線

• 位串行：每拍處理 1 位，極省面積。
• 字串行：每拍處理一小段位寬。
• 深度流水線：把“部分積生成→壓縮樹→CPA”分成多級，高頻高吞吐；常見于 DSP/矩陣乘 MAC 單元。

1.6 FPGA 與 DSP Slice

FPGA 里通常有硬核 DSP 乘法器（如 18×25、27×27 等），綜合器會自動映射。大位寬乘法通過平鋪/分塊實現；可選 截斷 或 飽和 以控資源與誤差。

---

2）浮點乘法（IEEE-754）的標準流程

單次乘法 M1 × M2：

1. 符號：S = S1 XOR S2
2. 階碼：E = E1 + E2 ? Bias
3. 尾數：P = (1.M1) × (1.M2)（隱含 1）
4. 規格化：若 P ∈ [2,4) 則右移并 E++；若 <1 則左移并 E--
5. 舍入：最近偶、向零、向上、向下；用 Guard/ Round/ Sticky 位保證正確舍入
6. 特殊值：NaN、±Inf、±0、非正規數（Subnormal）；溢出/下溢標志
7. FMA（融合乘加）：a*b + c 一次完成，只舍入一次，精度與性能更優，是現代 CPU/GPU/AI 核心標配。

---

3）大整數（多精度）乘法：從小學豎式到 FFT

在密碼學/任意精度庫（GMP、OpenSSL）中，位數 n 很大，復雜度主導：

• 豎式（Schoolbook / Comba）：O(n2)，常用在小規模或分塊內核；可做緩存友好的 Comba 布局。

• Karatsuba：分治，O(n^1.585)。當 n 超閾值時快過豎式。

• Toom-Cook（Toom-3/4/…）：進一步分治，多項式插值思想。

• FFT/NTT 乘法：把乘法轉為卷積，O(n log n)。大到極致（上萬位）時采用（如 Sch?nhage-Strassen、Fürer、Harvey-Hoeven 變體）。

• 模乘（密碼學）：

  • Montgomery 乘法：把模約簡“融合”進乘法，避免顯式除法，適合固定模 N 的重復乘；
  • Barrett 約減：預計算 μ≈?b^{2k}/N? 近似除法。
  • 常數時間實現避免時序側信道。

---

4）乘以“特殊數”的優化（Strength Reduction）

• 乘以 2^k：直接算術/邏輯左移。
• 乘以常數 C：編譯器會把它分解為移位+加減（如 ×10 → (x<<3)+(x<<1)），或使用最少加法圖/加法器網絡；DSP 里常做乘法器-less FIR 濾波。
• 乘以固定小數/系數表：可用查表（LUT）或分段線性逼近，換取延遲/功耗優勢。

---

5）有限域乘法（GF(2)/GF(2^n)）

在糾錯碼、密碼（AES、GCM）里常見：

• 加法=按位 XOR；
• 乘法=按位與與移位的多項式卷積，然后對既定本原多項式取模約簡；
• 可用 Karuatsuba-like 分治、查表、組合邏輯或 LUT+移位器實現。

---

6）“乘-加”與矩陣乘：從 MAC 到張量核心

• MAC（Multiply-Accumulate）：乘法器后接累加器，是 DSP 的心臟；可做飽和/舍入。
• 向量/SIMD：一次處理多對操作數。
• 矩陣乘/卷積陣列：systolic array、張量核心（FP16/BF16/INT8/FP8），實質是大量并行的乘-加單元 + 高帶寬緩存/片上網絡。

---

7）誤差、溢出與近似乘法

• 溢出策略：補碼回繞（兩端對齊）、飽和（鉗位到最大/最小），DSP 常用飽和。
• 截斷/舍入：為省資源可截斷低位，需量化誤差評估。
• 近似乘法器：在容錯類應用（ML/多媒體）里犧牲少量精度換低功耗/更高吞吐。

---

8）何時用哪種實現？（工程取舍）

• 極簡硬件/低成本 MCU：順序移位-相加或小基數 Booth，可能位串行。
• 通用高性能 CPU/GPU/FPGA：改進 Booth + Wallace/Dadda + 快速 CPA，深度流水線；浮點優先 FMA。
• FPGA 項目：盡量吃DSP Slice，超大位寬分塊拼接；若系數常量，探索“移位+加法”。
• 大整數/密碼：選擇 Karatsuba/Toom-Cook/FFT 結合 Montgomery/Barrett，注意常數時間。
• DSP/AI：MAC 陣列、向量化/張量核，必要時做截斷/飽和/定點量化。

---

9）兩個小例子

（A）Radix-4 Booth（簡化版）

對乘數B做重疊分組：b_{i+1} b_i b_{i-1} （含1位重復）
編碼到 {0, ±1, ±2}：000/111→0, 001/010→+1, 011→+2, 100→-2, 101/110→-1
對每組選擇 {0, A, 2A, -A, -2A}，左移 2i 位后累加到 CSA 樹

（B）浮點乘法（單精度骨架）

S = S1 XOR S2
E = (E1 - Bias) + (E2 - Bias) + Bias
P = (1.M1) * (1.M2)    // 24×24 位陣列或 Booth+樹
規格化(P, E)
舍入(P, GRS, mode)
檢查 NaN/Inf/Subnormal/溢出/下溢

---