找到平方根到精度

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

在我的头顶,这是两种方法:

• 使用间隔二分 ; 你知道错误不超过当前的间隔宽度,所以一旦间隔小于所需的精度就停止迭代.这很简单,但不像其他方法那样快速收敛.
• 使用迭代方法,如牛顿方法(在用于计算平方根时也称为巴比伦方法),并在每次迭代后估计误差.

为了估计错误,假设我们试图找到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;
    }
}