左耳听风_014_13_魔数_0x5f3759df
你好，我是陈浩网名猪耳朵耗子。
在开始之前呢，我先提醒一下，那这节课呢会出现很多的代码和计算公式。
所以推荐你打开文章，配合着音频进行学习。
不然啊，你大概率理解不了。
那好，我们现在正式开始。
首先呢我们来看一下文中的这段代码啊，这个函数的源代码来自一九九九年发布的一个游戏啊，雷神之锤三竞技场。
那其实呢最早在零二年到零三年的时候呢，这段平方根倒数速算法的代码就已经出现在u net和其他论坛上了。
并且啊也在程序员的圈子里引起了热烈的讨论。
那我把这段代码贴在文章里面了，我刚开始读这样代码的时候啊，是完全读不懂，尤其是那个魔法数字，一个十六进制的数五f三七五九DF,根本不知道它是什么意思。
那同样啊源代码的注释里面也标记了world fuck.那今天这节课呢，我主要啊就是想带你来了解一下这个函数中的代码究竟是怎么写出来的那其实这个函数的作用呢就是求平方根的倒数，也就是x的负二分之一次方，或者是根号下x分之一。
那当然它算出来的是一个坐标值，只不过这个近似值的精度很高，而且计算成本呢也比传统的浮点数计算平方根的算法低太多。
在以前那个计算资源还不是很充足的年代里呢，一些三d游戏场景的计算机图形学中啊，如果你要获得照明和投影的光照和反射效果，就经常需要计算平方根的倒数。
而且啊经常要对一个曲面上很多的点做平方根的倒数。
所以呢会有大量的计算。
那这个时候呢，我们就需要用到一个算式儿，也就是根号下x平方加y平方加z平方再求倒数。
那其中的XYZ呢分别是三d坐标上的一个点的三个坐标值。
那基本上来说呢，在一个三d游戏里，我们每秒钟啊都需要做上百万次的平方根，倒数的运算。
在计算硬件还不是很成熟的时代啊，这些计算啊都需要用软件来完成。
所以计算速度非常慢。
我们要知道啊，在上个世纪九十年代，大多数浮点数的操作速度啊更是远远落后于整数操作。
所以这段代码带来的作用啊是非常大的那为了讲清楚这段代码呢，我们需要先了解一下计算机的浮点数表示法。
那在c语言中呢，计算机的浮点数表示啊用的是i triple e七五四标准。
那这个标准的表现形式呢，其实就是把三十二个比特位分成三段。
第一段占一个比特，表示符号位代称为s也就是sin,第二段呢占八个。
比特位表示指数代称为e,也就是exponent.呃，第三段呢占剩下的二十三个比特位，表示尾数代称为m也就是曼梯。
那然后呢一个小数就是用文章中这个公式来计算出来的。
也就是说我先求负一的s次幂，再乘上一加上m除以二的二十三次幂，再乘上二的e减去一百二十七次幂。
那这样呢我就可以用三十二个比特位把一个小数表示出来啊，但是呢这个公式基本上来说啊就是让人一头雾水。
I triple e里面对于浮点数的解释啊，基本上就是我教你怎么画一匹马。
那我第一步呢先画两个圈，第二步呢再画四小腿，第三步再画上点。
最后呢我把徐悲鸿画的马拍到你面前，说再加一点细节啊，你就可以画成这样子了啊，就很让人摸不着门路。
所以接下来呢让我来尝试解释一下浮点数的这三段都表示什么意思。
所以第一段是符号位，这对于这一段呢，我相信大家都应该理解。
那第二段是指数位，什么叫指数位呢？也就是说对于任何一个数字x我都可以找到一个n让x啊处于二的n次幂和二的n加一次幂之间。
比如我假设x等于n因为三在二和四之间，所以这里的n啊等于一。
而浮点数的这个指数位啊，要表示小数n需要小于零，所以需要有负数。
这八个比特位本来可以表示零到二百五十五啊，但是为了表示负的取值要放在负的一百二十七到正的一百二十八这个闭区间中。
所以这就是为什么在上面的公式中啊，有二的表示一百二十七次幂这一项了。
也就是说n等于e减去一百二十七。
那如果n等于一呢，那么e啊就是一百二十八了。
第三二呢是尾数尾，也就是小数位，但是这里呢叫偏移量可能更好一些。
而这里的取值呢是在零到二的二十三次方之间。
你可以认为我们把一条线啊分成二的二十三次方个线段，也就是说八百多万条线段。
也就是说对于任何一个n我都可以把二的n次幂到二的n加一次幂分成八百多万个线段。
而这个m值的意思呢，就是说我从二的n次幂到x需要经过多少条线段。
那这就需要计算一下二的n次幂到x的长度，占二的n次幂到二的加一次次幂的长度度的例例是多少。
我估计你对第三段还是有点不懂。
那那我我们举举个例，比比说对对，三点四这个小数，而以呢呢它是正数，所以符号位s等于零。
最后呢三点一四在二的一次幂和二的二次幂之间，所以呢n等于一，也就说一减减一百二十七等等于。
所以呢三点一次等等于一百十八八，最后三点点一四减去二除以四减去二等于零点五七，而零点五七乘以二的二十三次幂等于四七八一五零六点五六。
那四舍五入之后呢，就得到了一个尾数m等于四七八一五零七。
因为呢这里有一个四舍五入，所以呢就产生了浮点数精度的问题。
然后呢，我把符号位s指数e尾数m都转成二进制的数，那就得到了三点一四到二进制表示我们再用i triple e七五四的那个算式来反算一下。
我们把SE和m都代入进去，计算之后呢，会发现结果啊会比三点一四稍微大一点，得到了三点一四零零零零幺零四等等。
哎，你看浮点数的精度问题啊就出现了。
然后我们再来看另外一个例子，一个小数零点零一五其先呢它是正数，所以呢符号位s等于零。
其次呢零点零一五在二的负七次幂到二的负六次幂之间。
所以呢n等于负七，因为n加一百二十七等于一百二十，所以啊指数为e等于一百二十。
最后呢零点零一五减去二的负七次幂，再除以二的负六次幂，减去二的负七次幂等于零点九二。
而零点九二乘以二的二三次幂等于七七幺七五幺九点三六。
那四舍五入之后呢，就得到了m等于七七幺七五幺九。
于是呢我们同样得到了零点零一五的二进制编码。
那文中呢也有相应的编码表示图，我们再把SE和m都带入公式来反算一下。
会发现啊结果又比零点一五小一点，得到了零点一四九九九九九六。
你看啊浮点数的精度问题啊又出现了。
我们可以用c语言的代码来验证一下这个问题，再用mac的LDB工具调试一下。
你会发现啊，从结果上完全验证了我们的刚刚的分析。
好了，不知道你听懂了没有啊，我相信啊你应该是听懂了。
那接下来呢，因为那个浮点数的表示的公式有点复杂，所以我们简化一下。
那可以得到一个简化后的公式，我们让公式中的小m是就样m除以二的二十三次幂，再让小e呢等于大e减去二百三次幂。
因为我们要计算平方根的倒数数，就就是y等于x的二分之一次次幂。
所以呢等号两边一定都是正数，所以以符号啊也可以去掉掉。
那这样浮点数的算式就简化为一，加上m再乘以二的一次幂。
那通过这个算式呢，我们就可以从一个三十二个比特币的二进制啊计算出一个浮点数。
所以呢这个三十二位数对应的整形数字的算式啊，是m加上e乘以二的二十三次幂，比如零点零一五呃对应的三十二个比特位，它对应的整形再通过上面的算式啊，就能得到一个十六进制的数三c七五c二八f.然后呢，我们再来讲一下平方根倒数公式的推导啊，接下来呢会有好多数学公式，但是你千万不要害怕，因为这些数学公式啊只需要高中数学就能看懂。
首先呢我们来看一下平方根倒数的公式，也就是y等于根号下x分之一，也就是x的负二分之一次幂。
那等式两边呢取以二为底的对数呢，就得到了以二为底y的对数，等于负二分之一乘上以二为底x的对数。
因为我们实际上在算浮点数，所以我们把公式中的x啊和y分别用浮点数的那个简化算式，一加上m乘以二的一次幂替换掉。
那代入这个公式中呢，我们就得到了另外一个公式，也就是以二为底，一加上MY的对数，再加上EY等于负二分之一乘上。
以二为底加上MX的对数，再加上EX啊，因为有对数啊，这公式看着就很麻烦，但是呢我们可以对它做一些简化。
我在文章中呢列出了具体的简化和推导过程。
我假设这两个三十二位浮点数x和y对应的整型数字呢是IX和IY.那最终呢就得到另一个等式，IY约等于一个常数r减去二分之一倍的IX.如果你想了解具体的细节呢，建议你回到文章中阅读。
那接下来呢我们回到这节课的主题，也就是那个平方根倒数的代码。
首先呢看一下被注射了evil, floating point比level l hiking king这行。
那那行代代码的作用呢，就是把一个浮点数的三十二进制比特位转成整型。
那假如说我要取三零一四的平方根，倒数那三点一四对应的三十二位二进制转换成整型呢是一零七八五二三三三幺。
如以代码里的y啊等于三点一四，i呢等于一零七八五二三三三幺。
然后呢，再看被注射的world, fuck这一行代码，也就是i等于零叉五七三七五九DF减去i向右移一位。
我们都知道i向右偏移一位呢就是i除以二。
呃，所以呢这个就对应了我们上面推导出来的那个公式，也就是IY约等于一个常数r减去二分之一的IX.这里面的常数r呢就等于这个十六进制数，五f三七五六DF.那这个数啊是个神奇的数字，它是怎么算出来的，到现在都没有人知道。
不过呢我们先继续往下看后面这段代码做的事情啊，实际上对应的另一个公式，也就是IY撇等于IY乘以一点五减去零点五倍的x再乘以IY的平方。
那它实际上是一个牛顿求根法，呃，这是一个通过不断逼近的手段去寻找FX等于零的一个根的这么一个计算方式。
就像文中这里的函数图像表示的一样。
首先呢初始值为x零，然后呢我就找到x零所对应的y零，然后我在x零和y零这个点上做一个切线，得到了与x轴交汇的x一。
然后我再用x一再做一次同样的迭代，得到x二。
那就这样一直迭代下去，一直找到y零。
那x的值啊就就是我们想要的结果。
那通过牛顿法的通用公式啊，我们最终得到了YN加一等于YN乘以一点五减去零点五倍的x再乘以YN的平方。
那正好就是我们刚才的代码。
所以这段代码的整体逻辑啊，就是我先从一个浮点数的二进制啊生成一个整数。
对这个整数操作产生第一个近似值之后呢，将这个近似值作为参数送到函数，最后两句进行精化处理。
那代码中的两次迭代啊，主要是为了进一步提高精度。
但是因为雷神之锤三的图形计算中啊并不需要太高的精度，所以代码只进行了一次迭代，第二次迭代的代码就被注释掉了。
下面呢我讲一下与这段代码相关的一些历史。
根据维基百科上的描述呢，雷神之锤三的代码直到二零零五年的亏抗才正式的放了出来。
但是早在二零零二年到零三年的时候呢，这段频分跟倒数速算法的代码就已经出现在US net和其他论坛上面了。
那一开始呢大家都猜测这段代码是雷神之锤的创始人jon尔kmark写下的。
但是他后来在邮件里否认了这个观点，同时呢，猜测这个可能是之前曾经帮忙优化雷神之锤的这么一个资深汇编程序员写下的。
但是这个程序员也在邮件里表示啊，他只是在上个世纪九十年代初的时候呢，做过类似的实现。
准确来说呢，这条代码也不是他写的那现在所知道的最早的实现呢是美国一位计算机科学家garary塔劳里啊在SPI的一个三d图形工作站inicgo里面实现的。
但是他自己也承认，他只是对长寿花的曲折做一些改进。
那实际上他也不是作者。
后来呢MD的一位图形架构师啊向ma t lave的发明人做了一些查证嗯，得到了这个结论是这个原始的算法是arden的computer公司的grab wash发明。
当然他也没有任何确定性的证据啊，能证明这个事儿不单单是这个算法的原作者是不明的那这个魔法数字啊，当初到底是怎么选择出来的，大家也是无法确定的。
在零三年的时候呢，普渡大学数学系的一个学生chris lamont曾经做过相关的研究。
他推算出了一个函数来讨论这个速算法的误差，并且啊找出了让误差最小的最佳的r值五f三七六四二f那这个值呢和代码中的五f三七五九DF相当接近。
但是把这个值代入算法再做一次牛顿迭代之后呢，得到近似值的精度啊，反而略低于五f三七五九DF的结果。
所以这个同学呢就转而去查找。
经过一到两次牛顿迭代之后，精度最高的r值。
那通过暴力搜索呢得出最优的r值啊是五f三七五a八六，用这个值代入算法，并且进行牛顿迭代啊，得到的结果都比原始值更精确。
所以他就说如果果能能想询问一下原作者这个速算法到底是数学推导出来的，还是用反复试错的方式求出来的？啊，同时呢他还指出六十四位的i triple e七五四浮点数呢，对应的魔法数字是五f一六EC八五e七DE三零DA.但是后来呢其他人的研究表明，代入另一个数的精确度更高。
另一位研究者也使用了一种和lmon类似的方法来优化这个r值。
他最开始呢是用穷举搜索，得到的结果和long man是一致的。
后来呢他尝试用带权的二分法来查找。
那最终呢得到的结果恰好是代码中用到的魔法数字，也就是五f三七五九DF.所以他认为啊这个魔法数字啊最初可能是通过二分法的方式来求出来的。
好了，这可能是编程世界里最经典的魔法数字的故事。
希望你啊能从这节课收获一些数学的基础知识啊，数学啊真的是需要努力学习好的一门功课，尤其啊是在人工智能火热的今天。