我们找到了各种各样的技巧来替换std::sqrt
(Timing Square Root),也找到了一些技巧来替换std::exp
(Using Faster Exponential Approximation),但我找不到任何技巧来替换std::log
。
它是我的程序中循环的一部分,它被多次调用,虽然exp和sqrt已经过优化,但英特尔VTune现在建议我优化std::log
,在此之后,似乎只有我的设计选择会受到限制。
现在我使用ln(1+x)
的三阶泰勒近似,其中x
在-0.5
和+0.5
之间(90%的情况下最大误差为4%),否则回到std::log
。这给了我15%的加速。
7条答案
按热度按时间ghg1uchk1#
在开始设计和部署超越函数的自定义实现以提高性能之前,最好在算法级别以及通过工具链进行优化。遗憾的是,我们没有关于要优化的代码的任何信息,也没有关于工具链的信息。
在算法层面,检查是否所有超越函数的调用都是真正必要的。也许有一个数学变换需要更少的函数调用,或者将超越函数转换为代数运算。是否有任何超越函数调用可能是多余的,例如,因为计算不必要地在对数空间内外切换?如果精度要求不高,整个计算是否可以使用
float
而不是double
以单精度执行?在大多数硬件平台上,避免double
计算可以显著提高性能。编译器倾向于提供各种开关,这些开关会影响数字密集型代码的性能。除了将常规优化级别提高到
-O3
之外,通常还有一种方法可以关闭非规格化支持,即打开刷新为零或FTZ模式。这在各种硬件平台上都有性能优势。此外,通常会有一个“快速数学”标志,使用该标志会略微降低精度,并消除处理特殊情况(如NaN和无穷大)以及处理errno
的开销。一些编译器还支持代码的自动矢量化,并附带SIMD数学库,例如Intel编译器。对数函数的定制实现通常涉及将二进制浮点自变量
x
分离成指数e
和尾数m
,使得x = m * 2
e
,因此log(x) = log(2) * e + log(m)
.m
被选择为使得其接近1,因为这提供了有效的近似,例如log(m) = log(1+f) = log1p(f)
乘以minimax polynomial approximation。C++提供了
frexp()
函数来将浮点操作数分离成尾数和指数,但实际上通常使用更快的机器专用方法,通过将浮点数据重新解释为相同大小的整数,在位级处理浮点数据。下面的单精度对数logf()
代码演示了这两种变体。函数__int_as_float()
和__float_as_int()
提供了将int32_t
重新解释为IEEE-754binary32
浮点数的功能,反之亦然。此代码严重依赖于融合乘法-在大多数当前处理器、CPU或GPU上的硬件中直接支持加法操作FMA。在fmaf()
Map到软件仿真的平台上,此代码将非常慢。如代码注解中所述,上述实现提供了忠实舍入的单精度结果,并且其处理与IEEE-754浮点标准一致的异常情况。通过消除对特殊情况的支持、消除对非规格化自变量的支持以及降低精度,可以进一步提高性能。这导致以下示例性变体:
wsewodh22#
看一下this的讨论,公认的答案是基于Zeckendorf分解计算对数的函数的implementation。
在实现文件的注解中有一个关于复杂度的讨论和一些达到O(1)的技巧。
希望这对你有帮助!
vom3gejh3#
yacmzcpb4#
我矢量化了@njuffa的答案。自然对数,适用于AVX 2:
xwbd5t1u5#
我也需要一个快速的对数近似,到目前为止,最好的一个似乎是一个基于Ankerls算法。
说明:http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/
代码(复制自):
只是一个减法和乘法。它是令人惊讶的好和无与伦比的快。
zqry0prt6#
精度和性能略有提高:
虽然它有被认为是慢操作的除法,但有许多操作可以由处理器并行执行。
mfpqipee7#
这取决于你需要的精确度。通常,log被调用来得到数字的大小,你可以通过检查浮点数的指数字段来免费地得到。这也是你的第一近似。我会在我的书《基本算法》中插入一个插件,这本书解释了如何从第一原理实现标准库数学函数。