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

末蓝、 2023-01-04 15:58 66阅读 0赞

> 本问题参考自：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][http_www.matrix67.com_data_InvSqrt.pdf]

**每日一刷，轻松提升技术，斩获各种offer：**

![image][]

[http_www.matrix67.com_data_InvSqrt.pdf]: http://www.matrix67.com/data/InvSqrt.pdf
[image]: /images/20221119/9694e02a84c740c098b6912916eadf03.png