极客工场

Appearance

共 2,515 字预计阅读约 8 分钟

除法器原理：为什么除法又慢又贵 ​

更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」**进阶层（intermediate）**数字逻辑基础第二十七篇。加法器、乘法器都能靠并行结构做快，唯有除法至今是数据通路里最贵、最慢的基本运算。这一篇讲清它难在哪、硬件怎么做。

本文要回答的问题 ​

  • 二进制长除的「试商」在硬件上怎么落地？
  • 恢复余数法为什么要「减了再加回」？不恢复余数法省掉了什么？
  • SRT 除法凭什么能一拍跳多位，商为什么允许负数字？
  • Newton-Raphson 求倒数怎么把除法变成一连串乘法？
  • 为什么除法延迟是 O(n) 拍、CPU/FPGA 都把它当特殊操作？

一、本质：除法是一串「试商—移位—加减」 ​

乘法是同时产生 n 排部分积再压缩，可以大规模并行；除法反过来：每一位商是 0 还是 1，取决于当前余数够不够再减一次除数，而当前余数又依赖上一步的结果。这是一条环环相扣的串行依赖——不先定出高位商，就不知道下一步余数，也就定不了下一位商。因此除法天然难并行，简单结构延迟 O(n) 拍。

先看手算长除的二进制版。求 Q = N ÷ D（N 被除数、D 除数），维护一个余数寄存器 R，初始放被除数高位，从最高位起：

  1. 把被除数下一位移进 R（R 左移、补入新位）；
  2. 试着 R − D；
  3. 若结果 ≥0，说明够减，本拍商 1，保留新余数；若结果 <0，不够减，本拍商 0，余数恢复；
  4. 重复 n 次，得商 Q 和最终余数 R，满足 N = Q·D + R（R<D）。

这就是**恢复余数法（restoring）**的全部思想，和十进制竖式「这一位能上几」一模一样。

二、恢复余数 vs 不恢复余数 ​

恢复余数法有个浪费：当试减发现变负，要把 D 再加回来恢复，这一拍白做一次加法还可能多花一拍。把「加回」的账记到下一拍去，就得到不恢复余数法（non-restoring），也叫加减交替法：

  • 规则直接看当前余数符号：余数为正，商 1，下一拍做 R ← R − D；余数为负，商 0，下一拍做 R ← R + D（而不是当拍加回）；
  • 数学上等价：「这拍减过头、下拍加回来」的净效果，正好抵消恢复操作，因为移位后加 D 相当于在当前语境补回半个 D，可严格由递推式推出。
chip-design/intermediate/08-divider-basics.md D2 示意图

不恢复法每拍只需一次加/减、没有浪费的恢复动作，控制略复杂（最后若余数为负要补一次加法修正），是简单整数除法器的主流。它的「基本单元」和乘法阵列对称，可拼成除法阵列（用可控加减单元 CAS），属于面积换单拍吞吐的做法。

三、SRT：让商允许 ±1，一拍跳多位 ​

上面每拍只定 1 位商，n 位要 n 拍。SRT 除法（Sweeney–Robertson–Tocher，Pentium 著名的 FDIV bug 就出在它的查表）引入两个加速思想：

  1. 冗余商数字集：商每位不再只许 0/1，而允许 {−1,0,+1}（基 2）或基 4 的 {−2,…,+2}。因为余数有冗余，判断「够不够减」不必等余数精确值，只需知道它落在哪个粗区间——可以用余数最高几位查表决定商，且很多步直接商 0，这一步只移位、不用做加减，跳过一次运算；
  2. 高基（radix-4/8/16）：一次迭代定出多位商（radix-4 一拍 2 位），迭代次数减半/减到 1/4。查表 + 简单选择逻辑代替精确比较。

最后冗余的商数字（含 −1）再做一次进位传播转换成普通二进制（on-the-fly conversion 边算边转）。SRT 用「允许暂时不精确、用冗余换简单和并行」，和 进位保留/压缩树用冗余 3:2 表示回避进位传播是同一种哲学，是高性能 CPU 整数/浮点除法器的基础。

四、Newton-Raphson：把除法变成乘法迭代 ​

浮点除法常用另一条路：不求商，先求除数的倒数，再乘被除数。求倒数用 Newton-Raphson 迭代。对函数 f(x)=1/x − D，其根是 1/D，牛顿迭代式为：

bash
xᵢ₊₁ = xᵢ·(2 − D·xᵢ)

只要初值 x₀ 足够接近 1/D（可用一小块 ROM 查表得到），每迭代一次正确位数约翻倍（二次收敛）——一次迭代从几位精度到十几位，再一次就到全精度，只需少数几次。而每次迭代只含乘法和一个 2− 运算，因此可以直接复用数据通路里那个又大又快的乘法器，不必单独养一个 n 拍除法阵列。Goldschmidt 算法是同族的「乘到分母趋近 1」变体。代价是结果通常是近似值，要做正确舍入（IEEE 754 的最后一步修正）。

五、代价与工程取舍 ​

结构延迟面积场景
恢复/不恢复余数（移位减法）n 拍、O(n)一个加减器+寄存器，最省嵌入式、多拍除法指令、FPGA 除法 IP
除法阵列（组合 CAS 阵列）O(n) 门延迟n² 量级，大要单拍/少拍、肯花面积
SRT（基 4/8）n/k 拍查表+加减，中等高性能 CPU、FPU
Newton-Raphson/Goldschmidt几次乘法迭代（log 级精度增长）复用乘法器浮点单元、有快乘法器的机器

工程结论很直接：①除法是串行依赖链，绝不要放进每个周期都走的关键数据通路——CPU 把除法做成独立执行单元、发一条除法指令要十几二十拍，RTL 里也应把除法放多拍模块/状态机，而不是组合 q = a/b 让综合器拼出巨大组合链卡死频率；②很多算法可以预先消去除法：常量除法改成乘倒数/移位（定点 Q 格式，见 定点数基础），分母为常量时综合器也会自动转乘加移位；③FPGA 写 / 或 % 要格外小心：常量分母通常被优化成乘加，变量分母要么调多拍除法 IP、要么在高端器件用专用块，否则可能综合出占用大量 LUT 的组合除法、时序和资源双双爆炸；④取模 % 和除法是同一运算的两个输出（商与余数同时得到），一起算比分开省。

理解除法，最有价值的不是记住每种算法的接线，而是建立「依赖能否并行」的判断力：乘法的部分积彼此独立所以能压缩并行，除法的每一步都被上一步余数锁死所以只能迭代——这决定了它在硬件中的全部性格。

与现有篇目的衔接 ​

总结 ​

一句话总结：除法之所以又慢又贵，是因为每一位商都取决于当前余数够不够再减一次除数、而余数又依赖上一步结果，形成无法并行的串行依赖链，简单结构注定 O(n) 拍；它在硬件上就是二进制长除的「移位—试商—加减」迭代——恢复余数法每拍先试 R−D，为负则商 0 并把 D 加回来，不恢复余数法（加减交替）把这次加回记到下一拍，直接按余数符号决定下一步 R←R−D（余正、商 1）或 R←R+D（余负、商 0），每拍只做一次加减，是省资源多拍除法器的主流；SRT 除法用 {−1,0,+1} 乃至基 4/8 的冗余商数字，仅凭余数高位查表定商、遇到商 0 只移位不加减、一次迭代定多位，把迭代次数成倍压缩（Pentium FDIV bug 正出自其查表），末了再把冗余商转成普通二进制；Newton-Raphson 则绕开长除，用 xᵢ₊₁=xᵢ(2−Dxᵢ) 迭代求倒数，精度每次翻倍、几次即全精度，且全程只靠乘法从而能复用高速乘法器，Goldschmidt 为同族变体，代价是需做正确舍入；工程上除法不进每周期关键通路而用独立多拍单元，变量除法在 FPGA 上要走多拍 IP/专用块，常量除法应改乘倒数加移位，取模与除法是同一运算的商与余数应一并求得——学除法最大的收获是建立「依赖能否并行」的判断力：乘法部分积独立故可压缩并行，除法步步锁死故只能迭代。