java快速开平方

问题

实现 int sqrt(int x);
计算和返回x的平方根。

学过数值分析的都知道牛顿迭代法

令f(x) = x2-a;
那么上式就变成:

xn+1 =xn-(xn2-a)/(2*xn)=(xn+a/xn)/2

实现的代码如下,简单优美,收敛快。

public class Solution {
public int sqrt(int x) {
if(x==0) return 0;
if(x<=2) return 1;
int result = x/2;
while(true){
int next = (result+x/result)/2;
if(next>=result){
break;
}
else{
result = next;
}
};
return result;
}
}

标签