|
1/sqrt(x)在许多计算领域都是非常常用的，例如3D计算中的向量正规化等等。本文给出一个神奇的快速求1/sqrt(x)的程序。 今天做优化声音分离程序的工作，发现其中求复数的模的倒数的计算数量相当大，于是就在网上找时候有比1/sqrt(x)更快的方法，还真让我找到了。采用这个优化算法之后，程序运行时间从14秒提升到了10秒，效果还是相当惊人的。那么让我们来看看这个程序吧。
float InvSqrt(float x){
float xhalf=0.5f*x;
long i=*(long*)&x;
i=0x5f3759df - (i>>1);
x=*(float *)&i;
x=x*(1.5f-xhalf*x*x);
return x;
}
倒数第二行的x=x*(1.5f-xhalf*x*x);是牛顿迭代法，这个在一般的数值计算的书中都能找到，关键是它计算初期迭代值的方法比较奇特，使得 只需要一次迭代就足够精确了，当然如果想要更加精确的结果的话，就多来一次迭代即可。它直接把浮点转换为整形来计算，还出现了一个神奇的数： 0x5f3759df，这个数字是加快算法的核心。它是怎么算出来的呢，在网络上搜索一下这个数字吧。原来这段程序是著名的游戏Quake 3的一个函数。介绍这个算法的文章可以在 下载。这篇文章从理论上分析了0x5f3759df的来历，并且提出了一个更加精确的数：0x5f375a86。如果各位有耐心的话不妨看看他的求解过程，写得很精彩，有时间的话真想把它翻译成中文。
|
