平方根的快速算法(sqrt) | 平方根算法
在我們的產品上要對數據進行FFT運算,之後要進行開方運算。但使用TI提供的sqrt函數運算速度較慢,因此從網上找到這篇介紹sqrt快速算法的文章。經我的測算,迭代兩次的快速sqrt算法是TI提供的函數運算時間的50%,精度可以達到0.05%,可以滿足我們的要求。以下是文章正文:作者:Blackbird文章出處:友善之臂旅店[1]在3D圖形編程中,經常要求平方根或平方根的倒數,例如:求向量的長度或將向量歸一化。C數學函數庫中的sqrt具有理想的精度,但對於3D遊戲程式來說速度太慢。我們希望能夠在保證足夠的精度的同時,進一步提高速度。Carmack在...
在我們的產品上要對數據進行FFT運算,之後要進行開方運算。但使用TI提供的sqrt函數運算速度較慢,因此從網上找到這篇介紹sqrt快速算法的文章。
經我的測算,迭代兩次的快速sqrt算法是TI提供的函數運算時間的50%,精度可以達到0.05%,可以滿足我們的要求。以下是文章正文:
作者:Blackbird文章出處:友善之臂旅店[1]
在3D圖形編程中,經常要求平方根或平方根的倒數,例如:求向量的長度或將向量歸一化。C數學函數庫中的sqrt具有理想的精度,但對於3D遊戲程式來說速度太慢。我們希望能夠在保證足夠的精度的同時,進一步提高速度。
Carmack在QUAKE3中使用了下面的算法,它第一次在公衆場合出現的時候,幾乎震住了所有的人。據說該算法其實並不是Carmack發明的,它真正的作者是Nvidia的Gary Tarolli(未經證實)。
// // 計算參數x的平方根的倒數 // float InvSqrt (float x) { float xhalf = 0.5f*x; int i = *(int*)&x; i = 0x5f3759df - (i >> 1); // 計算第一個近似根 x = *(float*)&i; x = x*(1.5f - xhalf*x*x); // 牛頓迭代法 return x; }該算法的本質其實就是牛頓迭代法(Newton-Raphson Method,簡稱NR),而NR的基礎則是泰勒級數(Taylor Series)。NR是一種求方程的近似根的方法。首先要估計一個與方程的根比較靠近的數值,然後根據公式推算下一個更加近似的數值,不斷重複直到可以獲得滿意的精度。其公式如下:
函數:y=f(x) 其一階導數爲:y=f(x) 則方程:f(x)=0 的第n+1個近似根爲 x[n+1] = x[n] - f(x[n]) / f(x[n]) NR最關鍵的地方在於估計第一個近似根。如果該近似根與真根足夠靠近的話,那麼只需要少數幾次迭代,就可以得到滿意的解。現在回過頭來看看如何利...