c++ - 精确求平方根

Question

我刚刚回顾了各个公司在面试中提出的问题。我发现一个是“找到一个数字的平方根到一个精度。函数定义应该是这样的:double getSquareRoot(int num, int precision)”。

我写了一个小函数，它给出平方根但不关心精度:

double getSquareRoot(int num){
 int num1=0, num2=0;
 for(int i=1 ;; i++){
   if(i*i == num){
    std::cout<<i <<" is the sq root"<<std::endl;
    break;
   }
  else if(i*i > num){
   num2 = i;
   num1 = --i;
   break;
  }
} 
 // in the above for loop, i get the num1 and num2 where my input should lie 
 // between them
 // in the 2nd loop below.. now i will do the same process but incrementing 
 // by 0.005 each time
for(double i =num1;i<(double)num2;i+=0.005)
  {
   if(i*i>= num){
     std::cout<<(double)i <<" is the sq root"<<std::endl;
     break;
   }
 }
}

现在为了达到精确度，我将不得不做一些调整，比如添加 if 循环等等。我不喜欢那样。你们能帮帮我吗？如果您正在编写代码，请说明。我将不胜感激。

谢谢。

此代码非常不足，无法解决问题的“直到这个精度”部分。我写它只是为了让你们不要认为我尝试了一点。这个

Answer 1

在我脑海中，有两种方法:

• 使用interval bisection ;您知道误差不超过当前区间宽度，因此一旦区间小于所需精度就停止迭代。这非常简单，但收敛速度不如其他方法。
• 使用迭代方法，例如 Newton's method (在用于计算平方根时也称为 Babylonian method)，并在每次迭代后估计误差。

为了估计误差，假设我们试图找到 x0 = sqrt(y)，这样 x0*x0 = y。每次迭代后，我们都有一个候选 x = x0 + d，我们要估计误差 d。如果我们对 x 求平方，则我们得到

x*x = x0*x0 + 2*x0*d + d*d
    = y + 2*(x-d)*d + d*d
   ~= y + 2*x*d

丢弃 d*d 项，随着 d 变小，它变得非常小。所以我们可以将误差估计为

d ~= (x*x - y) / (2*x)
   = (x - y/x) / 2

一旦小于要求的精度就停止迭代。

如果您使用的是巴比伦方法，那么这会为迭代计算增加很少的工作，x = (x + y/x)/2，所以结果类似于

double sqrt(double y, double precision)
{
    double x = y;  // or find a better initial estimate
    for (;;) {
        double z = y/x;
        if (std::abs(x-z) < 2*precision)
            return x;
        x = (x+z)/2;
    }
}