编程论坛 → C语言论坛

牛顿迭代法-续

kin3z 发布于 2017-01-21 14:29， 1180 次点击

[cpp]

程序代码：

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;
}

一发不可收拾，请问有人可以说说里面的那句迷之代码的原理？
i = 0x5f3759df - ( i >> 1 );

引用自：

http://blog.

[此贴子已经被作者于2017-1-21 14:30编辑过]

3 回复

#2

吹水佬2017-01-21 16:40

在代码中用一个没有声明定义的常数，可能是一个“经验数”或“试验数”。
据说用 0x5f375a86 比 0x5f3759df 还要好一点点，谁有兴趣去验证一下。

#3

吹水佬2017-01-21 16:49

找到一段解释，不知对否？
程序首先猜测了一个接近1/sqrt(number)的值，然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 – a = 0的一个正实根，它的导数是-2/x^3。运用牛顿迭代公式x' = x – f(x)/f'(x)，式子化简为x' = x * (1.5 – 0.5a * x^2)。迭代几次后，x的值将趋于1/sqrt(a)。
但这段代码那个神秘的0x5f3759df，因为0x5f3759df-(i>>1)出人意料地接近根号y的倒数。

#4

kin3z2017-01-22 15:40

回复 3楼吹水佬

那推算，可能它们多次运行测试发现y的值都不变，就没必要按照公式去推算出y了，直接打印出y的值记录下来当作常量来用，不过需要验证才能证实猜想，今天找时间验证。

1