建議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）的值，因此，我們只需要一次迭代就可以求得近似解，或許這就是數學的神奇。