是否可以滚动明显更快的sqrt版本

Question

在我正在分析的应用程序中,我发现在某些情况下,此功能可以占用总执行时间的10%.

我已经看到多年来使用偷偷摸摸的浮点技巧进行了更快的sqrt实现的讨论,但我不知道现代CPU上是否有这样的东西已经过时了.

正在使用MSVC++ 2008编译器,以供参考......虽然我认为sqrt不会增加太多开销.

有关modf函数的类似讨论,另请参见此处.

编辑:作为参考,这是一种广泛使用的方法,但它实际上更快？这些天SQRT有多少个周期？

Answer 1

是的,即使没有欺骗也有可能:

1)牺牲速度的准确性:sqrt算法是迭代的,以较少的迭代重新实现.

2)查找表:要么只是迭代的起点,要么与插值相结合,一直到达那里.

3)缓存:你总是在使用相同的有限值集吗？如果是这样,缓存可以很好地工作.我发现这在图形应用程序中非常有用,其中对于大量相同大小的形状计算相同的东西,因此可以有效地缓存结果.

Answer 2

这里有一个很好的比较表:http: //assemblyrequired.crashworks.org/timing-square-root/

长话短说,SSE2的ssqrts比FPU fsqrt快约2倍,并且近似+迭代比这快4倍(整体8倍).

此外,如果您正在尝试采用单精度sqrt,请确保实际上是您获得的.我听说至少有一个编译器将float参数转换为double,调用双精度sqrt,然后转换回float.

Answer 3

通过更改算法而不是通过更改实现,您很可能获得更多的速度提升:尝试减少呼叫sqrt()而不是更快地拨打电话.(如果您认为这是不可能的 - sqrt()您提到的改进就是:用于计算平方根的算法的改进.)

由于它经常被使用,因此标准库的实现很可能sqrt()对于一般情况而言几乎是最佳的.除非你有一个受限制的域(例如,如果你需要更少的精度),算法可以采取一些快捷方式,所以不太可能有人想出一个更快的实现.

请注意,由于该函数使用了10%的执行时间,即使您设法实现仅占用75%时间的实现std::sqrt(),这仍然只会使执行时间减少2.5%.对于大多数应用程序,用户甚至不会注意到这一点,除非他们使用手表进行测量.