为什么除法比乘法更耗费资源？

Question

我并不是真的在努力优化什么，但我记得程序员经常这样说，我把它看作是真理。毕竟他们应该知道这些东西。

但我想知道为什么除法比乘法慢？难道除法不只是加法减法的升级版吗？所以从数学上讲，我不明白为什么沿着一个方向或另一个方向计算会有非常不同的计算成本。

请有人解释一下原因或导致这种现象的原因，让我明白，而不是像之前问过的其他程序员那样说：“因为”。

- Joan Venge

---

也许你会惊讶于大多数人不知道的事情，毕竟他们应该知道这些东西。 - David

您需要询问一位电子工程师，这是一个电路设计问题。制作硬件乘法器相当容易，但制作硬件除法器则不然。实际的除法电路是迭代的，因此需要更长的时间。请在electronics.stackexchange.com上咨询。 - Hans Passant

维基百科（参见FLOPS文章）和其他来源（http://en.community.dell.com/techcenter/high-performance-computing/w/wiki/2329.aspx）声称，典型的CPU可以在每个时钟周期内执行4个浮点运算。这似乎与类型无关。因此，除法的代价与乘法相同。谁愿意做一个基准测试？ - Axel Kemper

简而言之：商估计和校正步骤。 - Brett Hale

你说得对，乘法可以分解为多个加法操作，而除法则可以分解为多个减法操作。不同之处在于，乘法中的加法可以并行处理，而除法中必须等到前一个减法完成并进行比较后才能进行下一个减法。因此，硬件乘法器会利用这种内在的并行性，在同时计算和累加许多子乘积的同时增加芯片面积成本。而除法则无法享受这种优势。 - Mysticial

Answer 1

CPU的ALU（算术逻辑单元）执行算法，尽管它们是在硬件中实现的。经典的乘法算法包括Wallace树和Dadda树。更多信息可在此处获取。新型处理器提供了更复杂的技术。通常，处理器致力于并行化位对操作，以便最小化所需的时钟周期。乘法算法可以相当有效地并行化（尽管需要更多的晶体管）。

除法算法无法被并行化地高效执行。最有效的除法算法相当复杂（奔腾FDIV缺陷展示了其复杂程度）。通常，它们需要更多的时钟周期来处理每一位。如果您想了解更多技术细节，这里是Intel提供的一个不错的解释。事实上，Intel还申请了专利保护他们的除法算法。

- Lior Kogan

Answer 2

我在想为什么除法比乘法慢呢？难道除法不只是一种华丽的减法，而乘法则是一种华丽的加法吗？

区别在于，在长乘法中，你只需要在移位和遮掩后加上一堆数字。在长除法中，每次相减后都必须测试是否溢出。

让我们考虑两个n位二进制数的长乘积。

- 移位（无时间） - 遮盖（常数时间） - 加法（朴素地看起来与n²成正比的时间）

但是，如果我们仔细看，就会发现我们可以通过使用两个技巧来优化加法（还有更多的优化，但这些是最重要的）。

1. 我们可以按组添加数字，而不是按顺序添加。 2. 直到最后一步，我们可以添加三个数字以产生两个数字，而不是添加两个数字以产生一个数字。当添加两个数字以产生一个数字需要时间与n成正比时，添加三个数字以产生两个数字可以在常数时间内完成，因为我们可以消除进位链。

因此，现在我们的算法看起来像这样：

- 移位（无时间） - 遮盖（常数时间） - 添加以三个数字为一组，以生成两个数字，直到只剩下两个（时间与log(n)成正比） - 执行最后一个加法（时间与n成正比）

换句话说，我们可以在大约与n成正比的时间内构建两个n位数字的乘法器（空间大约与n²成正比）。只要CPU设计师愿意投入逻辑，乘法就可以几乎和加法一样快。

在长除法中，我们需要知道每次相减是否溢出，然后才能决定下一步使用什么输入。因此，我们不能像在长乘法中那样应用相同的并行化技巧。

虽然有比基本长除法更快的除法方法，但它们仍然比乘法慢。

- plugwash