Posted on 2013-04-15 10:19
小明 阅读(1445)
评论(0) 编辑 收藏 所属分类:
数据结构和算法
学过数值分析的都知道牛顿迭代法
令f(x) = x
2-a;
那么上式就变成:
x
n+1 =x
n-(x
n2-a)/(2*x
n)=(x
n+a/x
n)/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;
}
}