★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：https://www.cnblogs.com/strengthen/p/10989143.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★?

曲面法線廣泛用于光照和陰影計算，需要計算矢量的范數。這里顯示了垂直于表面的矢量場。

使用法線 $C從入射角求出反射角的二維例子;?$

在這種情況下，在從曲面鏡反射的光上。快速反平方根用于將該計算推廣到三維空間。

? ? ? ?浮點數的倒數平方根用于計算標準化向量。程序可以使用標準化向量來確定入射角和反射角。3D圖形程序必須每秒執行數百萬次這些計算以模擬光照。當代碼在20世紀90年代早期開發時，大多數浮點處理能力都落后于整數處理的速度。在專門用于處理變換和照明的硬件出現之前，這對3D圖形程序來說很麻煩。

? ? ? ?通過計算其歐幾里德范數：矢量分量的平方和的平方根來確定矢量的長度。當向量的每個分量除以該長度時，新向量將是指向相同方向的單位向量。在3D圖形程序，所有的載體在三維空間中，所以 $v將是一個向量（v? 1 ，v? 2 ，v? 3 ）。$ ?

$\ | {\ boldsymbol {v}} \ | = {\ sqrt {v_ {1} ^ {2} + v_ {2} ^ {2} + v_ {3} ^ {2}}}$

是向量的歐幾里德范數。?

${\ displaystyle {\ boldsymbol {\ hat {v}}} = {\ frac {\ boldsymbol {v}} {\ left \ | {\ boldsymbol {v}} \ right \ |}}}$

是使用 $|| 的歸一化（單位）向量?|| v||? 2 代表 v1^2?+?v2^2?+?v3^2。$ ?

${\ displaystyle {\ boldsymbol {\ hat {v}}} = {\ frac {\ boldsymbol {v}} {\ sqrt {\ left \ | {\ boldsymbol {v}} \ right \ | ^ {2}}} }}$

它將單位矢量與距離分量的平方根相關聯。反平方根可用于計算 $v，因為該等式等價于$ ?

${\ displaystyle {\ boldsymbol {\ hat {v}}} = {\ boldsymbol {v}} \，{\ frac {1} {\ sqrt {\ left \ | {\ boldsymbol {v}} \ right \ | ^ {2}}}}}$

其中分數項是 $的平方根?|| v||? 2 。$ 當時，與乘法相比，浮點除法通常很昂貴;?快速逆平方根算法繞過了除法步驟，賦予其性能優勢。

? ? ? ?為了計算平方根倒數的一般方法是計算一個近似為 $1 ? \sqrt x ，然后通過另一種方法修改該近似直到它來實際結果的可接受的誤差范圍之內。20世紀90年代早期的常用軟件方法從查找表中得出近似值。快速平方根的關鍵是通過利用浮點數的結構直接計算近似，證明比表查找更快。該算法比使用另一種方法計算平方根并計算倒數通過浮點除法快大約四倍。該算法的設計考慮了IEEE 754-1985?32位浮點規范，但研究表明它可以在其他浮點規范中實現。$

? ? ? ?快速反平方根的速度優勢來自于將包含浮點數的長字視為整數，然后從特定常數0x5F3759DF中減去它。查看代碼的人不會立即清楚常量的目的，因此，與代碼中的其他此類常量一樣，它通常被稱為幻數。該整數減法和位移產生長字，當作為浮點數處理時，該長字是輸入數的反平方根的粗略近似。執行牛頓方法的一次迭代以獲得一定的準確性，并且代碼完成。該算法使用Newton方法的唯一第一近似值生成相當準確的結果;?然而，它比在1999年發布的rsqrtss x86處理器上使用SSE指令要慢得多且準確度低得多。

Talk is cheap.Show me your code：

(1)、平方根函數：方法1-牛頓迭代法

 1 func sqrt1(_ x: Float) -> Float {
 2     //判斷x是否為0
 3     if x == 0 {return 0}
 4     let high:Float = Float(x)
 5     let mid:Float = high/2
 6     var y:Float = (mid>1) ? mid : 1
 7     while(true)
 8     {
 9         let dy:Float = (y * y + high) / Float(y)/2
10         //處理float類型的取絕對值fabsf(float i)
11         if fabsf(y - dy) <= 0.00000001
12         {
13             return dy
14         }
15         else
16         {
17             y = dy
18         }
19     }
20 }

(2)、平方根函數：方法2?

 1 func sqrt2(_ x:Float) -> Float
 2 {
 3     var y:Float
 4     var delta:Float
 5     var maxError:Float
 6     if x <= 0 {return 0}
 7     // initial guess
 8     y = x / 2
 9     // refine
10     maxError = x * 0.00000001
11     repeat {
12         delta = ( y * y ) - x
13         y -= delta / ( 2 * y )
14     } while ( delta > maxError || delta < -maxError )
15     return y
16 }

(3)、快速反向平方根：方法1-使用memcpy()

注意開頭的導入：import Foundation。

invSqrt(x)比1.0/sqrt(x)快速增加了約40％，

最大相對誤差低于0.176％?

 1 import Foundation
 2 func invSqrt1(_ x: Float) -> Float {
 3     let halfx = 0.5 * x
 4     var y = x
 5     var i : Int32 = 0
 6     memcpy(&i, &y, 4)
 7     i = 0x5f3759df - (i >> 1)
 8     memcpy(&y, &i, 4)
 9     y = y * (1.5 - (halfx * y * y))
10     return y
11 }

(4)、快速反向平方根：方法2-bitPattern()

從Swift3開始，memcpy()可以用bitPattern:方法替換Float相應的構造函數UInt32:

1 func invSqrt2(_ x: Float) -> Float {
2     let halfx = 0.5 * x
3     var i = x.bitPattern
4     i = 0x5f3759df - (i >> 1)
5     var y = Float(bitPattern: i)
6     y = y * (1.5 - (halfx * y * y))
7     return y
8 }

綜合(1)~(4)測試：?

 1 let x:Float = 10.0
 2 let ans1:Float = sqrt1(x)
 3 let ans2:Float = sqrt2(x)
 4 let ans3:Float = invSqrt1(x)
 5 let ans4:Float = invSqrt2(x)
 6 print(1.0/ans1)
 7 //Print 0.31622776
 8 print(1.0/ans2)
 9 //Print 0.31622776
10 print(ans3)
11 //Print 0.31568578
12 print(ans4)
13 //Print 0.31568578

常量0x5f3759df來自哪里？為什么代碼有效？

快速逆平方根：有時被稱為快速InvSqrt()或由十六進制常數0x5F3759DF的估計 $1 ? \sqrtx 算法的倒數（或乘法逆）的的平方根的32位的浮點數X在IEEE 754浮點格式。此操作用于數字信號處理以標準化矢量，即將其縮放為長度1.例如，計算機圖形程序使用反平方根來計算入射角和反射對照明和陰影。$

? ? ? ?該算法接受32位浮點數作為輸入，并存儲一半的值供以后使用。然后處理代表浮點數作為一個32位的整數的比特，一個邏輯移位一個位權執行，并且結果從減去幻數 0X 5F3759DF，這是一個近似的浮點表示√2¹²⁷。這導致輸入的平方根的第一近似。再次將這些位作為浮點數處理，它運行牛頓方法的一次迭代，產生更精確的近似。

一個有效例子：作為一個例子，數x = 0.15625可用于計算1?√x ≈ 2.52982.。該算法的第一步如下所示：?

1 0011_1110_0010_0000_0000_0000_0000_0000  Bit pattern of both x and i
2 0001_1111_0001_0000_0000_0000_0000_0000  Shift right one position: (i >> 1)
3 0101_1111_0011_0111_0101_1001_1101_1111  The magic number 0x5F3759DF
4 0100_0000_0010_0111_0101_1001_1101_1111  The result of 0x5F3759DF - (i >> 1)

使用IEEE 32位表示：?

1 0_01111100_01000000000000000000000  1.25 × 2?3
2 0_00111110_00100000000000000000000  1.125 × 2?65
3 0_10111110_01101110101100111011111  1.432430... × 263
4 0_10000000_01001110101100111011111  1.307430... × 21

將該最后一位模式重新解釋為浮點數給出近似值 $y?= 2.61486，其具有大約3.4％的誤差。在牛頓方法的一次迭代之后，最終結果是 y?= 2.52549，誤差僅為0.17％。$

算法描述：快速反向平方根算法計算 $1 ? \sqrt x ，通過執行以下步驟。$

(1)、將參數 $x別名為整數，作為計算 ? log 2 (x) 近似值的方法$

(2)、使用這種近似計算的近似 $對數log 2 (1 ? \sqrt x)= ?1/2 log 2 (x)$

(3)、別名返回浮點數，作為計算base-2指數近似值的方法

(4)、使用牛頓方法的單次迭代來細化近似。

準確度：下圖顯示啟發式快速反平方根與libstdc提供的平方根直接反轉之間差異的圖表。注意兩個軸上的對數刻度。如上所述，近似值令人驚訝地準確。右邊的圖表描繪了函數的誤差（即，通過運行牛頓方法的一次迭代后的近似值的誤差），對于從0.01開始的輸入，其中標準庫給出10.0作為結果，而InvSqrt()給出9.982522，使差值為0.017479，即真值的0.175％。絕對誤差僅從此開始下降，而相對誤差保持在所有數量級的相同范圍內。