卡马克的求平方根的倒数的程序(快速平方根倒数算法).docVIP

卡马克的求平方根的倒数的程序（快速平方根倒数算法） 2009-09-18 10:45:01| 分类： HYPERLINK /blog/#m=0t=1c=fks_087064085087088067087085080095083086088068085081080068离奇的code | 标签： |字号大中小 订阅 这个程序，大概在2006年看到的，当时进行了分析，主要分析了位运算那部分：如何利用浮点数的位表示法快速计算一个近似值。而对于整个迭代计算原理并没有仔细看，今天再重新分析一下，并把当时那部分分析写的更明了些。 原贴如下：---------------------------------------------------------------------------------------------------------- 发信人: interma ( 4PZP | 抓紧时间 | OFG P ), 信区: C_Cpp标 题: [zz] 源自Quake3的快速求InvSqrt()函数发信站: 兵马俑BBS (Mon Dec 4 13:11:36 2006), 本站() HYPERLINK /article.pl?sid=06/12/04/0210205from=rss/article.pl?sid=06/12/04/0210205from=rss 人们很早就在Quake3源代码中发现了如下的C代码，它可以快速的求1/sqrt(x)，在3D图形向量计算方面应用很广。float InvSqrt(float x){ float xhalf=0.5f*x; long i=*(long*)x; i=0x5f3759df - (i1); x=*(float *)i; x=x*(1.5f-xhalf*x*x); return x;}Beyond3D.com的Ryszard Sommefeldt一直在想到底是哪个家伙写了这些神奇的代码？2003年Chris Lomont还写了一篇文章（PDF)对这些代码进行了分析。毫无疑问写出这些代码的人绝对是天才。 是John Carmack？Michael Abrash？John Carmack在邮件回复中明确表示不是他，也不是Michael，可能是Terje Matheson。于是侦探Ryszard又向Terje Mathisen寻求答案。Terje说他写过类似的高效代码，但上面的不是。他猜测可能在MIT的旧文档中可以找到。Ryszard的求证之路显然无止境。 ☆──────────────────────────────────────☆  phylips 于 Tue Dec 5 10:04:42 2006 提到： 分析了一下，关于计算过程还是可以理解的 但是关于其中的数学依据，只能看出一部分 主要思想利用了浮点数的表示法，ieee的标准 其中关键部分是  long i=*(long*)x;  i=0x5f3759df - (i1);  x=*(float *)i; 其他地方都比较简单，这三句的意思，应当是把x的浮点表示格式直接看出long类型的， 然后进行0x5f3759df - (i1)运算，之后再直接把long类型的看成float类型的。其中 的数学道理，我大致看了下 对于浮点数的表示，在ieee里float类型是按照符号.指数.尾数格式进行的 其中符号位1位，指数位8位，尾数23位，先只考虑了指数部分， long i=*(long*)x是把浮点数看成了与他具有相同位格式的long型数 i=0x5f3759df - (i1) 对于0x5f3759df如果看成浮点数的话，其指数位为(0101)(1111)0-1011111=190 设原来的xIEEE表示的指数位为a则新的结果的指数位变成了190-a/2；注意如果要转换成 m*2^n格式，需要将指数a-127；所以得到的新结果用数学表示的指数位为190-a/2-127= 63-a/2 而x的原来如果从ieee格式变成数学表示应为a-127 比较63-a/2与a-127 可以看出指数之间的关系为63-a/2==（a-127)*(-1/2) 所以经过上述三句，x应该已经是1/sqrt(x)的近似值 然后下面的应该是继续进行了精化，具体依据还没搞懂 【 在 interma ( 4PZP | 抓紧时间 | OFG P ) 的大作中提到: 】 ☆──────────────────────────────────────☆  xiao