Fast inverse square root
快速平方根倒数算法是一种用于快速计算的一种算法。
#include <iostream>
using namespace std;
float rsqrt(float num){
long i;
float y;
float x2 = num * 0.5F;
y = num;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
//迭代
y *= 1.5f - ( x2 * y * y );
y *= 1.5f - ( x2 * y * y );
return y;
}
int main(){
float n = 255;
cout<<rsqrt(n);
return 0;
}
0x5f375a86这个魔法数字。它来自一个传奇算法(平方根倒数速算法)，此算法最早被认为是由约翰·卡马克所发明.
但后来的调查显示，该算法在这之前就于计算机图形学的硬件与软件领域有所应用，如SGI和3dfx就曾在产品中应用此算法。
在现代的CPU里，可以使用SSE指令来加快计算。
以下程序使用了SSE指令来计算平方根倒数。GCC下的编译指令为 g++ file.cpp -o a.out -msse4 -O0
#include <iostream>
#include <x86intrin.h>
using namespace std;
inline float rsqrt(float num){
long i;
float y;
float x2 = num * 0.5F;
y = num;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
//迭代
y *= 1.5f - ( x2 * y * y );
y *= 1.5f - ( x2 * y * y );
return y;
}
inline __m128 rsqrt(__m128 num){
return _mm_rsqrt_ps(num);
}
int main(){
float a = 14.64525;
//SSE
__m128 m_a = _mm_set_ps1(a);
m_a = rsqrt(m_a);
cout<<"SSE\t" << m_a[0]<<endl;
//Normal
cout<<"Normal\t" <<rsqrt(a)<<endl;
return 0;
}