平方根倒数速算法：修订间差异

|6=zh-cn:进制; zh-hk:進制; zh-tw:進位;

}}

'''平方根倒数速算法'''（{{lang-en|Fast Inverse Square Root}}，亦常以“Fast InvSqrt()”或其使用的[[十六进制]][[常数]]'''<tt>0x5f3759df</tt>'''代称）是用于快速计算<math>\textstyle x^{-1/2}</math>（即<math>\textstyle x</math>的[[平方根]]的[[倒数]]，在此<math>\textstyle x</math>需取符合[[IEEE 754]]标准格式的32位[[浮点数]]）的一种[[算法]]。此算法最早可能是于90年代前期由[[硅谷图形公司|SGI]]所发明，后来则于1999年在《[[雷神之锤III竞技场]]》的源代码中应用，但直到2002－2003年间才在[[Usenet]]一类的公共论坛上出现<ref name="Beyond3D">{{cite web|url=http://www.beyond3d.com/content/articles/8/|title=Origin of Quake3's Fast InvSqrt()|last=Sommefeldt|first=Rys|date=2006-11-29|work=Beyond3D|accessdate=2009-02-12|language=en}}</ref>。这一算法的优势在于减少了求平方根倒数时浮点运算操作带来的巨大的[[算法#复杂度|运算耗费]]，而在[[计算机图形学]]领域，若要求取[[照明]]和[[浓淡处理|投影]]的[[波动角度]]与[[反射 (计算机图形学)|反射]]效果，就常需计算平方根倒数。

== 算法的切入点 ==

浮点数的平方根倒数常用于计算[[单位向量|正规化向量]]{{sfntag|Blinn|2003|p=130}}。3D图形程序需要使用正规化向量来实现光照和[[余弦辐射体|投影]]效果，因此每秒都需做上百万次平方根倒数运算，而在处理[[T&L|坐标转换与光源]]的专用硬件设备出现前，这些计算都由软件完成，计算速度亦相当之慢；在1990年代这段代码开发出来之时，多数浮点数操作的速度更是远远滞后于整数操作<ref name="Beyond3D" />，因而针对正规化向量算法的优化就显得尤为重要。下面陈述计算正规化向量的原理：

=== 将浮点数转化为整数 ===

{{see also|浮点数}}

要理解这段代码，首先需了解浮点数的存储格式。一个浮点数以32个二进制位表示一个[[有理数]]，而这32位由其意义分为三段：首先首位为符号位，如若是0则为正数，反之为负数；接下来的8位表示经过[[IEEE 754#指數偏移值|偏移处理]]（这是为了使之能表示-127－128）后的指数；最后23位表示的则是[[有效数字]]中除最高位以外的其余数字。将上述结构表示成公式即为<math>\textstyle x=(-1)^{\mathrm{Si}}\cdot(1+m)\cdot 2^{(E-B)}</math>，其中<math>\textstyle m</math>表示有效数字的尾数（此处<math>\textstyle 0 \le m < 1 </math>，偏移量<math>\textstyle B=127</math>{{sfntag|McEniry|2007|p=2}}，而指数的值<math>\textstyle E-B</math>决定了有效数字（在Lomont和McEniry的论文中称为“尾数”（''mantissa''））代表的是小数还是整数{{sfntag|Hennessey|1998|p=276}}。以上图为例，将描述带入有<math>\textstyle m=1\times 2^{-2}=0.250</math>），且<math>\textstyle E-B=124-127=-3</math>，则可得其表示的浮点数为<math> \textstyle x=(1+0.250)\cdot 2^{-3}=0.15625</math>。

=== 精确度 ===

如上所述，平方根倒数速算法所得的近似值惊人的精确，右图亦展示了以上述代码计算（以平方根倒数速算法计算后再进行一次牛顿法迭代）所得近似值的误差：当输入0.01时，以C语言标准库函数计算可得10.0，而InvSqrt()得值为9.9825822，其间误差为0.017479，相对误差则为0.175%，且当输入更大的数值时，绝对误差不断下降，相对误差也一直控制在一定的范围之内。

== 历史与考究 ==

《雷神之锤III》的代码直到[[QuakeCon#Qcon 2005|QuakeCon 2005]]才正式放出，但早在2002年（或2003年）时，平方根倒数速算法的代码就已经出现在[[Usenet]]与其他论坛上了<ref name="Beyond3D" />。最初人们猜测是卡马克写下了这段代码，但他在回复询问他的邮件时否定了这个观点，并猜测可能是先前曾帮id Software优化雷神之锤的资深汇编程序员Terje Mathisen写下了这段代码；而在Mathisen的邮件裡，他表示，在1990年代初，他只曾作过类似的實作，确切来说这段代码亦非他所作。现在所知的最早實作是由Gary Tarolli在SGI Indigo中實作的，但他亦坦承他仅对常数R的取值做了一定的改进，实际上他也不是作者。在向以发明[[MATLAB]]而闻名的[[克里夫·莫勒尔|Cleve Moler]]查证后，Rys Sommefeldt则认为原始的算法是{{Tsl|en|Ardent Computer}}公司的Greg Walsh所发明，但他也没有任何决定性的证据能证明这一点<ref>{{cite web|url=http://www.beyond3d.com/content/articles/15/|title=Origin of Quake3's Fast InvSqrt() - Part Two|accessdate=2008-04-19|author=Sommefeldt, Rys|date=2006-12-19|publisher=Beyond3D}}</ref>。

{{雷神之锤系列}}

[[Category:求根算法]]