感谢杨工，让我更加认识到自己技术薄弱，这道题源自于和杨工的非正式面试，当时根本没思路，甚至没和查找有丝毫的联系，看来做自己想做的还是要付出努力的。sqrt()即开平方运算，y=x*x,已知Y的情况下求解X的值，基本的思路是找个区间，逐步计算逼近，知道需要的精度。
（1）二分查找
并不是严格的二分查找，设定寻找的区间，在这个区间中一直取中点，计算中点的平方和Y的查找，逐步逼近，直到自己需要的精度：
#define ABS_FLOAT 0.000001bool eqs(double val1 , double val2){ double diff = fabs(val1 - val2) ; if(diff < ABS_FLOAT) { return true ; } else { return false ; }}//获取开方值，二分查找的方法double SqrtBybisection(double _value){ if (_value <= 0 ) return 0 ; double low = 0.0; double high = 0.0 ; if (_value > 0 && _value < 1) { low = _value; high = 1.0 ; } else { low = 1.0 ; high = _value ; } double mid = (low + high)/2.0 ; double last = 0.0 ; do { if (mid * mid > _value) { high = mid ; } else { low = mid ; } last = mid ; mid = (high + low )/ 2.0 ; //std::cout << mid << std::endl ; }while(! eqs( last , mid)) ; return mid ;}
牛顿迭代法通过泰勒公司展开，通过切线逐步逼近，具体推到可以参考： ， sqrt实现的代码：
//牛顿迭代法求解 /* f(x) = x^2 - v --> x = x0 - f(x0)/2x0 -->x = (x0 + v / x0) / 2 ; -->*/double SqrtByNewton(const double& _val){ double nrt = _val ; double last_nrt = 0 ; while (! eqs( nrt , last_nrt)) { last_nrt = nrt ; nrt = (nrt + _val / nrt) / 2.0 ; } return nrt ;} 3 技巧算法
看到这种解法，我也很惊讶，程序员真是无底线啊~~
先看看浮点数表示，浮点数不论是float还是double在存储方式上都是遵从IEEE的规范的，float遵从的是IEEE R32.24 ,而double 遵从的是R64.53。
数学中浮点用S=M*2^N， 在计算机中 主要由三部分构成：符号位+指数位(N)+尾数(M)，符号位：0为正1为负，指数位：2^M ，移位存储，尾数：即有效数字，规定整数部分为1
float 浮点数内存分布：
| 31 | 30~23 | 22~0 |
| 1 位 符号位 | 8位 指数位 | 23位 尾数 |
| 63 | 62~52 | 51~0 |
| 1 位 符号位 | 11位 指数位 | 52位 尾数 |
| 符号位 | 指数位 | 尾数 |
| 0 | 10000010 | 0001 0000 0000 0000 0000 000 |
float sqrtinv(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;}
这个算法速度据说比系统函数还要快，确实，迭代的步骤少来很多，具体解释和浮点的表示有关，可以参考下文：一般而言，一个float数据 
共32个bit，和int数据一样。其中前23位为有效数字 
，后面接着一个8位数据 
表示指数，最后一位表示符号，由于这里被开方的数总是大于0，所以我们暂不考虑最后一个符号位。此时
如果我们把计算机内的浮点数 看做一个整数 
，那么
现在开始逐步分析函数。这个函数的主体有四个语句，分别的功能是：
int i = *(int*)&x; 这条语句把 转成 
。
i = 0x5f3759df - (i>>1); 这条语句从 计算 
。
y = *(float*)&i; 这条语句将 转换为 
。
y = y*(1.5f - xhalf*y*y); 这时候的y是近似解；此步就是经典的牛顿迭代法。迭代次数越多越准确。关键是第二步 i = 0x5f3759df - (i>>1); 这条语句从 计算 原理:
令
用 
和 
带入之后两边取对数，再利用近似表示
算一算就得到：
若取 
， 
就是程序里所用的常量0x5f3759df。至于为何选择这个 
，则应该是曲线拟合实验的结果。
4 测试结果