为什么乘法比划分便宜？

Question

我最近写了一个Vector 3类,并将我的normalize()函数提交给了朋友.他说它很好,但是我应该尽可能地乘以倒数,因为在CPU时间里"乘法比划分便宜".

我的问题很简单,那是为什么？

Answer 1

根据硬件可以更容易实现的基本操作来考虑它 - 加,减,移位,比较.即使在一个简单的设置中乘法也需要更少的这样的基本步骤 - 此外,它提供了更快的算法 - 例如在这里看到......但硬件通常不利用那些(除了非常专业的硬件).例如,正如维基百科网址所说,"Toom-Cook可以进行N次立方乘法以获得5次N次乘法的成本" - 这对于非常大的数字来说确实非常快(Fürer算法,一个相当近的发展,可以?(n ln(n) 2?(ln*(n)))- 再次,查看维基百科页面及其链接).

除了每个维基百科之外,分部的内部速度也很慢.即使是最好的算法(其中一些是在HW中实现的,只是因为它们无法像最好的乘法算法那样复杂和复杂;-)不能对乘法算法产生影响.

只是为了量化不那么庞大的数字的问题,这里有一些结果与gmpy,一个易于使用的GMP的 Python包装,往往有很好的算术实现,但不一定是最新和最大的喘息.在慢速(第一代;-) 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操作!),那么这个知识可以节省生命.

(与此相同的x*x是,与x**2[具有**"提升功率"运算符的语言相比,如Python和Fortran] 通常可以节省时间- 而且Horner的多项式计算方案比重复提升功率更可取操作- !).

Answer 2

如果你回想起小学,你会记得乘法比加法更难,除法比乘法更难.CPU的情况没有任何不同.

回想一下,计算倒数涉及一个除法,所以除非你计算一次倒数并使用它三次,否则你不会看到加速.