在C++中实现double sqrt（double x）

问题描述：

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

这是我在这里看到的面试面试问题。 http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm 任何相关的好主意吗？...

!!!编辑。!!!（不使用std库）。

`的#include `[换行符]`双SQRT（双X）{返回的std :: SQRT（X）; }` – 2011-02-15 05:18:44

@James：我在想`#include `[newline]`double sqrt（double x）{return std :: pow（x，0.5）; }` – 2011-02-15 05:23:09

http：//en.wikipedia。org/wiki/Newton％27s_method – Anycorn 2011-02-15 05:24:53

答

Look here。这个CodeProject文章比较了14种不同的计算平方根的方法。

答

这里是一个可以在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; 
}

答

两个明显的答案是平分（半缓）和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指令将会胜过这个（或者其他任何你可以写的东西）。

答

如果我允许使用日志（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

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

在C++中实现double sqrt（double x）

相关推荐