计算机如何实现“乘法”

下面分层次把乘法在数据表示 → 整数硬件/软件 → 大整数 → 浮点数 → 特殊场景里的主流实现方式讲清楚，并给出取舍建议与简单伪代码。

---

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(n²)，常用在小规模或分块内核；可做缓存友好的 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/溢出/下溢

---