题图无关 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 来计算开方值，也算是加速不少了。