乘除法的优化

本章为进阶内容，零基础读者可以跳过，不影响后续阅读。

复习

1. 第十五章：设计完成了乘法器，本质是逐位相乘、移位、相加
2. 第十六章：设计完成了除法器，本质是一位一位地试减

TL;DR

• 朴素的乘除法在位数多、数据“刚好最坏“时会很慢
• 乘法优化：Booth 算法（把连续 1 变成减法）、华莱士树（并行压缩部分积）
• 除法优化：不恢复余数法（用加法修正，省去恢复步骤）

正文

慢在哪里

　　第十三、十四章里那套乘除法，原理都对，但都很“老实“：

• 乘法：乘数每一位为 1，就要加一次。如果乘数是 1111 1111，64 位里全是 1，就得加 64 次
• 除法：每次试商都要真减一次；不够减，还得把余数恢复回去

　　位数一多，这些“老实“的做法就拖后腿了。这一章看看工程师们怎么优化它们。

乘法的优化一：Booth 算法

　　Booth 算法的聪明之处在于：把一串连续的 1，换成一次减法。

　　比如 1111（十进制 15），可以看成 10000 - 1（16 - 1）。这样，原本要加 4 次的连加，变成“加一次、减一次“，只动两步。

　　推广开来，对乘数里任意一段连续的 1，都可以只在它的开始处减一次、结束处加一次，中间那串 1 就全被“消化“掉了。

　　具体判断规则：从低到高扫描乘数的每一位，看它和前一位（相邻位）的关系：

　　为什么是“右移“？因为逐位相乘时，低位一旦算完就不受高位影响，可以右移“挤掉“，让部分积和被乘数对齐，直接参与运算。减被乘数时，用第十一、十二章的补码加法即可。

　　Booth 算法对补码特别友好：它天然就能处理带符号数，不需要额外把操作数转成绝对值。

乘法的优化二：华莱士树

　　普通做法是“一个部分积、一个部分积地累加“，加法器一级一级串起来，延迟很大。

　　华莱士树换了个思路：把一大堆部分积用进位保存加法器成对地、并行地压缩，像锦标赛一样一层层把数量减半，最后再做一次普通加法。这样级联的深度大幅减小，速度更快。它比较复杂，本指南不展开。

除法的优化：恢复余数法 vs 不恢复余数法

　　第十六章那种“减了发现不够、再恢复“的做法，叫恢复余数法：

• 每次试商后，如果不能减，就把余数恢复原样
• 实现简单，但多做了一次“恢复“，效率较低

　　改进的办法叫不恢复余数法：

• 试商时先减了再说。如果结果是负的（说明其实不够减），下一步不去恢复，而是在后续用加法把它“补“回来
• 省掉了恢复步骤，速度更快，代价是控制电路更复杂一点

　　一句话总结：恢复余数法是“做错了就撤回“，不恢复余数法是“将错就错，下一步再修正“。

思考题

　　Booth 算法对乘数里的 1111 很有优势，那它对 0101 这样的乘数有优势吗？为什么？

小结

知识点

• 朴素乘除法在位数多时变慢的原因
• Booth 算法：连续 1 化为减法
• 华莱士树：并行压缩部分积
• 恢复余数法与不恢复余数法

参考资料

1. Wikipedia(zh)：Booth 算法：一种优化的乘法算法
2. Wikipedia(zh)：华莱士树：用于快速计算部分积的方法
3. Wikipedia(zh)：长除法：恢复余数法与非恢复余数法

思考题答案（仅供参考）

　　优势不大。Booth 算法擅长的是“连续 1“，而 0101 里的 1 是零散的，并没有可以合并的长串，所以加减次数和朴素做法差不多。它真正的收益出现在乘数里“连续 1 很多“的场合。这也说明：没有万能的优化，工具要挑场合用。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪