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

曲面法線廣泛用于光照和陰影計(jì)算，需要計(jì)算矢量的范數(shù)。這里顯示了垂直于表面的矢量場(chǎng)。

?

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

在這種情況下，在從曲面鏡反射的光上?？焖俜雌椒礁糜趯⒃撚?jì)算推廣到三維空間。

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

? ? ? ?通過計(jì)算其歐幾里德范數(shù)：矢量分量的平方和的平方根來確定矢量的長(zhǎng)度。當(dāng)向量的每個(gè)分量除以該長(zhǎng)度時(shí)，新向量將是指向相同方向的單位向量。在3D圖形程序，所有的載體在三維空間中，所以v將是一個(gè)向量（v?₁，v?₂，v?₃）。?

是向量的歐幾里德范數(shù)。?

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

它將單位矢量與距離分量的平方根相關(guān)聯(lián)。反平方根可用于計(jì)算v，因?yàn)樵摰仁降葍r(jià)于?

其中分?jǐn)?shù)項(xiàng)是的平方根?||v||?²。當(dāng)時(shí)，與乘法相比，浮點(diǎn)除法通常很昂貴;?快速逆平方根算法繞過了除法步驟，賦予其性能優(yōu)勢(shì)。

? ? ? ?為了計(jì)算平方根倒數(shù)的一般方法是計(jì)算一個(gè)近似為¹?_√x，然后通過另一種方法修改該近似直到它來實(shí)際結(jié)果的可接受的誤差范圍之內(nèi)。20世紀(jì)90年代早期的常用軟件方法從查找表中得出近似值?？焖倨椒礁年P(guān)鍵是通過利用浮點(diǎn)數(shù)的結(jié)構(gòu)直接計(jì)算近似，證明比表查找更快。該算法比使用另一種方法計(jì)算平方根并計(jì)算倒數(shù)通過浮點(diǎn)除法快大約四倍。該算法的設(shè)計(jì)考慮了IEEE 754-1985?32位浮點(diǎn)規(guī)范，但研究表明它可以在其他浮點(diǎn)規(guī)范中實(shí)現(xiàn)。

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

Talk is cheap.Show me your code：

(1)、平方根函數(shù)：方法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類型的取絕對(duì)值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)、平方根函數(shù)：方法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()

注意開頭的導(dǎo)入：import Foundation。

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

最大相對(duì)誤差低于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相應(yīng)的構(gòu)造函數(shù)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)測(cè)試：?

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來自哪里？為什么代碼有效？

快速逆平方根：有時(shí)被稱為快速InvSqrt()或由十六進(jìn)制常數(shù)0x5F3759DF的估計(jì)¹?_√x算法的倒數(shù)（或乘法逆）的的平方根的32位的浮點(diǎn)數(shù)X在IEEE 754浮點(diǎn)格式。此操作用于數(shù)字信號(hào)處理以標(biāo)準(zhǔn)化矢量，即將其縮放為長(zhǎng)度1.例如，計(jì)算機(jī)圖形程序使用反平方根來計(jì)算入射角和反射對(duì)照明和陰影。

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

一個(gè)有效例子：作為一個(gè)例子，數(shù)x = 0.15625可用于計(jì)算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

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

算法描述：快速反向平方根算法計(jì)算¹?_√x，通過執(zhí)行以下步驟。

(1)、將參數(shù)x別名為整數(shù)，作為計(jì)算?log₂(x)近似值的方法

(2)、使用這種近似計(jì)算的近似對(duì)數(shù)log₂(¹?_√x)= ?1/2 log₂(x)

(3)、別名返回浮點(diǎn)數(shù)，作為計(jì)算base-2指數(shù)近似值的方法

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

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

?

轉(zhuǎn)載于:https://www.cnblogs.com/strengthen/p/10989143.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[Swift]快速反向平方根 | Fast inverse square root的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。