每日一面-sqrt(2)约等于1.414，如何求sq

本问题参考自：www.zhihu.com/question/41… 答案为个人原创

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.5fx;
   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-xhalfxx); // Newton step, repeating increases accuracy
   x = x*(1.5f-xhalfxx); // Newton step, repeating increases accuracy
   x = x*(1.5f-xhalfxx); // Newton step, repeating increases accuracy

   return 1/x;
   复制代码

   }

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

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