查看原文
其他

面试题:如何求根号2

程序猿DD 2019-07-13

来源:算法面试题


问题


小E最近找实习的时候,被面试官问了这样一道题:如何求根号2的值?

小E没能答上来,回来后向老师请教。


思路



点评:以上介绍了二分法和牛顿迭代法来求解根号2,另外我们还可以通过泰勒公式法来求解。很多朋友可能会问,我们经常调用的Math库中sqrt(x)函数的实现用的是哪种方法呢?为了效率,sqrt(x)函数在底层是用C语言来实现的,实现过程非常巧妙,效率极高,用到了牛顿迭代法的思想,但又不完全是牛顿迭代法,我会将sqrt(x)库函数的代码放于文后,有兴趣可以研究。


代码实现


牛顿迭代法(JavaScript)

//求n的算术平方根,参数n不能为负数
function sqrt(n) {
    //当n>=1时,从n开始迭代;
    //当n<1时,从1开始迭代
    let res = n >= 1 ? n : 1;
    while(res * res - n > 1e-8)
        res = 0.5 * (res + n / res);
    return res;
}


附:

C语言实现的库函数(源码)


//源码中求的是根号x的倒数,参数x必须大于0
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);
    //注:此函数返回的是根号x的倒数
    return x;
}


复制代码请前往https://blog.csdn.net/Great_Eagle/article/details/84780271

·END·

 近期热文:

关注我

点击“阅读原文”,看本号其他精彩内容

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存