總體思路，一步步逼近。

如何逼近呢？三個(gè)方法：

1. 基本二分法：折半。 線性逼近
2. Newton's 逼近；
   一次導(dǎo)數(shù)逼近：
3. 泰勒級(jí)數(shù)；（啊，回憶起了被高數(shù)支配的大學(xué)時(shí)光@_@）

這是用電子紙寫(xiě)的，不好用還貴，字也被弄的扭曲變形了，我的字比這好看多了

泰勒級(jí)數(shù)

泰勒(Taylor)中值定理 如果函數(shù)f(x)在定義在a附近的平滑函數(shù)f最近似的多項(xiàng)式被稱為關(guān)于x =a的N階泰勒多項(xiàng)式, 即

該公式稱為f(x)按(x-a)的冪展開(kāi)的n階泰勒公式。余項(xiàng)Rn(x)有多種形式。

在泰勒公式中，如果取a=0，則可得到所謂的麥克勞林(Maclaurin)公式：

我們要求開(kāi)平方根，那么把f(x)設(shè)為√x是不是就可以了呢？讓我們?cè)囋嚳辞笏膶?dǎo)數(shù)。

• f(x)=√x

• f'(x)=(√x)'

根據(jù)導(dǎo)數(shù)公式

• (x^u)' =u·x^(u-1)
• f'(x)=(x^(1/2))'=1/(2√x)

然后把0帶入，發(fā)現(xiàn)0在分母位置。所以把f(x)設(shè)為√x無(wú)法運(yùn)用麥克勞林公式。比如把f(x)設(shè)為√(x+1)

• f(x)=√(x+1)則f'(x)=1/(2√(x+1))

我們可以繼續(xù)計(jì)算得到2階，3階導(dǎo)數(shù)。

“函數(shù)展開(kāi)成冪級(jí)數(shù)”就是指，是否能找到這樣一個(gè)冪級(jí)數(shù)，它在某個(gè)區(qū)間內(nèi)收斂，且其和恰好就是給定的函數(shù)f(x)，如果能找到這樣的冪級(jí)數(shù)，我們就說(shuō)，函數(shù)f(x)在該區(qū)間內(nèi)能展開(kāi)成冪級(jí)數(shù)，或簡(jiǎn)單地說(shuō)函數(shù)f(x)能展開(kāi)成冪級(jí)數(shù)，而該級(jí)數(shù)在收斂區(qū)間內(nèi)就表達(dá)了函數(shù)f(x)。
有這樣一個(gè)定理 設(shè)函數(shù)f(x)在點(diǎn)x0的某個(gè)領(lǐng)域U(x0)內(nèi)具有各階導(dǎo)數(shù)，則f(x)在該領(lǐng)域內(nèi)能展開(kāi)成泰勒級(jí)數(shù)的充分必要條件是f(x)的泰勒公式中的余項(xiàng)Rn(x)當(dāng)n->∞時(shí)的極限為零。
所以函數(shù)展開(kāi)成冪級(jí)數(shù)是有條件的。對(duì)于√(x+1)=1+(1/2)x-(1/8)x^2+(1/16)x3+... 條件是-1<=x<=1。具體計(jì)算過(guò)程請(qǐng)看《高等數(shù)學(xué)》下冊(cè)第十一章第四節(jié)例6。

對(duì)于x的特殊要求 所以 我們求√(17) = √(16+1) = 4 * √(1+1/16). -1<= 1/16 <= 1.
所以√(17) = 4(1+1/21/16-1/8(1/16)^2+1/16(1/16)^3+...)
所以誤差 取決于我們省略號(hào)省略了什么。

• 二分法

int sqrt(int x) {
    long long i = 0;
    long long j = x / 2 + 1;// 為了防止溢出
    while (i <= j)//起初直接思路是：用x與mid * mid比較，但是用區(qū)間夾，誤差更小
    {
        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;
}

• 迭代逼近 （相當(dāng)于二分法的優(yōu)化，區(qū)間單端調(diào)整）

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;
}

• 泰勒級(jí)數(shù)

double Tsqrt(double x)//計(jì)算[0,2)范圍內(nèi)數(shù)的平方根
{
    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)//假設(shè)誤差為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)//讓括號(hào)整體的值,相當(dāng)于之前提的(1+x),在區(qū)間[0,2)；
{
    double correction=1;
    while(x>=2)
    {
        x/=4;
        correction*=2;
    }
    return Tsqrt(x)*correction;
}