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

Question

在 C++ 中实现 double sqrt(double x) 而不使用 std 库。

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

！编辑。！！！（不使用标准库。）

Answer 1

请查看此处。这篇 CodeProject 文章比较了 14 种不同的计算平方根的方法。

Answer 2

两个明显的答案是二分法（半慢）和牛顿拉夫森/莱布尼兹迭代（通常更快）。为了避免破坏任何人的乐趣，我将对这个问题进行重新解释 - 这是使用 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 3

这是最天才的 sqrt 实现之一，可以在 wikipedia 上找到。它不是最准确的，但速度非常快。

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

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