前言
人蠢要多读书！更加要多动脑！！（To me.）
正文
问题来源
本问题来自leetcode 69题。刚看到这题的时候，就感觉这道题不难（不难的原因是想到直接暴力求解，^A^hehe）。做完这道题提交后，才发现效率不行，没有办法通过。于是乎，上网搜关于这道题的最优解法（优雅姿势）。
1.二分
思路：要实现一个sqrt函数，可以使用二分法，首先确定一个范围[begin, end]，这个范围的中间数mid，看mid的平方是否等于x，如果相等，则返回mid，如果不等则缩小[begin,end]的范围，为原来的一半。这里的初始范围可以是[1, x]，也可以是更精确一些的[1, (x/2) + 1]。（因 (x/2) + 1 的平方等于 x+1+(x^2/4)，它一定大于x，所以，x的平方根一定在[1, (x/2) + 1]范围内）
题目中给出的函数原型是int mySqrt(int x)。参数和返回值都是整数。这里稍微扩展一下，将函数原型改为double mySqrt(int x)。解题思路还是一样的，但是浮点数因精度的原因，无法判断两个浮点数是否完全相等，只能说两者的差值绝对值小于某个精度，所以在二分查找时，需要一定的技巧，具体的代码如下：
double mySqrt_binarysearch(int x)
{
if(x <= 0) return 0;
double begin = 1;
double end = x/2+1;
double mid, lastmid;
mid = begin + (end-begin)/2;
do{
if(mid < x/mid) begin = mid;
else end = mid;
lastmid = mid;
mid = begin + (end-begin)/2;
}
while(ABS(lastmid-mid) > FLT_MIN);
return mid;
}
2.牛顿迭代法
上面的实现方法只能说是中规中矩，但是实现sqrt有更牛逼的方法，就是牛顿迭代法。该方法就是由我们熟知的牛顿提出的。具体思想可以自行搜索。简而言之，如下图：
x^2 = a的解，也就是函数f(x) = x^2 – a与x轴的交点。可以在x轴上先任选一点x0，则点（x0, f(x0)）在f(x)上的切线，与x轴的交点为x1，它们满足切线的方程：f(x0)=(x0-x1)f’(x0)，可得x1更接近最终的结果，解方程得到： x1 = (x0 + (a/x0))/2。以x1为新的x0，按照切线的方法依次迭代下去，最终求得符合精确度要求的结果值。它的实现代码如下：
double mySqrt_newton(int x)
{
if(x <= 0) return 0;
double res, lastres;
res = x; //初始值，可以为任意非0的值
do{
lastres = res;
res = (res + x/res)/2;
}
while(ABS(lastres-res) > FLT_MIN);
return res;
}
3.神迹
下面这段代码出自《雷神之锤》，至今尚未找到该代码的真正作者，代码如下：
float InvSqrt(float x)
{
float xhalf = 0.5f * x;
int i = *(int*)&x;
i = 0x5f375a86 - (i>>1);
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
x = x*(1.5f-xhalf*x*x);
x = x*(1.5f-xhalf*x*x);
return 1/x;
}
它本质上还是使用的牛顿迭代法，真正牛逼的地方在于它初始值的选择，0x5f375a86这个魔法数字的由来尚不可知，该算法的具体原理及其背景可以参见维基百科，不再赘述。
要注意的是，上面算法使用的是float和int类型，实验可知他们不能替换为double和long。
