牛顿迭代法求平方根及其推广

    一天晚上，本蒟蒻没有写代码，在水群，群里的奆佬说他在面试的时候HR叫他写一个求平方根的代码，这哥们写了一个十分大众的二分，结果那个HR说；”你写的太简单了“！！！，我凸(艹皿艹 )，不就是二分吗？还有其他骚操作？群里的其他奆佬就问:“牛顿迭代法？”，哇~~~开眼界了，今天闲来无事就去看了看，发现数学是真的奇妙。

 

    其他的废话就不扯了，感谢这位叫马同学的奆佬的博客让我浅显的明白了牛顿迭代法的原理以及实现过程 点击打开链接 。

    和二分差不多，牛顿迭代法采取逼近零点的方法得到近似零点的值（因为是逼近）。我们先随便找一个合法的x为起点，迭代公式为x=(x+a/x)/2，在很少的迭代后就可以得到√a很精确的解。求√a我们可以看成y=x*x-a的解，如图我们以A点为起点，先求在A点切线，在求出切线与x轴的交点，在以与x轴交点的正上面的B点为起点重复上面的迭代，求通过A点求B点的公式化简下来就为x=(x+a/x)/2。

这个神奇的牛顿迭代法可以在很少的迭代次数里求出很高进度的平方根，相比二分（50-70次循环）牛顿迭代法（10+，20+次循环）要快很多，而且在同一个eps的情况下，牛顿迭代法的精度也比二分高，但是都没有sqrt函数强大，sqrt函数不管是精度还是速度都是非常高的，是一个奆奆奆佬写的，写的非常巧妙，不过牛顿迭代法还可以推广到高次，速度精度还算可观，不过经历过太多次的平方和除法运算，精度还是有问题，所以...................

牛顿迭代法，二分，sqrt函数的比较代码：

#include<stdio.h>
#include<string.h>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ll long long
#define ull unsigned long long
#define qq printf("QAQ\n");
using namespace std;
const int maxn=1e5+5;
const int inf=2e9+1e8+12345;
const ll mod=1e9+7;
const ull hmod1=19260817;
const ull hmod2=19660813;
const double eps=1e-10;
const double e=exp(1.0);
const double pi=acos(-1);
int num;
double newton(double a)//牛顿迭代法求平方根
{
    double ans=max(a,1.0);
    int t=30;
    num=0;
    while(abs(ans*ans-a)>eps)
    //while(t--)
    {
        ans=(ans+a/ans)/2;
       num++;//printf("%.10f\n",ans);
    }
    cout<<num<<endl;
    return ans;
}
double f(double a)//二分求平方根
{
    double mid,l=0,r=max(a,1.0);
    while(abs(mid*mid-a)>eps)
    {
        mid=(l+r)/2;
        if(mid*mid-a<eps)l=mid;
        else r=mid;
        num++;//printf("%.10f\n",mid);
    }
    cout<<num<<endl;
    return mid;
}
double quick_pow(double a,int n)
{
    double ans=1.0;
    while(n)
    {
        if(n&1)ans=ans*a;
        n/=2;
        a=a*a;
    }
    return ans;
}
double hsqrt(double a,int n)//高次根
{
    double ans=max(a,1.0);
    num=0;
    while(abs(quick_pow(ans,n)-a)>eps)
    {
        ans=((n-1)*quick_pow(ans,n)+a)/(n*(quick_pow(ans,n-1)));
        num++;
    }
     cout<<num<<endl;
    return ans;
}
bool judge(int a)
{
    for(int i=2;i*i<=a;i++)
        if(a%i==0)return 0;
    return 1;
}
int main()
{
    double t;
    string s;
    while(cin>>t)
    {
        printf("%.15f\n",f(t));
        printf("%.15f\n",newton(t));
        printf("%.15f\n",hsqrt(t,2));
        printf("%.15f\n",sqrt(t));
    }
    return 0;
}