每日一面 - sqrt (2)约等于 1.414，如何求sqrt (2)小数点后 10 位

本问题参考自：https://www.zhihu.com/question/410210858/answer/1365984008 答案为个人原创

1.从 1.414 向下一位开始，二分法查找平方最接近2的数字。效率比较差。

2.使用牛顿迭代法:

• x初始等于1.414
• 不断令x等于x和2/x的平均数，然后求每次x的平方，看与2的差距
• 这样比之前的二分法要精简很多次运算。

这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入 f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2

1. Chris Lomont 魔法数 + 牛顿迭代，这个偏离了本题条件，因为本题给了初始数字1.414，但是对于没有初始猜想的数字，使用魔法数字 0x5f375a86 (源代码注释是：what the fxxk？？？，哈哈哈哈哈，这个数字太匪夷所思了，但是这就是数学的魅力)猜想初始数字，比x等于x和2/x的平均数这个初始数字，进行开方平均效率高很多，具体计算过程是：

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;
}

这个函数返回的是1/sqrt(x)，这个比sqrt(x)更常用于图像处理，参考这篇论文理解为啥是 0x5f375a86: http://www.matrix67.com/data/InvSqrt.pdf