python牛顿法计算平方根_常用的平方根算法详解与实现
本文從屬于筆者的數據結構與算法系列文章。
SquareRoot
平方根計算一直是計算系統的常用算法，本文列舉出幾張簡單易懂的平方根算法講解與實現。其中Java版本的代碼參考這里
Reference
Babylonian:巴比倫算法/牛頓法
巴比倫算法可能算是最早的用于計算$sqrt{S}$的算法之一，因為其可以用牛頓法導出，因此在很多地方也被成為牛頓法。其核心思想在于為了計算x的平方根，可以從某個任意的猜測值g開始計算。在真實的運算中，我們往往將g直接設置為x，不過也可以選擇其他任何的正數值。那么其計算的迭代過程為:
1.如果猜測值g已經足夠接近于正確的平方根，算法結束，函數將g作為結果返回。
2.如果猜測值g不夠精確，那么使用g和x/g的平均值作為新的猜測值。因為這兩個值中的一個小于確切的平方根，另一個則大于確切的平方根，選擇平均值有助于你得到一個更接近于正確答案的值。
3.把新的猜測值賦予給變量g，重復第一步的判斷。
綜上所述，其計算公式可以表述為:
其實現的參考代碼地址為SquareRoots:
public double Babylonian() {
double g = this.value;
while (isApproximate(g)) {
g = (g + this.value / g) / 2;
}
return g;
}
基于泰勒公式的級數逼近
微積分中的泰勒級數可以表示為:
在這個公式中，符號a表示某個常量，記號f'、f''和f'''表示函數f的一階、二階和三階導數，以此類推，這個公式稱為泰勒公式，基于這個公式，我們平方根公式的展開式為:
根據該公式我們可以在一定精度內逼近真實值，不過這個公式仍然存在一個問題，即是公式的收斂問題。在泰勒級數展開中，平方根函數的公式當且僅當參數值位于一個有效范圍內時才有效，在該范圍內計算趨于收斂。該范圍即是收斂半徑，當我們對平方根函數用a=1進行計算時，泰勒級數公式希望x處于范圍:$0
public double TSqrt() {
//設置修正系數
double correction = 1;
//因為要對原值進行縮小,因此設置臨時值
double tempValue = value;
while (tempValue >= 2) {
tempValue = tempValue / 4;
correction *= 2;
}
return this.TSqrtIteration(tempValue) * correction;
}
private double TSqrtIteration(double value) {
double sum = 0, coffe = 1, factorial = 1, xpower = 1, term = 1;
int i = 0;
while (Math.abs(term) > 0.000001) {
sum += term;
coffe *= (0.5 - i);
factorial *= (i + 1);
xpower *= (value - 1);
term = coffe * xpower / factorial;
i++;
}
return sum;
}
平方根倒數速算法
首先接收一個32位帶符浮點數，然后將之作為一個32位整數看待，以將其向右進行一次邏輯移位的方式將之取半，并用十六進制“魔術數字”0x5f3759df減之，如此即可得對輸入的浮點數的平方根倒數的首次近似值；而后重新將其作為浮點數，以牛頓法反復迭代，以求出更精確的近似值，直至求出符合精確度要求的近似值。在計算浮點數的平方根倒數的同一精度的近似值時，此算法比直接使用浮點數除法要快四倍。此算法最早被認為是由約翰·卡馬克所發明，但后來的調查顯示，該算法在這之前就于計算機圖形學的硬件與軟件領域有所應用，如SGI和3dfx就曾在產品中應用此算法。而就現在所知，此算法最早由Gary Tarolli在SGI Indigo的開發中使用。雖說隨后的相關研究也提出了一些可能的來源，但至今為止仍未能確切知曉此常數的起源。
其實現的參考代碼地址為SquareRoots:
public double FastInverseSquareRoot() {
double tempValue = value;
double xhalf = 0.5d * tempValue;
long i = Double.doubleToLongBits(tempValue);
i = 0x5fe6ec85e7de30daL - (i >> 1);
tempValue = Double.longBitsToDouble(i);
tempValue = tempValue * (1.5d - xhalf * tempValue * tempValue);
tempValue = this.value * tempValue;
return tempValue;
}
Comparsion:比較
筆者建立了一個專門的單元測試類來比較上述算法的準確度與性能，代碼參考SquareRootsTest，首先在準確度與穩定性測試方面，這幾種算法都能達到較好地穩定性，其中平方根倒數速算法相對而言是較好。
@Test
public void testBabylonian() {
for (int i = 0; i < 10000; i++) {
Assert.assertEquals(2.166795861438391, squareRoots.Babylonian(), 0.000001);
}
}
@Test
public void testTSqrt() {
for (int i = 0; i < 10000; i++) {
Assert.assertEquals(2.166795861438391, squareRoots.TSqrt(), 0.000001);
}
}
@Test
public void testFastInverseSquareRoot() {
for (int i = 0; i < 10000; i++) {
Assert.assertEquals(2.1667948388864198, squareRoots.FastInverseSquareRoot(), 0.000001);
}
}
而在性能測試方面，級數逼近的性能最差，巴比倫算法次之，平方根倒數速算法最好:
@Test
public void benchMark() {
//巴比倫算法計時器
long babylonianTimer = 0;
//級數逼近算法計時器
long tSqrtTimer = 0;
//平方根倒數速算法計時器
long fastInverseSquareRootTimer = 0;
//隨機數生成器
Random r = new Random();
for (int i = 0; i < 100000; i++) {
double value = r.nextDouble() * 1000;
SquareRoots squareRoots = new SquareRoots(value);
long start, stop;
start = System.currentTimeMillis();
squareRoots.Babylonian();
babylonianTimer += (System.currentTimeMillis() - start);
start = System.currentTimeMillis();
squareRoots.TSqrt();
tSqrtTimer += (System.currentTimeMillis() - start);
start = System.currentTimeMillis();
squareRoots.FastInverseSquareRoot();
fastInverseSquareRootTimer += (System.currentTimeMillis() - start);
}
System.out.println("巴比倫算法:" + babylonianTimer);
System.out.println("級數逼近算法:" + tSqrtTimer);
System.out.println("平方根倒數速算法:" + fastInverseSquareRootTimer);
}
/**
結果為:
巴比倫算法:17
級數逼近算法:34
平方根倒數速算法:7
**/
總結
以上是生活随笔為你收集整理的python牛顿法计算平方根_常用的平方根算法详解与实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python远程调用摄像头_Python
- 下一篇： mysql snowflake_雪花算法