因?yàn)椴皇强瓢喑錾恚约词咕幊桃欢螘r(shí)間也時(shí)常感覺自身基礎(chǔ)知識非常不扎實(shí)，于是在最近開始補(bǔ)習(xí)算法和計(jì)算機(jī)理論的基礎(chǔ)知識。
目前看的算法書籍是《算法》（第四版），由Robert Sedgewick以及Kevin Wayne編寫的，由于不可能把所有的練習(xí)都寫成博客記錄下來，于是就在學(xué)習(xí)過程中，挑選一些有意思的寫成筆記，以便日后參考以及與同行互相交流。
今天要準(zhǔn)備寫的就是非常經(jīng)典的牛頓迭代法求平方根，事實(shí)上現(xiàn)在的絕大部分編程語言中，標(biāo)準(zhǔn)庫中都已經(jīng)為我們準(zhǔn)備好了計(jì)算平方根的函數(shù)，但是本著學(xué)習(xí)的精神，今天我們也要寫出一個(gè)求平方根的函數(shù)。
牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。方法使用函數(shù) f(x)的泰勒級數(shù)的前面幾項(xiàng)來尋找方程f(x)=0的根。首先我們先來看函數(shù)圖像。
首先，選擇一個(gè)接近函數(shù)f(x)零點(diǎn)的x0,計(jì)算相應(yīng)的f(x0)和切線斜率f'(x0)（這里f'表示函數(shù)f的導(dǎo)數(shù))。
也就是求如下方程的解：
我們將新求得的點(diǎn) x坐標(biāo)命名為x1，通常x1會比x0更接近方程f(x)=0的解。因此我們現(xiàn)在可以利用x1開始下一輪迭代。迭代公式可化簡為如下所示：
而求平方根的方程我們可以看成f(x) = x^2 - a,a即為我們要求平方根的常數(shù)。
于是在算法代碼的編寫上，我們也可以用這種猜的思想，來近似求解這個(gè)平方根，我們需要定義一個(gè)精度，若Xn+1-Xn的值小于我們的精度值，那么我們即可以認(rèn)為Xn為我們要求的解。
所以算法代碼編寫如下(采用Java示例)。
/**
* 牛頓迭代法求平方根
* @param number 求值的數(shù)
* @param accuracy 精度
* @return Double
*/
public static double NewtonSqrt(double number, double accuracy) {
//第一個(gè)猜測值
double guess = number / 2;
int count = 0;
if (number < 0) {
return Double.NaN;
}
//當(dāng)兩個(gè)猜測的差值大于精度即return
while (Math.abs(guess - (number / guess)) > accuracy) {
//迭代公式推導(dǎo)而成
guess = (guess + (number / guess)) / 2;
count++;
System.out.printf("try count = %d, guess = %f\n", count, guess);
}
System.out.printf("final result = %f\n", guess);
return guess;
}
牛頓迭代法求平方根的代碼就如上面所示，而接下來為了體現(xiàn)牛頓迭代法的優(yōu)勢，我們再寫一個(gè)二分法計(jì)算平方根的算法，來對比：
public static double DichotomySqrt(double number, double accuracy) {
double higher = number;
double lower = 0.0;
double middle = (lower + higher) / 2;
double last_middle = 0.00;
int count = 0;
if (number < 0) {
return Double.NaN;
}
while (Math.abs(middle - last_middle) > accuracy) {
if (middle * middle > number) {
higher = middle;
} else {
lower = middle;
}
last_middle = middle;
middle = (lower + higher) / 2;
count++;
System.out.printf("Dichotomy try count = %d, guess = %f\n", count, last_middle);
}
System.out.printf("Dichotomy final result = %f\n", last_middle);
return last_middle;
}
二分法的講解就不多說了，跟牛頓迭代法的驗(yàn)證結(jié)果相似，看精度差是否在定義范圍內(nèi)。
那么接下來我們來測試二分法和牛頓迭代法求值的效率。
public static void main(String[] args) {
double result = NewtonSqrt(2,1e-3);
double dichotomyRes = DichotomySqrt(2,1e-3);
}
先看小精度情況下，求2的平方根
try count = 1 guess = 1.5
try count = 2 guess = 1.4166666666666665
try count = 3 guess = 1.4142156862745097
final result = 1.4142156862745097
Dichotomy try count = 1 guess = 1.0
Dichotomy try count = 2 guess = 1.5
Dichotomy try count = 3 guess = 1.25
Dichotomy try count = 4 guess = 1.375
Dichotomy try count = 5 guess = 1.4375
Dichotomy try count = 6 guess = 1.40625
Dichotomy try count = 7 guess = 1.421875
Dichotomy try count = 8 guess = 1.4140625
Dichotomy try count = 9 guess = 1.41796875
Dichotomy try count = 10 guess = 1.416015625
Dichotomy final result = 1.416015625
可以看到牛頓迭代法計(jì)算了3次，二分法計(jì)算了10次。
而精度稍大的時(shí)候
public static void main(String[] args) {
double result = NewtonSqrt(2,1e-15);
double dichotomyRes = DichotomySqrt(2,1e-15);
}
try count = 1 guess = 1.5
try count = 2 guess = 1.4166666666666665
try count = 3 guess = 1.4142156862745097
try count = 4 guess = 1.4142135623746899
try count = 5 guess = 1.414213562373095
final result = 1.414213562373095
Dichotomy try count = 1 guess = 1.0
Dichotomy try count = 2 guess = 1.5
Dichotomy try count = 3 guess = 1.25
Dichotomy try count = 4 guess = 1.375
Dichotomy try count = 5 guess = 1.4375
Dichotomy try count = 6 guess = 1.40625
Dichotomy try count = 7 guess = 1.421875
Dichotomy try count = 8 guess = 1.4140625
Dichotomy try count = 9 guess = 1.41796875
Dichotomy try count = 10 guess = 1.416015625
Dichotomy try count = 11 guess = 1.4150390625
Dichotomy try count = 12 guess = 1.41455078125
Dichotomy try count = 13 guess = 1.414306640625
Dichotomy try count = 14 guess = 1.4141845703125
Dichotomy try count = 15 guess = 1.41424560546875
Dichotomy try count = 16 guess = 1.414215087890625
Dichotomy try count = 17 guess = 1.4141998291015625
Dichotomy try count = 18 guess = 1.4142074584960938
Dichotomy try count = 19 guess = 1.4142112731933594
Dichotomy try count = 20 guess = 1.4142131805419922
Dichotomy try count = 21 guess = 1.4142141342163086
Dichotomy try count = 22 guess = 1.4142136573791504
Dichotomy try count = 23 guess = 1.4142134189605713
Dichotomy try count = 24 guess = 1.4142135381698608
Dichotomy try count = 25 guess = 1.4142135977745056
Dichotomy try count = 26 guess = 1.4142135679721832
Dichotomy try count = 27 guess = 1.414213553071022
Dichotomy try count = 28 guess = 1.4142135605216026
Dichotomy try count = 29 guess = 1.414213564246893
Dichotomy try count = 30 guess = 1.4142135623842478
Dichotomy try count = 31 guess = 1.4142135614529252
Dichotomy try count = 32 guess = 1.4142135619185865
Dichotomy try count = 33 guess = 1.4142135621514171
Dichotomy try count = 34 guess = 1.4142135622678325
Dichotomy try count = 35 guess = 1.4142135623260401
Dichotomy try count = 36 guess = 1.414213562355144
Dichotomy try count = 37 guess = 1.4142135623696959
Dichotomy try count = 38 guess = 1.4142135623769718
Dichotomy try count = 39 guess = 1.4142135623733338
Dichotomy try count = 40 guess = 1.4142135623715149
Dichotomy try count = 41 guess = 1.4142135623724243
Dichotomy try count = 42 guess = 1.414213562372879
Dichotomy try count = 43 guess = 1.4142135623731065
Dichotomy try count = 44 guess = 1.4142135623729928
Dichotomy try count = 45 guess = 1.4142135623730496
Dichotomy try count = 46 guess = 1.414213562373078
Dichotomy try count = 47 guess = 1.4142135623730923
Dichotomy try count = 48 guess = 1.4142135623730994
Dichotomy try count = 49 guess = 1.4142135623730958
Dichotomy try count = 50 guess = 1.414213562373094
Dichotomy final result = 1.414213562373094
這里就一目了然了，所以有時(shí)候，寫代碼一定不能想著功能實(shí)現(xiàn)了就好，在算法的效率上一定要多多思考。
不再舉栗子了，免得有湊字?jǐn)?shù)的嫌疑。下次再討論咯。
