48

我并没有真正尝试优化任何东西，但我记得我一直从程序员那里听到这个，我认为这是一个事实。毕竟他们应该知道这些东西。

但我想知道为什么除法实际上比乘法慢？除法不只是一种美化的减法，而乘法是一种美化的加法吗？所以从数学上讲，我不明白为什么走一种方式或另一种方式在计算上会有非常不同的成本。

任何人都可以澄清这个原因/原因，所以我知道，而不是我从其他程序员那里听到的我之前问过的是：“因为”。

4

2 回答 2

59

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

除法算法不能高效地并行化。最有效的除法算法非常复杂（Pentium FDIV 错误展示了复杂程度）。通常，它们每比特需要更多的时钟周期。如果您想了解更多技术细节，这里有来自英特尔的一个很好的解释。英特尔实际上为他们的除法算法申请了专利。

于 2013-06-28T18:26:59.600 回答
6

但我想知道为什么除法实际上比乘法慢？除法不只是一种美化的减法，而乘法是一种美化的加法吗？

最大的区别在于，在长乘法中，您只需在移位和屏蔽后将一堆数字相加。在长除法中，您必须在每次减法后测试溢出。

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

  • 班次（没时间）
  • 掩码（恒定时间）
  • 添加（看起来时间与 n² 成正比）

但是，如果我们仔细观察，我们可以通过使用两个技巧来优化加法（还有进一步的优化，但这些是最重要的）。

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

所以现在我们的算法看起来像

  • 班次（没时间）
  • 掩码（恒定时间）
  • 将三个一组的数字相加以产生两个，直到只剩下两个（时间与 log(n) 成正比）
  • 执行最后的加法（时间与 n 成正比）

换句话说，我们可以为两个 n 位数构建一个乘法器，时间与 n 大致成正比（空间与 n² 大致成正比）。只要 CPU 设计者愿意献身，逻辑乘法几乎可以和加法一样快。

在长除法中，我们需要知道每个减法是否溢出，然后才能决定下一个使用什么输入。所以我们不能应用与长乘法相同的并行技巧。

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

于 2018-11-16T23:09:43.137 回答