2018-12-18


面试题:如何求根号2

Great Eagle 程序猿DD 

来源:算法面试题

问题

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

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

思路

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

代码实现

牛顿迭代法(JavaScript)


//求n的算术平方根,参数n不能为负数

functionsqrt(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

floatinvSqrt(floatx){

    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;

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • “区块链”作为2018年最被关注的行业,许多人对于这个陌生的领域,都会用带有千万种疑问的眼光去看待它,尤其是对一些...
    山高云飞阅读 1,501评论 0 0
  • LeetCode 63. Unique Paths II Description A robot is locat...
    ruicore阅读 1,417评论 0 0
  • 又征召能治河者上百人,他们提供的战略各有不同,长水校尉、平陵人关并说:“黄河决口,主要是在平原、东郡左右,因为当地...
    华杉2009阅读 4,796评论 1 12
  • 如果你没有50年的洞见,那么你至少要有5年的眼光;如果你没有5年的眼光,那你至少要有1年的梦想;如果你没有1年的梦...
    雨杉_aaf5阅读 955评论 0 0
  • 什么东西再轰轰烈烈也会有趋于平平淡淡,平静的一天,无论是爱情还是生活。我相信没有一个人会一直对一个人好下去,再热烈...
    s宋华露阅读 1,878评论 0 0