为什么除法比乘法更昂贵？

Question

我并不是真的想要优化任何东西,但我记得我一直都是从程序员那里听到的,我把它当作一个真理.毕竟他们应该知道这些东西.

但我想知道为什么除法实际上比乘法慢？分裂只是一个美化的减法,乘法是一个美化的加法吗？所以在数学上我不明白为什么一种方式或另一种方式在计算上有非常不同的成本.

任何人都可以澄清这个的原因/原因所以我知道,而不是我从其他程序员那里听到的,我之前询问的是:"因为".

Answer 1

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

除法算法无法有效并行化.最有效的划分算法非常复杂(Pentium FDIV错误证明了复杂程度).通常,它们每位需要更多的时钟周期.如果你需要更多的技术细节,这是英特尔的一个很好的解释.英特尔实际上专利的除法算法.

Answer 2

但是我不知道为什么除法实际上比乘法慢？除法不仅是光荣的减法，而乘法是光荣的加法吗？

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

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

• 转移（无时间）
• 面罩（恒定时间）
• 加（看起来像时间与n²成正比）

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

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

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

• 转移（无时间）
• 面罩（恒定时间）
• 以三个为一组的数字相加产生两个，直到只剩下两个（时间与log（n）成比例）
• 执行最后的加法（与n成正比的时间）

换句话说，我们可以在时间上为两个n位数字建立一个与n大致成比例的乘数（而空间与n²大致成比例）。只要CPU设计人员愿意献身于逻辑乘法，它的速度几乎可以与加法一样快。

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

有些除法比基本的长除法快，但比乘法慢。