平方根倒数快速算法
一、平方根倒数算法的由来在制作3D游戏的时间，曲面是由许多平面构成的，要求出光线在物体外貌反射后的结果，就必要知道平面的单元法向量，法向量的长度的平方R很容易求出，单元法向量 = 坐标值 / R的平方根。电脑每次都要进行百万次如许的盘算，每次盘算节约一些时间就可以大大提高游戏的帧率。而平方根快速算法就是干这行的。
二、牛顿法
当我们要求解2的平方根的时间，可以借助图形 https://latex.csdn.net/eq?y%20%3D%20x%5E2-2 当 y = 0的时间就可以算出2的平方根了。现在我们可以使用牛顿的迭代法，随便取一个在曲线上的点，求出该点的切线与y = 0的交点，此时他是更精确的借，将这个算法迭代几次你就可以找到一个近似解出来了。
https://i-blog.csdnimg.cn/direct/724214ea4a894fd28ed2549e6951cb73.png
但是牛顿法有个问题，如果我开始随便找一个点，找了个100，那导致迭代次数许多次后才能慢慢到达一个较好的精度。但如果你开始就用1.414来盘算，你只用一次就可以算出一个理想的高精度解。
三、平方根倒数算法
我们只用把二进制数处理一下就可以得到牛顿法必要的初始值。
那么首先我们要了解一下，在电脑中是怎样存放二进制数的。在32位表现一个浮点数的环境下，S(1位符号位) + E(8位指数位)+M(23位尾数位)。留意尾数位指标是小数点后的数，也就是说现在的M表现0.5，加上省略的1+小数点，则表现1.5*2^E-127。 指数为如前面所述，支持正负所以要 -127。
https://i-blog.csdnimg.cn/direct/8a6de56116a4407990b343c32d370de1.png
那么通过对数来简化指数和乘法运算。
https://i-blog.csdnimg.cn/direct/7c4de002348c45c0a0bd7a3f323c0ce4.png
https://i-blog.csdnimg.cn/direct/dbf857e323254488919791b5d19e4cf2.png
在式中有几个点必要提出的是
① https://latex.csdn.net/eq?%5Clog%20%281+x%29 在(0,1)之间约等于x，所以直接拿下来了。
https://i-blog.csdnimg.cn/direct/147f47bb644a4d739beef84b8f22655e.png
②在二进制中*2表现左移一位，所以左移E 23位后加上23位的M正好是y在盘算机中的二进制格式。
https://i-blog.csdnimg.cn/direct/43670974a1834797a388c68e9d71e1e4.png
所以我们得出结论https://latex.csdn.net/eq?%5Clog%20y%20%3D%20%5Cfrac%7BY%7D%7B2%5E%7B%5E%2823%29%7D%7D%20-%20127。
所以根据问题，我们必要知道y的平方根的倒数即：
https://i-blog.csdnimg.cn/direct/fb68dc4df935464493b925f588c1390b.png
将上述结论代入后得到：
https://i-blog.csdnimg.cn/direct/0f7866f352fe4b5ea3caffb66b1e0b5f.png
虽然做到这一步就挺好了，但是为了提高团体精度，我们似乎还可以把y = x向上提高一点，同时0x5f400000对应着381*2^22 ， 同时0.5*Y也可以改成Y右移一位，毕竟我们只用找到近似解就行，后面还有牛顿算法保底呢。
https://i-blog.csdnimg.cn/direct/c155ad53d0bd4111b32d80fa49e058d7.png
四、代码
float invSqrt(float x) {
float halfx = 0.5f * x;
float y = x;
long i = *(long*)&y;
i = 0x5f3759df - (i>>1);
y = *(float*)&i;
y = y * (1.5f - (halfx * y * y));
return y;
} 最后这个牛顿迭代的方程如下图所示来自GPT4：
https://i-blog.csdnimg.cn/direct/cb6e863dcd1a4371a9729310c2bb2987.png
https://i-blog.csdnimg.cn/direct/f61fa3a350d141acaf59b3279e414293.png
https://i-blog.csdnimg.cn/direct/cd3b1c2bf83e47dd9423660085711886.png
参考
什么代码让程序员之神感叹“卧槽”？改变游戏行业的平方根倒数算法_哔哩哔哩_bilibili
Open source IMU and AHRS algorithms – x-io Technologies
Graphing Calculator - GeoGebra
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]