原文：http://blog.csdn.net/legend050709/article/details/39394381
sqrt算法实现：
（一）int sqrt1(int n);
求取整数x的平方根，向下取整；
（0）步骤：
1.先求出范围；然后排序
2.然后二分查找；
（1）方法一:O(n)
for(int i=0;i*i<n;i++);
i=i-1;
（2）方法二:二分查找，O(lgn)
1)范围已经确定，即0~n,并且0~n之间的数据有序；
2）二分查找：
int sqrt1(int n){
int left=0;
int right=n;
int mid;
int last;
while(left<=right){//应该找出mid*mid<=n的最后一个数
mid=(right-left)/2+left;
if(mid*mid<=n){//寻找最后一个数，所以不断压缩左边，即left=mid+1
last=mid;
left=mid+1;
}else{
right=mid-1;
}
}
return last;
}
（3）方法三：O(lg(2分之根号n))+lg(根号n)
1）先确定范围；O(lg(2分支根号n))
for(int i=n;i*i>n;i=i/2);
j=2*i;
循环结束时，i*i<=n<(2i)*(2i)即i^2<=n<4i^2
然后只需要在i~2i之间寻找一个最大的数k,是的k^2<=n。
2）二分查找：
int left=i,right=j;
while(left<=right){//应该找出mid*mid<=n的最后一个数
mid=(right-left)/2+left;
if(mid*mid<=n){//寻找最后一个数，所以不断压缩左边，即left=mid+1
last=mid;
left=mid+1;
}else{
right=mid-1;
}
}
return last;
----------------------
（二）float sqrt(float x)库函数的实现：
（1）二分法：
const float eps=0.000001; // eps的值可能影响最后计算精度，甚至导致无限循环
// 二分法，注意区分x的取值区间
float SqrtByBisection(float x)
{
if(x<0) // 负数
return x;
if(x<=eps) // 正数0
return 0.0f;
if(fabs(x-1)<=eps) // 正数1
return 1.0f;
float left, right;
float mid;
if(x>eps&&x<1.0f-eps) // (0,1)区间
{
left=x;
right=1.0f;
}
else
{
left=1.0f;
right=x;
}
while(right-left>eps) // （1，）区间
{
mid=(left+right)/2;
if(mid*mid>x+eps)
right=mid;
else if(mid*mid<x-eps)
left=mid;
else
return mid;
}
return mid;
}
---
（2）牛顿迭代算法：
1）示例图如下：
图一，图二：
2）代码实现：
// 牛顿迭代法
const float eps=0.000001; // eps的值可能影响最后计算精度，甚至导致无限循环
float SqrtByNewton(float x)
{
float val=x;
float last;
while(fabs(val-last)>eps)
{
last=val;
val=(val+x/val)/2;
}
return val;
}
----
（3）性能最好：比标准库函数快4倍；（不需要理解，了解即可）
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return 1/x;
}