平方根倒数快速算法

一、平方根倒数算法的由来

        在制作3D游戏的时间，曲面是由许多平面构成的，要求出光线在物体外貌反射后的结果，就必要知道平面的单元法向量，法向量的长度的平方R很容易求出，单元法向量 = 坐标值 / R的平方根。电脑每次都要进行百万次如许的盘算，每次盘算节约一些时间就可以大大提高游戏的帧率。而平方根快速算法就是干这行的。

二、牛顿法

        当我们要求解2的平方根的时间，可以借助图形 

 当 y = 0的时间就可以算出2的平方根了。现在我们可以使用牛顿的迭代法，随便取一个在曲线上的点，求出该点的切线与y = 0的交点，此时他是更精确的借，将这个算法迭代几次你就可以找到一个近似解出来了。

        但是牛顿法有个问题，如果我开始随便找一个点，找了个100，那导致迭代次数许多次后才能慢慢到达一个较好的精度。但如果你开始就用1.414来盘算，你只用一次就可以算出一个理想的高精度解。

三、平方根倒数算法

        我们只用把二进制数处理一下就可以得到牛顿法必要的初始值。
        那么首先我们要了解一下，在电脑中是怎样存放二进制数的。在32位表现一个浮点数的环境下，S(1位符号位) + E(8位指数位)+M(23位尾数位)。留意尾数位指标是小数点后的数，也就是说现在的M表现0.5，加上省略的1+小数点，则表现1.5*2^E-127。 指数为如前面所述，支持正负所以要 -127。

        那么通过对数来简化指数和乘法运算。

        在式中有几个点必要提出的是
① 

 在(0,1)之间约等于x，所以直接拿下来了。

②在二进制中*2表现左移一位，所以左移E 23位后加上23位的M正好是y在盘算机中的二进制格式。

        所以我们得出结论

。
所以根据问题，我们必要知道y的平方根的倒数即：

将上述结论代入后得到：

        虽然做到这一步就挺好了，但是为了提高团体精度，我们似乎还可以把y = x向上提高一点，同时0x5f400000对应着381*2^22 ， 同时0.5*Y也可以改成Y右移一位，毕竟我们只用找到近似解就行，后面还有牛顿算法保底呢。

四、代码

1. float invSqrt(float x) {
2.         float halfx = 0.5f * x;
3.         float y = x;
4.         long i = *(long*)&y;
5.         i = 0x5f3759df - (i>>1);
6.         y = *(float*)&i;
7.         y = y * (1.5f - (halfx * y * y));
8.         return y;
9. }

复制代码

最后这个牛顿迭代的方程如下图所示来自GPT4：

参考

什么代码让程序员之神感叹“卧槽”？改变游戏行业的平方根倒数算法_哔哩哔哩_bilibili
Open source IMU and AHRS algorithms – x-io Technologies
Graphing Calculator - GeoGebra

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。