精度が平方根であることを知るには

Question

私は様々な企業がインタビューで尋ねる質問にちょうど挑戦していました。私は1つが「精度の数値の平方根を求めていることがわかりました。関数定義はこのようなものでなければなりません：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; 
    } 
} 
} 

今精度に到達することを、私はループし、すべての場合には追加のようないくつかの調整を行う必要があります。私はそれが好きではない。あなたはここで私を助けてくれますか？コードを書いているなら、説明してください。私はそれをお願い申し上げます。

ありがとうございました。

このコードは非常に不十分で、問題の「この精度まで」は考慮しません。私はそれを書いたので、あなたは、私がちょっと試したとは思っていません。 これは

です。

Answer 1

、ここでは二つのアプローチです：

• 使用interval bisectionは、エラーが現在の間隔幅を超えていないことがわかっているので、間隔が必要な精度よりも小さくなると、繰り返しを停止します。これは非常に簡単ですが、他の方法ほど速く収束しません。
• Newton's method（平方根の計算に使用する場合はBabylonian methodとも呼ばれます）などの反復方法を使用し、各繰り返し後にエラーを推定します。

誤差を推定するために、x0*x0 = yように、我々は、x0 = sqrt(y)を見つけるためにしようとしているとします。各反復の後、x = x0 + dという候補があり、エラーdを推定したいと考えています。我々平方xなら、私たちはdが小さいにつれて非常に小さくなるd*d用語を、廃棄

x*x = x0*x0 + 2*x0*d + d*d 
    = y + 2*(x-d)*d + d*d 
    ~= y + 2*x*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; 
    } 
} 

Answer 2

多分この場合の最良の答えは：GNU MP Bignumのようないくつかの大きな数字のライブラリを使用します。それはmpf_sqrtと同様の機能を提供します。浮動小数点のデフォルト精度はmpf_set_default_precで設定できます。

ベスト、 - クリストフ

Answer 3

いくつかのアルゴリズムのためにここを見て：私の頭の上オフMethods of computing square roots

Answer 4

のようなものが私のソリューションです::

double root(int num) 
{ 
    double l=0,m=num,h=num,om=0; 

     while(m-om) 
     { 
      om=m; 
      m=(l+h)/2.0; 
      if(m*m < num) 
      { 
       l = m;    
      } 
      else if(m*m > num) 
      { 
       h=m; 
      } 
     } 
     return m; 
}