c++ - 不使用 sqrt 函数求平方根？

Question

我在不使用 sqrt 函数的情况下找出求平方根的算法，然后尝试将其用于编程。我最终在 C++ 中得到了这个工作代码

    #include <iostream>
    using namespace std;

    double SqrtNumber(double num)
    {
             double lower_bound=0; 
             double upper_bound=num;
             double temp=0;                    /* ek edited this line */

             int nCount = 50;

        while(nCount != 0)
        {
               temp=(lower_bound+upper_bound)/2;
               if(temp*temp==num) 
               {
                       return temp;
               }
               else if(temp*temp > num)

               {
                       upper_bound = temp;
               }
               else
               {
                       lower_bound = temp;
               }
        nCount--;
     }
        return temp;
     }

     int main()
     {
     double num;
     cout<<"Enter the number\n";
     cin>>num;

     if(num < 0)
     {
     cout<<"Error: Negative number!";
     return 0;
     }

     cout<<"Square roots are: +"<<sqrtnum(num) and <<" and -"<<sqrtnum(num);
     return 0;
     } 

现在的问题是在声明中初始化迭代次数 nCount(这里是 50)。例如求 36 的平方根需要 22 次迭代，所以没有问题，而求 15625 的平方根需要 50 多次迭代，所以它会在 50 次迭代后返回 temp 的值。请给出解决方案。

Answer 1

有一种更好的算法，最多需要 6 次迭代才能收敛到 double 的最大精度:

#include <math.h>

double sqrt(double x) {
    if (x <= 0)
        return 0;       // if negative number throw an exception?
    int exp = 0;
    x = frexp(x, &exp); // extract binary exponent from x
    if (exp & 1) {      // we want exponent to be even
        exp--;
        x *= 2;
    }
    double y = (1+x)/2; // first approximation
    double z = 0;
    while (y != z) {    // yes, we CAN compare doubles here!
        z = y;
        y = (y + x/y) / 2;
    }
    return ldexp(y, exp/2); // multiply answer by 2^(exp/2)
}

算法从 1 开始，作为平方根值的第一近似值。然后，在每一步，它通过取当前值 y 之间的平均值来改进下一个近似值。和 x/y .如果 y = sqrt(x) ，它会是一样的。如果 y > sqrt(x) ，然后 x/y < sqrt(x)大约相同的数量。换句话说，它会很快收敛。

更新:为了加快在非常大或非常小的数字上的收敛速度，更改了 sqrt()从[1, 4)中的数字提取二进制指数并计算平方根的函数范围。它现在需要 frexp()来自 <math.h>获得二进制指数，但可以通过从 IEEE-754 数字格式中提取位而不使用 frexp() 来获得该指数.