8

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

我的问题很简单，为什么会这样？

4

3 回答 3

10

考虑一下硬件可以更容易实现的基本操作——加法、减法、移位、比较。即使在微不足道的设置中，乘法也需要更少的基本步骤——此外，它提供了更快的高级算法——例如，参见这里……但硬件通常不会利用这些（除了可能非常专业的硬件）。例如，正如 wikipedia URL 所说，“Toom–Cook 可以做一个大小为 N 的三次乘法，成本为五次大小为 N 的乘法”——这对于非常大的数字来说确实非常快（Fürer 的算法，一个相当新的发展，可以做Θ(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相比，通常会节省时间——而且霍纳的多项式计算方案比重复提升权力更可取操作！-)。x**2**

于 2009-07-13T04:26:49.873 回答
6

如果你回想小学，你会记得乘法比加法更难，除法比乘法更难。CPU 的情况并没有什么不同。

还记得计算倒数涉及除法，因此除非您计算倒数一次并使用它三次，否则您不会看到加速。

于 2009-07-13T04:30:03.907 回答
0

（浮点）除法的 CPU 操作比乘法复杂得多。CPU 必须做的更多。我对硬件知之甚少，但您可以找到很多关于通用除法实现的信息（例如，基于牛顿-拉夫森算法）。

我也会小心使用倒数的乘法而不是除法来获得 CPU 性能：它们可能不会给出完全相同的结果。根据您的应用程序，这可能会或可能无关紧要。

于 2009-07-13T04:22:11.487 回答