0x5f375a86 魔法数

在机缘巧合下，了解到了这么一个神奇的 16 进制数字0x5f3759df，顺便记录一下

科学改变世界，数学改变科学

上回遇到的不讲道理的数字是0.75，它出现在 Java HashMap 的源码中，含义是默认的负载因子。简单介绍一下这个值的含义：在 HashMap 中达到容量的 0.75 倍时（即容量为 16 时元素为 12 时）会对 HashMap 进行扩容，扩容的意义在于减少 hash 冲突，避免 HashMap 退化为链表而大大增加查询时间。至于这个值为什么是 0.75，有个很简单的解释：提高空间利用率和减少查询成本的折中，主要是泊松分布，0.75 的话碰撞最小

好吧，这个解释我能接受，这个 0.75 也能接受，但是我完全无法想象0x5f3759df这个玩意儿是怎么得来的完全想象不出来。
以下是关于这个魔法数的背景和源码介绍，部分引用自知乎：0x5f3759df 这个快速开方中的常数的数学依据是什么？，及另一篇博客：0x5f3759df 的数学原理；中文版可以看这个：数学之美：平方根倒数速算法中的神奇数字 0x5f3759df

Quake-III Arena (雷神之锤 3)是 90 年代的经典游戏之一。
该系列的游戏不但画面和内容不错，而且即使计算机配置低，也能极其流畅地运行。这要归功于它 3D 引擎的开发者约翰-卡马克（John Carmack）。事实上早在 90 年代初 DOS 时代，只要能在 PC 上搞个小动画都能让人惊叹一番的时候，John Carmack 就推出了石破天惊的 Castle Wolfstein, 然后再接再励，doom, doomII, Quake...每次都把 3-D 技术推到极致。他的 3D 引擎代码资极度高效，几乎是在压榨 PC 机的每条运算指令。当初 MS 的 Direct3D 也得听取他的意见，修改了不少 API。

这个神奇的数字出现在这个 3D 引擎的底层代码中，它的作用是将一个数开平方并取倒数，经测试这段代码比(float)(1.0/sqrt(x))快 4 倍：

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

#ifndef Q3_VM
#ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
    return y;
}

关于迭代法

迭代法通过旧值计算新值，循环往复，非常符合计算机语言。
最经典的迭代算法是欧几里德算法（辗转相除法），用于计算两个整数 a,b 的最大公约数。其计算原理依赖于下面的定理：

gcd(a,b) = gcd(b,a mod b)

除此之外，常见的比如斐波那契数列，也可以用迭代法计算。一般来说，递归算法拥有很好的可读性，但往往需要更多的开销，这时可以将递归转换为递推（迭代），以期更高的效率。这一点我在做算法题时深有感触。

关于牛顿迭代法

简介：牛顿迭代法-百度百科
300 年前的思想到现在仍然可以发光发热，数学果然是文明的基石
一般 sqrt 算法就是使用牛顿迭代法,用x-f(x)/f'(x)来不断的逼近f(x)=a的根。

简单来说比如求平方根,f(x)=x^2=a ,f'(x)= 2*x,f(x)/f'(x)=x/2,把f(x)代入x-f(x)/f'(x)后有(x+a/x)/2，现在我们选 a=5 ,选一个猜测值比如 2，那么我们可以这么算

1. 5/2 = 2.5;(2.5+2)/2 = 2.25;

2. 5/2.25 = 2.22;(2.25+2.22)/2 = 2.235;

3. 5/2.235 = 2.23713;(2.235+2.23713)/2 = 2.236065;

仅仅三步我们得到的值就和 sqrt(5)= 2.23606797 相差无几，可以预见，如此反复迭代其结果收敛于 sqrt(5)。一般可以迭代 4~7 次后就能得到一个相对精确的值。这是建立在猜测值相对不精确来说的，理论上，只要猜测值足够精确，就可以大幅压缩迭代次数，于是这个数0x5f3759df出现了。

具体的推导过程可以参考以上的博客，这边引用一下文末的结论，这同时激起我对游戏引擎的好奇。

如此神奇，如此怪异，如此不符合常理，如此符合常理，如此美丽。

我们已经足够深入了，至少我很满足了，没有什么可以继续探究的了。对于我来说，通过这个练习，主要学到的是整形和浮点型之间的位转换操作不是没有意义的，它很怪异但却很经济的数字操作，在计算中很有用。我认为它还有更多有待发现的用处。