为什么乘法比除法更便宜？

Question

我最近编写了一个 Vector 3 类，并将我的 normalize() 函数提交给朋友进行审查。他说它很好，但我应该在可能的情况下乘以倒数，因为“乘法比除法更便宜”。

我的问题很简单，为什么呢？

- jkeys

---

你正在处理整数还是浮点数？ - Uri

请问：在编程中，乘以逆矩阵和除以除数哪个更好？ - womp

找出答案的即时方式是问你的朋友 :P。 - Nrj

不是重复问题，因为他询问的是整数操作。其他问题是关于浮点数的。 - Thilo

Answer 1

从硬件可以更容易实现的基本操作角度来考虑-- 加、减、移位、比较。即使在简单的设置中，乘法也需要更少的这种基本步骤--而且，它提供了更快的先进算法--例如，参见这里......但是硬件通常不利用这些算法（除了可能是极其专业化的硬件）。例如，正如维基百科网址所说，“Toom-Cook可以以五个大小为N的乘法的代价进行大小为N³的乘法运算”——对于非常大的数字而言，这确实非常快（Fürer's algorithm是最近的一个比较重要的发展，可以做到Θ(n ln(n) 2Θ(ln*(n)))——同样，请参见维基百科页面及其链接）。

相比之下，除法就天生慢一些，就像维基百科所说的那样；即使是最好的算法（其中一些已经在硬件中实现），也不能与乘法算法媲美，因为它们远没有乘法算法那么复杂和精密。

只是为了量化一下非常巨大的数字的问题，这里给出了一些使用gmpy的结果，它是一个易于使用的Python封装器，用于调用GMP中相当不错的算术实现，虽然并不一定是最新和最好的技巧。在一台较慢的（第一代的 ;-) Macbook Pro上：

$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib'
1000000 loops, best of 3: 0.186 usec per loop
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b'
1000000 loops, best of 3: 0.276 usec per loop

就算是在数字位数较小的情况下，通过使用乘法逆元，可以比除法快1/3。这些库都是由追求速度的人进行了优化。

尽管这几个纳秒可能只在极少数情况下影响到程序的生死存亡，但是如果你需要重复地用相同的值做除法（以摊销掉1.0/b操作），这种技巧就能够救命。

类似的道理还有，相比于使用幂运算符（如Python和Fortran等语言中的**）来计算平方，使用x*x通常会更快。而霍纳方案（Horner's scheme）用于多项式计算时，要远比反复使用幂运算更可取！

- Alex Martelli

---

有关汇编指令的有用信息。 (http://www.agner.org/optimize/instruction_tables.pdf) - nonsensickle

Answer 2

如果你回想起小学时期，你会发现乘法比加法更难，而除法比乘法更难。对于CPU来说也是一样的。

还记得计算倒数需要进行除法运算，所以除非你计算倒数一次并使用三次，否则你不会看到速度提升。

- David Norman

---

+1 对于缓存倒数的必要性的重要评论。 - Thilo

至于小学阶段，我发现（现在仍然如此）减法比加法更难做，但对于CPU来说，这两者似乎是相同的。;-) - Thilo

@Thilo：当你需要执行减法时，只需取反第二操作数，然后你就可以执行一个“更简单”的加法了。 :-) - Laurence Gonsalves

只需使用十进制的补数！例如，对于35 - 17；要将17取反，先找出17的九进制补数，即...99982（在所有可用的最高位填充9）；再加1得到-17的十进制补数，即...99983；将00035和99983相加，像CPU一样舍弃溢出，就得到了18！好吧，借位也不那么糟糕。=P - JustJeff

Answer 3

（float）除法的CPU操作比乘法复杂得多。 CPU必须做更多工作。 我对硬件知之甚少，但您可以找到许多关于常见除法实现（例如基于newton-raphson算法）的信息。

我还要小心始终使用倒数的乘法而不是除法来获得CPU性能：它们可能无法给出完全相同的结果。 这可能重要或不重要，具体取决于您的应用程序。

- David Cournapeau