更快的开方倒数运算

题图无关 pixiv_id=42768956

问题始于与 @Xiami@Ream 两位菊苣舍友的讨论。

开方运算在编程过程之中是一个常见的运算,而开方倒数作为其衍生物,也被广泛使用着。

对于一般的开方运算,一般采用牛顿逼近法来求出计算值。对于 c\c++,一般使用 a / sqrt(b) 就好了,其 sqrt() 的底层实现是 FSQRT,对于 Python,建议使用 a / math.sqrt(b),这个方法就是 c 语言 sqrt() 的映射(对于CPython),相对于 a / b**.5 的方法,性能更好一些(实验见此戳我)。

那有没有“更快的开方倒数运算”呢?

参考 crashworks 的文章,查了一下指令集,发现 Intel 的指令集 里有 SQRTSS 一条指令,从精度和性能上都略优越于 FSQRT

1
2
3
4
__m128 tmp = _mm_load_ss(&b);
tmp = _mm_sqrt_ss(tmp);
_mm_store_ss(&b, tmp);
ret = a / b;

还有没有更快的呢?

1999 年的《Quake III Arena》源码公布后,有一段利用魔法数 0x5f3759df 计算开方倒数的神奇函数,是一段开方倒数的近似算法,示例剥离了C语言预处理器的指令,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}

简单点解释的话,该算法可以通过利用将浮点数直接转化为长整型的数据,利用数学方法构成一个线性方程,而魔法数,这里是 0x5f3759df,则提供一次运算的精度。

更具体的解释可以看这篇文档

还有没有更好的?

Intel 从硬件上支持了上一条的近似算法,即指令 RSQRTSS,文档见此

1
2
3
4
__m128 tmp = _mm_load_ss(&b);
tmp = _mm_rsqrt_ss(tmp);
_mm_store_ss(&b, tmp);
ret = a * b;

根据 crashworks 的文章 所说,RSQRTSS 差不多比 FSQRT 快近一个数量级,那么即使用 RSQRTSS 来计算开方值,也算是加速不少了。

评论