面試題:如何求根號2

來源：算法面試題

問題

小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·

 近期熱文：

關注我

點擊「閱讀原文」，看本號其他精彩內容