总体思路，一步步逼近。
如何逼近呢？三个方法：
- 基本二分法：折半。 线性逼近
- Newton's 逼近；
一次导数逼近： - 泰勒级数；（啊，回忆起了被高数支配的大学时光@_@）
这是用电子纸写的，不好用还贵，字也被弄的扭曲变形了，我的字比这好看多了
泰勒级数
泰勒(Taylor)中值定理 如果函数f(x)在定义在a附近的平滑函数f最近似的多项式被称为关于x =a的N阶泰勒多项式, 即
该公式称为f(x)按(x-a)的幂展开的n阶泰勒公式。余项Rn(x)有多种形式。
在泰勒公式中，如果取a=0，则可得到所谓的麦克劳林(Maclaurin)公式：
我们要求开平方根，那么把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)x2+(1/16)x3+... 条件是-1<=x<=1。具体计算过程请看《高等数学》下册第十一章第四节例6。
对于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+...)
所以误差 取决于我们省略号省略了什么。
- 二分法
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;
}
