求平方根的多种方法
求平方根的多种方法
在编程和算法领域，求平方根是一个常见的问题。本文将介绍多种求平方根的方法，从最简单的内置函数调用，到更复杂的算法实现，如暴力枚举、二分枚举和牛顿迭代法等。这些方法各有优劣，适用于不同的场景。
Top9 sqrt
直接调用math库（C语言）或者cmath库（C++）里内置的求平方根的sqrt函数即可，最后转化为int类型
int mysqrt(int n){
return int(sqrt(n));
}
Top8 pow
用内置的pow函数，简单粗暴
int mysqrt(int n){
return int(pow(n,0.5));
}
Top7 指数恒等式
如果 xx=n 我们要求x的值，两边同时取对数，得 ln(xx)=lnn 即 2lnx=lnn 那么 lnx=lnn/2 所以 x=e^(lnn/2)
这里公式凑活着看（不难，是高中知识），主要是我写的latex公式导不过来
代码我们可以直接返回这个值：
int mysqrt(int n){
return int(exp(log(n) / 2));
}
Top6 精度修正
由于log和exp运算存在精度损失，所以在强制转换为int类型的时候需要加上一个精度（通常是1e-8），把这个精度损失给调整回来
return int(exp(log(n) / 2) + exs);
但是这会导致一个问题，由于引入了浮点数，不同平台的计算结果可能不一样
Top5 暴力枚举
我们从1开始遍历，对于每个数i，如果此时刚有 i*i>=n ，也就是说 (i-1) * (i-1)<n ，因此 i-1 就是我们所求的平方根
int mysqrt(int n){
int i=1;
while(i++){
if(i*i>=n){
return i-1;
}
}
return 0;
}
这个方法的缺点是时间复杂度的提高
Top4 二分枚举
我们发现函数 n-i*i 是一个单调函数，因此我们可以用二分枚举
假设我们要求n的平方根，我们定义一个函数
这里举个例子
显然，我们关注x轴的正方向。随着x的增大，f(x)的值逐渐变小
那么我们要求的n的平方根，即满足 f(x)>=0 的最大整数x即可
int y(int n,int x){ //计算当前f(x)的值
return -x*x+n;
}
int binarysqrt(int n){
int l=0,r=46340;
int ret=-1;
while(l<=r){
int x=(l+r) >> 1; //除以2我们用移位运算符运算更快
if(y(n,x) >= 0){
l = x+1;
ret = x;
}
else{
r = x-1;
}
}
return ret;
}
这个方法每次只能改变一个位（bit），而且还用到乘法，计算较复杂
Top3 牛顿迭代法
我们定义一个函数
那么我们对于函数上一个点 (x,f(x)) ，找到该点对应的切线，切线交x轴于 (x1,0) ，那么就找到了点 (x1,f(x1)) ，按照同样的方法找到 x2 ， x3 ，……如此循环往复，直到无限逼近这条曲线与x轴的交点就是我们所求的平方根
代码如下：
double func(double x,int n){
return x*x - n;
}
int mysqrt(int n){
double x0,x1;
x1=18 //这里随便取一个就行
do{
x0=x1;
double v=func(x0,n);
//切线f'(x) = v + 2x0(x - x0);
x1=-v/(x0*2)+x0;
}while(fabs(x0-x1) > 1e-8);
int ans = (int)(x0+1e-8);
if(ans*ans>n)
--ans;
return ans;
}
牛顿迭代要用到除法更慢了