建议12-2：使用牛顿迭代法求除数的倒数

在上一小节，我们阐述了如何使用倒数相乘（x/y=x*（1/y））的方法来实现除法运算。然而，对于如何能够快速有效地取倒数，牛顿迭代法（Newton’s method）是最佳方案。

对于牛顿迭代法，相信学过高等数学的读者并不陌生，它又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，它将非线性方程线性化，从而得到迭代序列的一种方法。

对于方程f（x）=0，设x0为它的一个近似根，则函数f（x）在x0附近截断高次项可用一阶泰勒多项式展开为如下形式：

这样，由式（1）我们可以将f（x）=0转化为如下形式：

在这里，我们设f′（x）≠0，则有：

取x作为原方程新的近似根x1，再代入方程，如此反复，于是就产生了迭代公式：

有了迭代公式（4）之后，现在我们继续来看如何用牛顿迭代公式来求倒数，即求除数a的倒数1/a。

这里我们设，式中x为a的倒数，方程f（x）=0为一非线性方程。现在把f（x）=0代入牛顿迭代序列式（4）中，就可以得出求倒数的公式，如下所示：

在式（5）中，xn为第n次迭代的近似根。

如式（5）所示，用牛顿迭代法求倒数，每次迭代需要一次减法与两次乘法，所用的迭代次数决定最终的计算速度和精度。迭代次数越多，则精度越高。但迭代次数越多，速度也越慢，因此实际运用时应综合考虑速度和精度两方面的因素，选择合适的迭代次数。

其实，牛顿迭代法在程序中应用得非常广泛，如最常用的开方、开方求倒数等。在QuakeⅢ源码中，在game/code/q_math.c文件中就有一个函数Q_rsqrt，它的作用是将一个数开平方后取倒，其运行效率也非常高。如代码清单2-2所示。

代码清单2-2　Q_rsqrt函数的实现

---

float Q_rsqrt（ float number ）
{
    long i；
    float x2， y；
    const float threehalfs = 1.5F；
    x2 = number * 0.5F；
    y  = number；
    i  = * （ long * ） &y；
    i  = 0x5f3759df - （ i >> 1 ）；
    y  = * （ float * ） &i；
    // 第一次迭代
    y  = y * （ threehalfs - （ x2 * y * y ） ）；
    // 第二迭代
    // y  = y * （ threehalfs - （ x2 * y * y ） ）；
    return y；
}

---

从代码清单2-2中可以看出，程序首先猜测出一个接近1.0/sqrt（number）的近似值，然后两次使用牛顿迭代法进行迭代（实际只需要使用一次）。这里需要特别注意的是0x5f3759df这个值，因为通过执行语句“0x5f3759df-（i>>1）”，得出的值出人意料地接近1/sqrt（number）的值，因此，我们只需要一次迭代就可以求得近似解，或许这就是数学的神奇。