0x5f3759df这个快速开方中的常数的数学依据是什么?

0x5f3759df这个快速开方中的常数的数学依据是什么?

来试试知乎的用文章回答问题的功能,看起来是直接复制文章过来了呀,那就这样吧。

感觉十分有必要写一下自己对这段代码的学习以及理解了。

在数学中如果我们考虑一个函数 时,这里的 自然是认为为实数(没考虑复数)。但是计算机时没有办法处理任意实数的,毕竟无限不循环这件事在物理层面是实现不了的。计算机中对实数有两种表达: double 和 float,两者主要差异是占用内存的大小区别。我们重点放在float,因为学会float理解double就容易了,而且在游戏计算中对计算速度要求很高,float也会更常用。

浮点数,全名应该是floating-point number,其实是一系列的规定。为了理解float,我们先思考计算机如何使用二进制表示数字。让我们一步一步来吧

举个例子,

我们对十进制的理解就是将数字从0数到9就进一位,因为没有一个数字或字母来直接表示10的含义,而二进制中只有0和1,也是因此 ,我们将每一个二进制的位称为比特 (bit) 。

但我们在写程序时也不是跟每一个bit打交道,由于历史以及某些硬件原因,我们一般与字节(byte) 打交道,也就是8个bits一起。那么每1个byte能代表的数字就是 0 ~ 255,即

当然,事情自然不会这么简单,如果我们要表示负数咋办?如果你了解过如何用加法来进行减法,那就不难理解为啥我们会有一个咋一看很奇怪的规则:第一位bit的0、1来代表是否为负数,于是乎我们上面的那个例子就变成了

1个byte能代表的数字也就变成了 -127 ~ 127

好的,当你能理解上面的设定后,就可以来看看float的设定了,一般而言,如果不加以设定float一般时32 bits,也就是4 bytes的。其中

第1位bit是正负号;8个bits(1个byte)是幂 (Exponent,后面记为E);后23个bits是小数位 (Mantissa, 后面记为M)

设定归设定,啥意思呢?还是先想十进制

好的,但是如果更大或更小的情况呢?比如 或 呢,相信你可能就会用科学计数法了,即 和 。这样就方便很多了,同样的,float的设定本质上算是科学计数法的拓展。

任意float可以通过下式转换为被表示为

想看各种数如何变成二进制的可以去 IEEE-754 Floating Point Converter 试一下

看一个例子

这里我用‘,’将符号、幂和小数位分开了

其中

运用上面的公式我们得到了 ,可以看出,float不能百分百还原我们要的小数,但是是一个不错的近似。

如果你不觉得这像是科学计数法,那我们就换一种写法

再加一个1.0,即默认会有的 ,科学计数法是不以0做开头的(例如 不是科学计数法,应该是 )。由此再看,我们这个就像是 ,这里 指小数位 的第 位数,只不过每一位都是要乘2的对应幂,而不是10。

刚我们看来如果你要将float从二进制换算为十进制,需要用将 和 按十进制读出来,然后再用公式

但这只是规定而已,计算机中本质上还就是那些0和1,所以如果你非要将一个float的二进制读成一个二进制的整数,那也没人能拦着你,就像雷神三中的

就是将float y读成了一个整数(long int)

然后又返回去了。能想着这么做真不是什么省油的灯。

如果你理解了前面整数的二进制表达部分,就不难理解这里 i 通过这么一系列变成了

这就是转换后会得到的整数。

要看懂雷神三的代码还有两部分,一部分是牛顿法,另一部分就是一个对数函数的近似。牛顿法是很简单的,放到最后吧。有意思的是一个对数函数近似,

虽然从图像上不难看出没啥问题,但是确实也挺没道理的。就算用泰勒展开,也不能直接写出关于x的表达(底数不是e)。

但不管怎样,从图像中,我们可以看出:当x在0到1之间,k都在0到0.1以内。

好了,有了全部这些东西,让我们来看看那段 What Technically Fabulous codes 的魔法吧

让我们先考虑

将 认定为float,带入我们的float表达

可以看到我们的对数函数内是符合之前那个近似的条件的,使用那个近似

这个形式是很有意思的,因为右边 是将需要进行操作的 的float强行看成整数时的表达,左边 是做完操作后的 看成整数时的表达。

所以代码中

就对应着

位操作,向右移,差不多除以2,就不多细讲了,想明白整数的二进制表达就好。

而最后的magic number,0x5f3759df到底是什么鬼?

就应该是对应着我们的常数

我们可以逆推一下,0x5f3759df是十六进制(想想二进制和十进制,你就应该能想明白),它换成十进制就是1597463007。那么k就应该是0.0450,与我们之前说k的范围是对应的。

再看一眼,也就是说这段代码就是将float y看成一个整数i,然后通过一个奇妙的常数去减去除以了2的i,这时就已经完成了 的一个估计计算了,再让y等于将这个整数i看成float的情况。

妙啊,妙啊!

近似毕竟是近似,最后他们又用了一、两次牛顿法来得到一个更好的值,但这个就很好理解了。

以上就是牛顿法的形式了,这里

是输入,是一个定值,那么

好了,再看最后两句

牛顿法,朴实无华呐。

这段代码真的能看出一个程序员的功力啊,内心需要始终铭记计算机不是数字,而是数据。真的是让我大为震撼。