为什么乘法比除法便宜？ [英] Why is multiplying cheaper than dividing?

问题描述

我最近写了一个Vector 3类，并且我将我的normalize（）函数提交给了一个朋友。他说这很好，但是我应该尽可能乘以倒数，因为CPU时间乘除比除便宜。

I recently wrote a Vector 3 class, and I submitted my normalize() function for reviewal to a friend. He said it was good, but that I should multiply by the reciprocal where possible because "multiplying is cheaper than dividing" in CPU time.

我的问题很简单，为什么是

My question simply is, why is that?

推荐答案

从基本操作上考虑一下，硬件可以更轻松地实现基本操作-加，减，移位，比较。甚至在琐碎的设置中，乘法也需要较少的基本步骤-此外，它还提供了更快的高级算法-请参见 here ...，但是硬件通常不利用这些资源（也许是非常专业的硬件除外）。例如，如Wikipedia URL所述， Toom–Cook可以以五次N大小的乘法来进行N大小的立方乘法 –确实对于非常大的数字来说这是非常快的（Fürer算法，这是最近的一项开发，可以做Θ（n ln（n）2Θ（ln *（n）））-再次，请参见Wikipedia页面及其链接）。

Think about it in terms of elementary operations that hardware can more easily implement -- add, subtract, shift, compare. Multiplication even in a trivial setup requires fewer such elementary steps -- plus, it afford advances algorithms that are even faster -- see here for example... but hardware generally doesn't take advantage of those (except maybe extremely specialized hardware). For example, as the wikipedia URL says, "Toom–Cook can do a size-N cubed multiplication for the cost of five size-N multiplications" -- that's pretty fast indeed for very large numbers (Fürer's algorithm, a pretty recent development, can do Θ(n ln(n) 2Θ(ln*(n))) -- again, see the wikipedia page and links therefrom).

部门本质上要慢一些，再次是-每个维基百科;即使是最好的算法（其中有些是在硬件中实现的，只是因为它们远没有最好的乘法算法那么复杂和复杂；-)也无法与乘法算法相提并论。

Division's just intrisically slower, as -- again -- per wikipedia; even the best algorithms (some of which ARE implemented in HW, just because they're nowhere as sophisticated and complex as the very best algorithms for multiplication;-) can't hold a candle to the multiplication ones.

只是用不太大的数字来量化问题，下面是 gmpy ，围绕 GMP 的易于使用的Python包装器，算术的实现，但不一定是最新和最好的。在速度较慢的（第一代；-） Macbook Pro上：

Just to quantify the issue with not-so-huge numbers, here are some results with gmpy, an easy-to-use Python wrapper around GMP, which tends to have pretty good implementations of arithmetic though not necessarily the latest-and-greatest wheezes. On a slow (first-generation;-) 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

As you see, even at this small size (number of bits in the numbers), and with libraries optimized by exactly the same speed-obsessed people, multiplication by the reciprocal can save 1/3 of the time that division takes.

只有在极少数情况下，这几纳秒是一个生死攸关的问题，但是当它们是时，当然，如果您反复重复除以相同的值（以摊销 1.0 / b 的操作！），那么此知识可以挽救生命。

It may be only in rare situations that these few nanoseconds are a life-or-death issue, but, when they are, and of course IF you are repeatedly dividing by the same value (to amortize away the 1.0/b operation!), then this knowledge can be a life-saver.

（在很多方面，与 x *相比， x * x 通常可以节省时间* * 2 [在具有 ** 提高权力运算符的语言中，例如Python和Fortran] –和Horner的方案绝对比反复提高功率更可取操作！-）。

(Much in the same vein -- x*x will often save time compared to x**2 [in languages that have a ** "raise to power" operator, like Python and Fortran] -- and Horner's scheme for polynomial computation is VASTLY preferable to repeated raise-to-power operations!-).

这篇关于为什么乘法比除法便宜？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！