c++ - 在 C++ 中实现 double sqrt(double x)

Question

在不使用 std 库的情况下用 C++实现double sqrt(double x)。

这是我在这里看到的一个 Facebook 面试问题。http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm 关于这个还有什么好主意吗？...

!!!Edited.!!!（不使用标准库。）

Answer 1

看这里。这篇 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 ——这是一个使用 Newton-Raphson 技术的 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找到设置为获得 log ₂ x 粗略近似值的最高有效位，然后将其除以 2 以获得初始近似值。

OTOH，这真的只在古代处理器上才有意义。对于自 486（左右）以来具有内置浮点硬件的任何东西，几乎可以肯定该FSQRT指令会击败这个（或几乎任何你可以编写的东西）。

Answer 4

如果我被允许使用 log (ln) 和 exp 那么当然 exp(log(x)/2) 会给我平方根。

假设不是：

如果我们发现sqrt的值是x并且起始值是y，那么我们迭代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^(log base 2(x)/2) 作为起点而不是 1。385 的对数介于 8 和 9 之间，因此如果我们说 8.5，因此从 2^4.25 开始。如果我们在 16 和 32 之间进行线性计算，那么我们将从 20 开始。

从 20 开始，我只需 4 个步骤即可到达：

20
19.625
19.6214172
19.62141687

但它需要以前的“迭代”来计算近似对数和指数。