仔細回味二分法 演算法：sqrt() 方法的實現
總體思路，一步步逼近。
如何逼近呢？三個方法：
- 基本二分法：折半。 線性逼近
- Newton's 逼近；
一次導數逼近： - 泰勒級數；（啊，回憶起了被高數支配的大學時光@_@）
這是用電子紙寫的，不好用還貴，字也被弄的扭曲變形了，我的字比這好看多了
泰勒級數
泰勒(Taylor)中值定理如果函式f(x)在定義在a附近的平滑函式f最近似的多項式被稱為關於x =a的N階泰勒多項式, 即
該公式稱為 f(x)按(x-a)的冪展開的n階泰勒公式 。餘項Rn(x)有多種形式。
在泰勒公式中，如果取a=0，則可得到所謂的 麥克勞林(Maclaurin)公式 ：
Line"/>
我們要求開平方根，那麼把f(x)設為√x是不是就可以了呢？讓我們試試看求它的導數。
-
f(x)=√x
-
f'(x)=(√x)'
根據導數公式
- (x^u)' =u·x^(u-1)
- f'(x)=(x^(1/2))'=1/(2√x)
然後把0帶入，發現0在分母位置。所以把f(x)設為√x無法運用麥克勞林公式。比如把f(x)設為√(x+1)
- f(x)=√(x+1)則f'(x)=1/(2√(x+1))
我們可以繼續計算得到2階，3階導數。
“函式展開成冪級數”就是指，是否能找到這樣一個冪級數，它在某個區間內 收斂 ，且其和恰好就是給定的函式f(x)，如果能找到這樣的冪級數，我們就說，函式f(x)在該區間內能展開成冪級數，或簡單地說函式f(x)能展開成冪級數，而該級數在收斂區間內就表達了函式f(x)。
有這樣一個定理 設函式f(x)在點x0的某個領域U(x0)內具有各階導數，則f(x)在該領域內能展開成泰勒級數的充分必要條件是f(x)的泰勒公式中的餘項Rn(x)當n->∞時的極限為零。
所以函式展開成冪級數是有條件的。對於√(x+1)=1+(1/2)x-(1/8)x 2+(1/16)x 3+... 條件是-1<=x<=1。具體計算過程請看《高等數學》下冊第十一章第四節例6。
對於x的特殊要求 所以 我們求√(17) = √(16+1) = 4 * √(1+1/16). -1<= 1/16 <= 1.
所以√(17) = 4 (1+1/2 1/16-1/8 (1/16)^2+1/16 (1/16)^3+...)
所以誤差 取決於我們省略號省略了什麼。
- 二分法
int sqrt(int x) {
long long i = 0;
long long j = x / 2 + 1;// 為了防止溢位
while (i <= j)//起初直接思路是：用x與mid * mid比較，但是用區間夾，誤差更小
{
long long mid = (i + j) / 2;
long long sq = mid * mid;
if (sq == x) return mid;
else if (sq < x) i = mid + 1;
else j = mid - 1;
}
return j;
}
- 迭代逼近 （相當於二分法的優化，區間單端調整）
double sqrt(double x) {
if (x == 0) return 0;
double last = 0.0;
double res = 1.0;
while (res != last)
{
last = res;
res = (res + x / res) / 2;
}
return res;
}
- 泰勒級數
double Tsqrt(double x)//計算[0,2)範圍內數的平方根
{
double sum,coffe,factorial,xpower,term;
int i;
sum=0;
coffe=1;
factorial=1;
xpower=1;
term=1;
i=0;
while(ABS(term)>0.000001)//假設誤差為0.000001
{
sum+=term;
coffe*=(0.5-i);
factorial*=(i+1);
xpower*=(x-1);
term=coffe*xpower/factorial;
i++;
}
return sum;
}
double sqrt2(double x)//讓括號整體的值,相當於之前提的(1+x),在區間[0,2)；
{
double correction=1;
while(x>=2)
{
x/=4;
correction*=2;
}
return Tsqrt(x)*correction;
}