2

このコードをhttp://blog.shay.co/newtons-method/から取得しました。

//a - the number to square root
//times - the number of iterations
public double Sqrt(double a, int times)
{
    if (a < 0)
        throw new Exception("Can not sqrt a negative number");
    double x = 1;
    while (times-- > 0)
        x = x / 2 + a / (2 * x);
    return x;
}

ある場合、数値の反復回数の適切な経験則は何ですか? (たとえば、「n/2 反復を使用する」。)

4

2 に答える 2

5

What is a good rule of thumb for the number of iterations on a number, if one exists?

Newton's method has quadratic convergence, ie. at every step of the algorithm, the number of significant digits in the answer doubles. Thus the algorithm computes square roots upto D digits of precision in O(log D) time. Thus the number of iterations in your loop will depend upon the accuracy expected. So to have a fine grained control over the accuracy of the result, you can add a check in your code that returns the answer when the estimate is not outside the error bounds.

public double Sqrt(double a){
    if (a < 0)
        throw new Exception("Can not sqrt a negative number");
    double error = 0.00001;
    double x = 1;
    while (true){
        double val = x*x;
        if(abs(val-a) <= error)
             return x;
        x = x / 2 + a / (2 * x);
    }
}
于 2014-04-26T06:40:42.783 に答える
0

一定の反復回数で相対精度を保証する場合は、結果が 1/2 から 2 になるまで 4 で割って反復を準備しますa。または、1 より小さい値から開始する場合は乗算します。分割数を覚えておいてください。以来

sqrt(a)=2^k*sqrt(4^(-k)*a)

結果に同じ数の因数 2 を掛ける必要があります。次に、減数の平方根の相対誤差は次のaようになります。

3*(1/6)^(2^m)

反復後m、またはより速く、

(x[m]-sqrt(a))/(x[m]+sqrt(a)) = ( (1-sqrt(a))/(1+sqrt(a)) )^(2^m)

frexp浮動小数点指数へのアクセス関数を使用することで、必要な 4 と 2 のべき乗を最速で抽出して操作できますldexp。C 数学ライブラリでは、Java の Double クラスの同様のメソッドを使用します。

于 2014-04-27T08:02:06.923 に答える