在C++中實現double sqrt（double x）

Question

使用C++實現double sqrt(double x)而不使用std庫。

這是我在這裏看到的面試面試問題。 http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm 任何相關的好主意嗎？...

!!!編輯。!!!（不使用std庫）。

Answer 1

Look here。這個CodeProject文章比較了14種不同的計算平方根的方法。

Answer 2

這裏是一個可以在wikipedia被發現的最天才的sqrt實現之一。這不是最準確，但速度非常快。

float fast_sqrt(float number) { 
    long i; 
    float x2, y; 
    const float threehalfs = 1.5F; 

    x2 = number * 0.5F; 
    y = number; 
    i = * (long *) &y;      // floating point bit level hacking [sic] 
    i = 0x5f3759df - (i >> 1);    // Newton's approximation 
    y = * (float *) &i; 
    y = y * (threehalfs - (x2 * y * y)); // 1st iteration 
    y = y * (threehalfs - (x2 * y * y)); // 2nd iteration 
    y = y * (threehalfs - (x2 * y * y)); // 3rd iteration 

    return 1/y; 
} 

Answer 3

兩個明顯的答案是平分（半緩）和Newton-Raphson/Leibniz迭代（通常更快）。爲了保持從破壞任何人的樂趣，我會做關於這個問題的reinterpret_cast的 - 這裏是用牛頓迭代技術在8086彙編語言整數的平方根的實現：

isqrt proc uses di, number:word 
; 
; uses bx, cx, dx 
; 
    mov di,number 
    mov ax,255 
start_loop: 
    mov bx,ax 
    xor dx,dx 
    mov ax,di 
    div bx 
    add ax,bx 
    shr ax,1 
    mov cx,ax 
    sub cx,bx 
    cmp cx,2 
    ja start_loop 
    ret 
isqrt endp 

這是開放的一些改進 - 它使用x/2作爲sqrt（x）的初始猜測。隨着386+的說明，您可以使用bsr發現被設置爲獲取日誌 x的一個粗略的估計最爲顯著位，併除以2得到您的初始近似。

OTOH，這真的只對古代處理器有意義。對於自內置浮點硬件的486（大多數）以來的任何內容，幾乎可以肯定的是，FSQRT指令將會勝過這個（或者其他任何你可以寫的東西）。

Answer 4

如果我允許使用日誌（LN），然後實驗值當然EXP的（LOG（X）/ 2）會給我的平方根。

假設並不：

如果我們的價值，我們發現開方的是X和起始值爲y，則我們反覆Ÿ - >（Y + X/Y）/ 2

終止條件要麼是y與其先前值或y * y與x的接近度。

隨着385我的x值我在反覆獲取這些值（EXCEL）

1 
193 
97.49740933 
50.7231161 
29.15667189 
21.1805984 
19.67880541 
19.62150055 
19.62141687 
19.62141687 

您可以使用 「近似」 2 ^（日誌基地2（X）/ 2）爲起點而不是1. 385有一個介於8和9之間的日誌，所以如果我們說8.5，並且因此以2^4.25開始。如果我們在16和32之間的直線那麼我們將開始與20

20開始我只是4個步驟那裏：

20 
19.625 
19.6214172 
19.62141687 

，但它需要以前的「迭代」來計算近似日誌和指數。