改變世界的四行程式碼－快速反向平方根

好久不見。
搬家結束後終於想起 Qiita，卻發現已經放置了大約 2 個月。

您好，復活的 Xu 來了。

偶爾我想說些不同的話題，今天我想談談與數學相關的話題。

那我們就開始吧，

log_2(1+\frac{M}{2^{23}})

大家對這個數式有印象嗎？

不知道也沒關係，我最近才知道這個式子。
這個式子被稱為高速逆平方根。

高速逆平方根

高速逆平方根（Fast inverse square root）計算是針對給定的 x 計算 1/√x 的近似值的快速演算法。

主要應用在 3D 圖形計算中，需要快速求得「向量長度」的倒數，這樣能提升像是遊戲等即時渲染的效能。

具體來說，在 3D 圖形中，曲面是由無數平面組成的，當光線照射時，這些曲面將如何反射，會在向量計算中應用到。

像 NVIDIA 和 Intel 這樣的顯示卡，在硬體層面上都已經優化了逆平方根的計算，因此實際上在程式碼層面上實作的機會並不多見。

乍看之下似乎有些困難，但請大家一起回憶起高中和大學的數學，深入探討這個話題吧！

解釋 1. 根號的倒數

首先讓我們複習基本概念。
對於非理科背景的人來說，大概在學生時代不會專門學習到這一點。

倒數簡單來說，就是分母和分子互換。
根號的倒數就是將根號放在分母，分子 1 的根號還是 1，這是理所當然的。

例如：

\sqrt{2} 的倒數是 \frac{1}{\sqrt{2}}

到這裡還算簡單吧。

解釋 2. 牛頓法

那我們來看看，如果不依賴機器的力量，你會怎麼計算平方根直到小數點後 7 位？

\sqrt{2}

這個問題可以轉換成尋找 y=x^2-2 與 x 軸的交點。

然而，這個圖形是曲線。
為了簡化計算，我們畫一條輔助線 x=2 （紅線），並在曲線交叉的點上作切線。

根據切線方程 y−f(a)＝f´(a)(x−a) 用微分法計算，可以得到 y=4x-6 （黃線）。

這樣，接線和 x 軸的交點為 (1.5, 0)。

曲線和 x 軸的交點已經很接近，但還是略有距離。
在這裡，我們再從 (1.5, 0) 向上畫一條線（紫線）。

再來在交點處作切線，計算與 x 軸的交點可以得到 1.414667...。

這樣就大致上得到了近似值。
如果還想要提高精度，可以重複以上輔助線和切線的過程數次。

若小數點後只需要 7 位，重複 5 次也幾乎不會有變化。
從粗略計算來看，這已經是相當好的精度了。

在微積分領域，這個方法稱作牛頓法，約在 300 年前由牛頓發明。

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

實際上，高速逆平方根的開發是基於這個牛頓法的思想。

計算的簡化

了解了這些後，接下來我們來看看這要如何轉換成程式碼。

如果簡單地用 while 迴圈來實行，會變得相當繁瑣。

def newtown_sqrt_2(precision=1e-7):
    x = 1.0  # 初始值
    while True:
        next_x = 0.5 * (x * 2 / x)  # 牛頓法
        if abs(next_x - x) < precision:
            return precision
        x = next_x

但實際情況下，Xn 的值來自何處呢？
在這裡就出現了，

改變世界的 4 行程式碼

被稱為 FPS 的創始者 John D. Carmack，僅用幾行程式碼就簡化了這個計算，並對世界產生了革命性的影響。


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));   // 第一次計算

---

原文出處：https://qiita.com/Xudev/items/701906ebe12b4576e7d5