快速平方根倒数算法常数

❶ 平方根倒数速算法的算法的切入点

浮点数的平方根倒数常用于计算正规化矢量。 3D图形程序需要使用正规化矢量来实现光照和投影效果，因此每秒都需做上百万次平方根倒数运算，而在处理坐标转换与光源的专用硬件设备出现前，这些计算都由软件完成，计算速度亦相当之慢；在1990年代这段代码开发出来之时，多数浮点数操作的速度更是远远滞后于整数操作，因而针对正规化矢量算法的优化就显得尤为重要。下面陈述计算正规化矢量的原理：
要将一个矢量标准化，就必须计算其欧几里得范数以求得矢量长度，而这时就需对矢量的各分量的平方和求平方根；而当求取到其长度并以之除该矢量的每个分量后，所得的新矢量就是与原矢量同向的单位矢量，若以公式表示： 可求得矢量v的欧几里得范数，此算法正类如对欧几里得空间的两点求取其欧几里得距离， 而求得的就是标准化的矢量，若以代表，则有， 可见标准化矢量时需要用到对矢量分量的平方根倒数计算，所以对平方根倒数计算算法的优化对计算正规化矢量也大有裨益。
为了加速图像处理单元计算，《雷神之锤III竞技场》使用了平方根倒数速算法，而后来采用现场可编程逻辑门阵列的顶点着色器也应用了此算法。

❷ 平方根倒数速算法的历史与考究

《雷神之锤III》的代码直到QuakeCon 2005才正式放出，但早在2002年（或2003年）时平方根倒数速算法的代码就已经出现在Usenet与其他论坛上了。最初人们猜测是卡马克写下了这段代码，但他在询问邮件的回复中否定了这个观点，并猜测可能是先前曾帮id Software优化雷神之锤的资深汇编程序员Terje Mathisen写下了这段代码；而在Mathisen的邮件里他表示在1990年代初他只曾作过类似的实现，确切来说这段代码亦非他所作。现在所知的最早实现是由Gary Tarilli在SGI Indigo中实现的，但他亦坦承他仅对常数R的取值做了一定的改进，实际上他也不是作者。Rys Sommefeldt则在向以发明MATLAB而闻名的Cleve Moler查证后认为原始的算法是Ardent Computer公司的Greg Walsh所发明，但他也没有任何决定性的证据能证明这一点。
目前不仅该算法的原作者不明，人们也仍无法明确当初选择这个“魔术数字”的方法。Chris Lomont在研究中曾做了个试验：他编写了一个函数，以在一个范围内遍历选取R值的方式将逼近误差降到最小，以此方法他计算出了线性近似的最优R值0x5f37642f（与代码中使用的0x5f3759df相当接近），但以之代入算法计算并进行一次牛顿迭代后，所得近似值与代入0x5f3759df的结果相比精度却仍略微更低；而后Lomont将目标改为遍历选取在进行1－2次牛顿迭代后能得到最大精度的R值，并由此算出最优R值为0x5f375a86，以此值代入算法并进行牛顿迭代后所得的结果都比代入原始值（0x5f3759df）更精确，于是他的论文最后以“原始常数是以数学推导还是以反复试错的方式求得”的问题作结。在论文中Lomont亦指出64位的IEEE754浮点数（即双精度类型）所对应的魔术数字是0x5fe6ec85e7de30da，但后来的研究表明代入0x5fe6eb50c7aa19f9的结果精确度更高（McEniry得出的结果则是0x5FE6EB50C7B537AA，精度介于两者之间）。在Charles McEniry的论文中，他使用了一种类似Lomont但更复杂的方法来优化R值：他最开始使用穷举搜索法，所得结果与Lomont相同；而后他尝试用带权二分法寻找最优值，所得结果恰是代码中所使用的魔术数字0x5f3759df，因此McEniry确信这一常数或许最初便是以“在可容忍误差范围内使用二分法”的方式求得。

❸ 平方根的倒数用c语言怎么表示

平方根的倒数用c语言用double sqrt(double)表示。

C语言中平方根的函数是：double sqrt(double)；参数介绍：（）中是double，返回值可能是double 也可能是int；该函数头文件：math.h；该函数功能： 计算一个非负实数的平方根；说明：sqrt系Square Root Calculations（平方根计算），通过这种运算可以考验CPU的浮点能力。

结论：

被开方数越大，对应的算术平方根也越大（对所有正数都成立）。一个正数如果有平方根，那么必定有两个，它们互为相反数。显然，如果知道了这两个平方根的一个，那么就可以及时的根据相反数的概念得到它的另一个平方根。

❹ 平方根的倒数怎么算呀

解：通项：1/(√n) （其中n>0）
分子，分母同时乘以√n,即：
1/(√n) = （√n) /[（√n)*（√n)]=（√n)/n(即n分之根号下n的意思)

因此像平方根3的倒数就是√3/3 （3分之根号下3）,不知你明白了没？

❺ 算术平方根的算法

数的开方是一种运算，一个正数有两个平方根，这两个平方根互为相反数，记作
，零的平方根是零，负数没有平方根。正数a的正的平方根，也叫做a的算术平方根，记作
，零的算术平方根仍旧是零，也就是在算术平方根的记号
中，a可以是正数，也可以是零，即a为非负数，平方根与算术平方根有相似之处，容易混淆，它们的相同点是被开方数都必须是非负数，并且零的平方根与算术平方根都是零，当a表示正数时，只要求出a的算术平方根
，便可知a的负平方根
，因此，可马上求出a的平方根，但它们又有本质的区别，正数a的平方根为
，是正负两个值，而算术平方根是两个值中的正值
，即算术平方根是一个非负数。

❻ 《微微一笑很倾城》中肖奈大神说的平方根倒数速算法是什么鬼

平方根倒数速算法

平方根倒数速算法是适用于快速计算（积的平方根的倒数，在此需取符合IEEE 754标准格式的32位浮点数）的一种算法。

平方根倒数速算法（英语：Fast Inverse Square Root，亦常以“Fast InvSqrt()”或其使用的十六进制常数0x5f3759df代称）是用于快速计算（积的平方根的倒数，在此需取符合IEEE 754标准格式的32位浮点数）的一种算法。此算法最早可能是于90年代前期由SGI所发明，后来则于1999年在《雷神之锤III竞技场》的源代码中应用，但直到2002－2003年间才在Usenet一类的公共论坛上出现。这一算法的优势在于减少了求平方根倒数时浮点运算操作带来的巨大的运算耗费，而在计算机图形学领域，若要求取照明和投影的波动角度与反射效果，就常需计算平方根倒数。

此算法首先接收一个32位带符浮点数，然后将之作为一个32位整数看待，以将其向右进行一次逻辑移位的方式将之取半，并用十六进制“魔术数字”0x5f3759df减之，如此即可得对输入的浮点数的平方根倒数的首次近似值；而后重新将其作为浮点数，以牛顿法反复迭代，以求出更精确的近似值，直至求出符合精确度要求的近似值。在计算浮点数的平方根倒数的同一精度的近似值时，此算法比直接使用浮点数除法要快四倍。

中文名

平方根倒数速算法

外文名

Fast Inverse Square Root

定义

适用于快速计算的一种算法

备注

最早被认为由约翰·卡马克所发明

❼ 平方根倒数速算法的注释

由于现代计算机系统对长整型的定义有所差异，使用长整型会降低此段代码的可移植性。具体来说，由此段浮点转换为长整型的定义可知，如若这段代码正常运行，所在系统的长整型长度应为4字节（32位），否则重新转为浮点数时可能会变成负数；而由于C99标准的广泛应用，在现今多数64位计算机系统（除使用LLP64数据模型的Windows外）中，长整型的长度都是8字节。 此处“浮点数”所指为标准化浮点数，也即有效数字部分必须满足，可参见David Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys. 1991.March, 23 (1): 5–48. doi:10.1145/103162.103163. Lomont 2003确定R的方式则有所不同，他先将R分解为与，其中与分别代表R的有效数字域和指数域。

❽ 怎么计算某数的平方根

如果一个数的开方是无理数. 直接就用：

如√20即简写，不必具体写出该数.

平方根就是开二次方运算的值. 它的逆运算就是乘二次方.

//
// 计算参数x的平方根的倒数
//
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1); // 计算第一个近似根
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x); // 牛顿迭代法
return x;
}
该算法的本质其实就是牛顿迭代法（Newton-Raphson Method，简称NR），而NR的基础则是泰勒级数（Taylor Series）。NR是一种求方程的近似根的方法。首先要估计一个与方程的根比较靠近的数值，然后根据公式推算下一个更加近似的数值，不断重复直到可以获得满意的精度。其公式如下：

函数：y=f(x)

其一阶导数为：y'=f'(x)

则方程：f(x)=0 的第n+1个近似根为

x[n+1] = x[n] - f(x[n]) / f'(x[n])
NR最关键的地方在于估计第一个近似根。如果该近似根与真根足够靠近的话，那么只需要少数几次迭代，就可以得到满意的解。

现在回过头来看看如何利用牛顿法来解决我们的问题。求平方根的倒数，实际就是求方程1/(x^2)-a=0的解。将该方程按牛顿迭代法的公式展开为：

x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])
将1/2放到括号里面，就得到了上面那个函数的倒数第二行。

接着，我们要设法估计第一个近似根。这也是上面的函数最神奇的地方。它通过某种方法算出了一个与真根非常接近的近似根，因此它只需要使用一次迭代过程就获得了较满意的解。它是怎样做到的呢？所有的奥妙就在于这一行：

i = 0x5f3759df - (i >> 1); // 计算第一个近似根
超级莫名其妙的语句，不是吗？但仔细想一下的话，还是可以理解的。我们知道，IEEE标准下，float类型的数据在32位系统上是这样表示的（大体来说就是这样，但省略了很多细节，有兴趣可以GOOGLE）：

bits：31 30 ... 0
31：符号位
30-23：共8位，保存指数（E）
22-0：共23位，保存尾数（M）
所以，32位的浮点数用十进制实数表示就是：M*2^E。开根然后倒数就是：M^(-1/2)*2^(-E/2)。现在就 十分清晰了。语句i>>1其工作就是将指数除以2，实现2^(E/2)的部分。而前面用一个常数减去它，目的就是得到M^(1/2)同时反转所有指数的符号。

至于那个0x5f3759df，呃，我只能说，的确是一个超级的Magic Number。

那 个Magic Number是可以推导出来的，但我并不打算在这里讨论，因为实在太繁琐了。简单来说，其原理如下：因为IEEE的浮点数中，尾数M省略了最前面的1，所以实际的尾数是1+M。如果你在大学上数学课没有打瞌睡的话，那么当你看到(1+M)^(-1/2)这样的形式时，应该会马上联想的到它的泰勒级数展开， 而该展开式的第一项就是常数。下面给出简单的推导过程：

对于实数R>0，假设其在IEEE的浮点表示中，
指数为E，尾数为M，则：

R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)

将(1+M)^(-1/2)按泰勒级数展开，取第一项，得：

原式
= (1-M/2) * 2^(-E/2)
= 2^(-E/2) - (M/2) * 2^(-E/2)

如果不考虑指数的符号的话，
(M/2)*2^(E/2)正是(R>>1)，
而在IEEE表示中，指数的符号只需简单地加上一个偏移即可，
而式子的前半部分刚好是个常数，所以原式可以转化为：

原式 = C - (M/2)*2^(E/2) = C - (R>>1)，其中C为常数

所以只需要解方程：
R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)
= C - (R>>1)
求出令到相对误差最小的C值就可以了

上面的推导过程只是我个人的理解，并未得到证实。而Chris Lomont则在他的论文中详细讨论了最后那个方程的解法，并尝试在实际的机器上寻找最佳的常数C。有兴趣的朋友可以在文末找到他的论文的链接。

所以，所谓的Magic Number，并不是从N元宇宙的某个星系由于时空扭曲而掉到地球上的，而是几百年前就有的数学理论。只要熟悉NR和泰勒级数，你我同样有能力作出类似的优化。

在GameDev.net上有人做过测试，该函数的相对误差约为0.177585%，速度比C标准库的sqrt提高超过20%。如果增加一次迭代过程，相对误差可以降低到e-004 的级数，但速度也会降到和sqrt差不多。据说在DOOM3中，Carmack通过查找表进一步优化了该算法，精度近乎完美，而且速度也比原版提高了一截（正在努力弄源码，谁有发我一份）。

值得注意的是，在Chris Lomont的演算中，理论上最优秀的常数（精度最高）是0x5f37642f，并且在实际测试中，如果只使用一次迭代的话，其效果也是最好的。但奇怪的是，经过两次NR后，在该常数下解的精度将降低得非常厉害（天知道是怎么回事！）。经过实际的测试，Chris Lomont认为，最优秀的常数是0x5f375a86。如果换成64位的double版本的话，算法还是一样的，而最优常数则为0x5fe6ec85e7de30da（又一个令人冒汗的Magic Number - -b）。

这个算法依赖于浮点数的内部表示和字节顺序，所以是不具移植性的。如果放到Mac上跑就会挂掉。如果想具备可移植性，还是乖乖用sqrt好了。但算法思想是通用的。大家可以尝试推算一下相应的平方根算法。

下面给出Carmack在QUAKE3中使用的平方根算法。Carmack已经将QUAKE3的所有源代码捐给开源了，所以大家可以放心使用，不用担心会收到律师信。

//
// Carmack在QUAKE3中使用的计算平方根的函数
//
float CarmSqrt(float x){
union{
int intPart;
float floatPart;
} convertor;
union{
int intPart;
float floatPart;
} convertor2;
convertor.floatPart = x;
convertor2.floatPart = x;
convertor.intPart = 0x1FBCF800 + (convertor.intPart >> 1);
convertor2.intPart = 0x5f3759df - (convertor2.intPart >> 1);
return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
}
另一个基于同样算法的更高速度的sqrt实现如下。其只是简单地将指数除以2，并没有考虑尾数的方根。要看懂该代码的话必 须知道，在IEEE浮点数的格式中，E是由实际的指数加127得到的。例如，如果实数是0.1234*2^10，在浮点表示中，E（第23-30位）的值其实为10+127=137。所以下面的代码中，要处理127偏移，这就是常数0x3f800000的作用。我没实际测试过该函数，所以对其优劣无从评 论，但估计其精度应该会降低很多。

float Faster_Sqrtf(float f)
{
float result;
_asm
{
mov eax, f
sub eax, 0x3f800000
sar eax, 1
add eax, 0x3f800000
mov result, eax
}
return result;
}
除了基于NR的方法外，其他常见的快速算法还有多项式逼近。下面的函数取自《3D游戏编程大师技巧》，它使用一个多项式来近似替代原来的长度方程，但我搞不清楚作者使用的公式是怎么推导出来的（如果你知道的话请告诉我，谢谢）。

//
// 这个函数计算从(0,0)到(x,y)的距离，相对误差为3.5%
//
int FastDistance2D(int x, int y)
{
x = abs(x);
y = abs(y);
int mn = MIN(x,y);
return(x+y-(mn>>1)-(mn>>2)+(mn>>4));
}
//
// 该函数计算(0,0,0)到(x,y,z)的距离，相对误差为8%
//
float FastDistance3D(float fx, float fy, float fz)
{
int temp;
int x,y,z;
// 确保所有的值为正
x = int(fabs(fx) * 1024);
y = int(fabs(fy) * 1024);
z = int(fabs(fz) * 1024);
// 排序
if (y < x) SWAP(x,y,temp)
if (z < y) SWAP(y,z,temp)
if (y < x) SWAP(x,y,temp)
int dist = (z + 11 * (y >> 5) + (x >> 2) );
return((float)(dist >> 10));
}
还有一种方法称为Distance Estimates（距离评估？），如下图所示：

红线所描绘的正八边形上的点为：

octagon(x,y) = min((1/√2) * (|x|+|y|), max(|x|,|y|))
求出向量v1和v2的长度，则：

√(x^2+y^2) = (|v1|+|v2|)/2 * octagon(x,y)
到目前为止我们都在讨论浮点数的方根算法，接下来轮到整数的方根算法。也许有人认为对整型数据求方根无任何意义，因为会得 到类似99^(1/2)=9的结果。通常情况下确实是这样，但当我们使用定点数的时候（定点数仍然被应用在很多系统上面，例如任天堂的GBA之类的手持设备），整数的方根算法就显得非常重要。对整数开平方的算法如下。我并不打算在这讨论它（事实是我也没有仔细考究，因为在短期内都不会用到- -b），但你可以在文末James Ulery的论文中找到非常详细的推导过程。

//
// 为了阅读的需要，我在下面的宏定义中添加了换行符
//
#define step(shift)
if((0x40000000l >> shift) + sqrtVal <= val)
{
val -= (0x40000000l >> shift) + sqrtVal;
sqrtVal = (sqrtVal >> 1) | (0x40000000l >> shift);
}
else
{
sqrtVal = sqrtVal >> 1;
}
//
// 计算32位整数的平方根
//
int32 xxgluSqrtFx(int32 val)
{
// Note: This fast square root function
// only works with an even Q_FACTOR
int32 sqrtVal = 0;
step(0);
step(2);
step(4);
step(6);
step(8);
step(10);
step(12);
step(14);
step(16);
step(18);
step(20);
step(22);
step(24);
step(26);
step(28);
step(30);
if(sqrtVal < val)
{
++sqrtVal;
}
sqrtVal <<= (Q_FACTOR)/2;
return(sqrtVal);
}

❾ 平方根倒数速算法的介绍

平方根倒数速算法最早被认为是由约翰·卡马克所发明，但后来的调查显示，该算法在这之前就于计算机图形学的硬件与软件领域有所应用，如SGI和3dfx就曾在产品中应用此算法。而就现在所知，此算法最早由Gary Tarolli在SGI Indigo的开发中使用。虽说在随后的相关研究中也提出了一些可能的来源，但至今为止仍未能确切知晓此常数的起源。

❿ 平方根倒数速算法的将浮点数转化为整数

要理解这段代码，首先需了解浮点数的存储格式。一个浮点数以32个二进制位表示一个有理数，而这32位由其意义分为三段：首先首位为符号位，如若是0则为正数，反之为负数；接下来的8位表示经过偏移处理（这是为了使之能表示-127－128）后的指数；最后23位表示的则是有效数字中除最高位以外的其余数字。将上述结构表示成公式即为，其中表示有效数字的尾数（此处，偏移量，而指数的值决定了有效数字（在Lomont和McEniry的论文中称为“尾数”（mantissa））代表的是小数还是整数。以上图为例，将描述带入有），且，则可得其表示的浮点数为。 符号位 0 1 1 1 1 1 1 1 = 127 0 0 0 0 0 0 1 0 = 2 0 0 0 0 0 0 0 1 = 1 0 0 0 0 0 0 0 0 = 0 1 1 1 1 1 1 1 1 = −1 1 1 1 1 1 1 1 0 = −2 1 0 0 0 0 0 0 1 = −127 1 0 0 0 0 0 0 0 = −128 8位二进制整数补码示例
如上所述，一个有符号正整数在二进制补码系统中的表示中首位为0，而后面的各位则用于表示其数值。将浮点数取别名存储为整数时，该整数的数值即为，其中E表示指数，M表示有效数字；若以上图为例，图中样例若作为浮点数看待有，，则易知其转化而得的整数型号数值为。由于平方根倒数函数仅能处理正数，因此浮点数的符号位（即如上的Si）必为0，而这就保证了转换所得的有符号整数也必为正数。以上转换就为后面的计算带来了可行性，之后的第一步操作（逻辑右移一位）即是使该数的长整形式被2所除。