乐鱼体育安卓版下载

转载)《雷锤3》魔数你见过吗?这10行代码简直吊炸天!

日期:2022-05-21 22:36:53 作者:乐鱼在线 来源:乐鱼体育安卓版下载 阅读:5

  如果你看到这个 0x5f3759df 数字,想必有点小懵逼,人生三问开始了:

  当你需要在游戏中实现一些物理效果,比如光影效果、反射效果时,所关注的点其实是某个向量的方向,而不是这个向量的长度,如果能将所有向量给单位化,很多计算就会变得比较简单。

  所以在计算中很重要的一点就是计算出单位向量,而在真正在运行代码中需要根据某个向量计算相应的单位向量,根据某个向量 (x, y, z) 计算法向量公式如下

  可以看出来计算一个数的平方根的倒数其实非常频繁,所以需要一个很快的算法去计算平方根倒数。众所周知,乘法和加法在计算机中被设计得非常快,所以 x*x+y*y+z*z 计算起来真的非常快,但是

  sqrt(x x + y y + z*z)求平方根算法很慢,求一个数的倒数即除法也很慢,所以上面的一行代码实现平方根倒数所消耗的时间会特别慢。而 Q_rsqrt(x*x + y*y + z*z) 里面的代码没有看到任何除法,以及求平方根,里面全部都是乘法、位移等运算速度很快的操作,平方根倒数速算其实是计算的近似数,大约1%的误差,但是运算速度是之前的三倍,下面就会解释这几行代码。

  首先函数的参数是一个32位浮点数,之后声明一个32位整型变量 i ,继续声明两个32位浮点数 x2,y ,声明一个32位浮点数常量 threehalfs ,即表示,之后两行也非常简单,一个是将 number 的一半赋值给 x2 ,将 number 赋值给 y ,你会发现很有趣的一点,就是这些变量不管是整型还是浮点型,其在内存中的长度都是32位,这其实是magic发生的基础。

  接着看下面几行的注释(因为直接看代码也看不懂),分别是 evil bit hack 、 what the 、 newton iteration ,这三个注释其实就说明了整个算法重要的三步,在真正解释这三个步骤之前,先来说说浮点数的在内存中表示。

  在日常生活中,我们通常以十进制的方式表示现实生活中的各种数,这种数被称为真值,对于负数,我们会在数的前面加一个‘-’号表示这个数是小于0,‘+’号(通常不写)去表示一个正数。而在计算机中只能表示0、1两种状态,所以下正负号在计算机中会以0、1的形式表示,通常放在最高位,作为符号位。为了能够方便对这些机器数进行算术运算、提高运算速度,计算机设计了许多种表示方式,其中比较常见的是:原码、反码、补码以及移码。下面主要以8bit长度的数 0000 0100 ,即十进制数4,去介绍这几种表示方式

  原码表示方式是最容易理解的,首先第一位为符号位,后面七位表示的就是真值,如果表示负数,只需要将符号位置为1即可,后面七位依然为线

  所以很容易就得出原码的表示范围为 [-127, 127] ,会存在两个特殊的数为 +0 与 -0 。

  所以反码表示范围为 [-127, 127] ,依然存在两个特殊的数为 +0 与 -0

  所以补码表示范围为 [-128,127] ,之前的-0在补码中被表示成了-128,可以多表示一个数。

  浮点数先考虑一个问题,如果你用32位二进制如何表示4.25?可能会是这样:

  这放在普通十进制,这种想法其实非常常见,但是这种方式放在二进制世界中,总共1位符号位,15号整数位,16位小数位,总共表示数的范围只有

  ,而对于长整型的范围却有,差的倍数有6w5,可见这种方式为了小数表示抛弃了一半的位数,得不偿失,所以有人提出了IEEE754 标准。

  IEEE754在描述这个标准前,先在这里说下科学计数法,在十进制中科学计数法表示如下

  所以 IEEE754 也是采用的是科学计数法的形式,会将32位数分为以下三部分

  第二部分用8位bit表示指数部分,可以表示数的范围是 [0, 255] ,但是这个只能表示正数,所以需要把负数也加进来,而 IEEE754 标准中阶码表示方式为移码,之所以要表示为移码的方式是在浮点数比较中,比较阶码的大小会变得非常简单,按位比较即可。不过和正常的移码有一点小区别是, 0000 0000 与 1111 1111 用来表示非规格化数与一些特殊数,所以偏移量从128变为127,表示范围也就变成了 [-127, 126] 。

  ,而科学计数法的第一位默认是为1的,所以这个范围就会变成,而1是默认存在的,这样就不会用这23位bit中一位专门来表示这个1,从而多出一位来表示更广范围的小数,线标准的机器数:首先变为相应的二进制数为1001.101,用规范的浮点数表达应为

  ,所以符号段为0,指数部分的移码为1000 0010,有效数字去掉1后为001101,所以最终结果为

  在前面我们介绍了一个浮点数是如何在计算机中以机器数来表示的,现在我们要对这个浮点数进行一些骚操作,以方便之后对这个浮点数的处理。同样的,我们以9.625这个数为例,首先我们令阶码的真值为E,则有

  现在我们先不认为这个是浮点数,这个数就是32位长整型,令这个数为L,它所表示的十进制数便是这样

  这个数L便是这32位所表示的无符号整型,这个数后面有大用,我们先暂且把它放在这儿,后续再来看。

  尾数加1是因为在IEEE754标准中把首位的一去掉了,所以计算的时候需要把这个一给加上,然后阶码减去127是因为偏移为127,要在8位线才是其表示真正的值。

  在这个公式, E-127 自然非常好计算,但是前面的对数计算起来是比较麻烦的,所以我们可以找个近似的函数去代替对数。

  与其实是非常相近的,那样我们可以取一个在 [0,1] 的校正系数$,使得下面公式成立到此,我们知道了怎样去简化对数,所以我们可以将这个简化代入上面浮点数表示中,就可以得到看见这个

  在某种程度上,不考虑放缩与变换,我们可以认为浮点数的二进制表示L其实就是其本身F的对数形式,即

  evil bit hack众所周知啊,每个变量都有自己的地址,程序运行的时候就会通过这个地址拿到这个变量的值,然后进行一系列的计算,比如i和y在内存中会这样表示

  ,只需要左移或者右移N个位就可以,但是浮点数明显无法进行位运算,它本身二进制表示就不是为了位运算设计的。然后,现在就会提出一个想法,我把float转成int,然后进行位运算不就行了,代码如下

  假设y为3.33,进行长整型强转后,C语言会直接丢弃尾数,i也就变成了3,丢失这么多精度,谁干啊,如果我们想一位都不动地进行位运算,就是下面这份代码

  这行代码做了什么事呢, &y 首先将浮点数y的地址找出来,可以认为就是 0x3d6f3d79 这个地址,它的类型其实是 float * ,C语言便会以浮点数的形式将这个数取出来,而想让C语言认为这个是长整型类型,就必须进行地址的类型的强转,将 float * 强转成 long * 。这个强转过程其实没改变内存中任何东西,首先它并没有改变 0x3d6f3d791 这个地址,也没改变这个地址中所存储的数据,可以认为改变的是C语言的“认知”,原本是要以IEEE754标准去读取这个地址中数据,但是C语言现在认为这个是长整型的地址,按长整型方式读取就行。所以 (long*)&y 代表 0x3d6f3d791 这个地址中存储的是长整型数据,然后我通过 * 运算符从这个地址中拿出数据,赋值给 i 这个长整型变量。

  这样我们其实避开了数字本身的意义,而是通过地址变换完整地拿出了这个二进制数据。

  众所周知啊,位运算中的左移和右移一位分别会使原数乘以或者除以2,比如我们想办法把平方根倒数做一个简单的转化

  这个等式其实就是我们的最终目标,接下的计算就会逐渐往这个等式靠近,得到一个近似的结果。

  在前面一步的叙述中,我们得出这样一个结论,浮点数的二进制表示其实就是其本身的对数形式,想要求的浮点数存储在y中,则有

  前面提到过,直接运算一个数的平方根倒数,所以不如直接计算平方根倒数的对数,然后就会有如下等式

  除法同样计算速度是比较慢的,所以我们用右移代替除法,这也就解释了 -(i 1) 其实是为了计算

  的结果。所以 0x5f3759df 这个数到底咋来的,为啥要这么计算,并且 -(i 1) 并不完全是

  的近似值啊,根据公式还得除以,还得加上一定的误差。先别急,我们先算下这个 magic number 是咋来的,令

  为y的平方根倒数,则有然后我们代入上面那个浮点数对数的公式中,则有现在经过一定的变换能够得到下面这个式子

  是就是之前简化对数计算引进的误差,通过一定计算,得到最合适的,来得到的近似值。这个计算过程偏向纯数学化的,具体过程请查阅《FAST INVERSE SQUARE ROOT》这篇论文。这个数的十六进制就是 0x5f3759df ,也就是上面提到的那个 magin number ,然后我们根据这个数去计算得到的近似值,并与真正的

  进行比较,具体函数图像如下从上面的图像可以看到,在 [1,100] 这个区间内,所得到的近似值曲线已经和原始值制拟合的比较好了,这样我们已经完成了前面几个比较重要的步骤。

  * ) 这样我们通过和 evial bit hack 的逆向步骤,即将一个长整型的内存地址,转变成一个浮点型的内存地址,然后根据IEEE754标准取出这个浮点数,即我们要求的 \Gamma 的近似值,其实到这里应该是算法差不多结束了,但是这个近似值还存在一定的误差,还需要经过一定的处理降低误差,更接近真实值。

  本身我们已经得到了一个比较好的近似值,但是仍然存在一定的误差,而牛顿迭代法可以这个近似值更加接近真实的值,近一步减少误差。牛顿迭代法本身是为了找到一个方程根的方法,比如现在有一个方程

  ,需要找到这个方程的根,但是解方程嘛,是不会解方程的,所以可以找到一个近似值来代替这个真正的解。如上图,假设

  的解为,我们需要首先给一个的近似值,通过这个,不断求得一个与更接近的值。在

  处做切线,切线的斜率就是在的导数,然后来求这条切线与x轴的交点,则有这样我们就完成了一次迭代,从图像上可以看见

  比更接近于真正的解,下一次迭代基于进行同样的步骤,就能得到比更好的近似值,所以牛顿迭代公式非常简单当这个迭代次数接近无限时,

  也就越接近真正的解。而最后一行就是经过一次迭代后的简化公式,这个公式怎么来的呢。对于一个浮点数

  ,在更接近真实答案的同时,运行速率也大大提升。仅仅牺牲了一点点的准确性,却能提高整个的速度,这其实就是算法在优化中的一个比较重要的点。

  来自字节跳动,是旗下大力教育前端部门,负责字节跳动教育全线产品前端开发工作。我

  围绕产品品质提升、开发效率、创意与前沿技术等方向沉淀与传播专业知识及案例,为业界贡献经验价值。包括但不限于性能监控、组件库、多端技术、Serverless、可视化搭建、音视频、人工智能、产品设计与营销等内容。字

乐鱼在线
乐鱼在线 @ 版權歸所有 乐鱼在线