原文：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 accuracyreturn 1/x;
}