キューブルートのニュートン反復を効率的にシードする

Question

数値の立方根を効率的に見つけるにはどうすればよいですか？ 私はNewton-Raphsonメソッドを使うことができると思いますが、反復回数を最小限に抑えるためにプログラムで初期解を推測する方法はわかりません。

Answer 1

これは誤って複雑な質問です。 Hereは、いくつかの可能なアプローチの良い調査です。

Answer 2

Accepted Answerを克服した「リンク腐敗」の観点から、私は、超自然的な繰り返しに適した初期推測を素早く得るトピックに焦点を絞って、より自己完結型の答えを提供します。

メタマーリスト（Wayback link）による「調査」は、さまざまな開始値/反復の組み合わせ（ニュートンとハレーの両方の方法が含まれています）についていくつかのタイミング比較を提供しました。その参照先は、W. Kahan、「実キューブルートの計算」、K. Turkowski「キューブルートの計算」によって行われます。

metamaristは、「32ビット整数を前提とし、倍精度のためのIEEE 754形式に基づいて、5ビットの精度で初期推定値を生成する」というこのスニペットを使用して、W. KahanのDEC- VAX時代ビット - ：

inline double cbrt_5d(double d) 
{ 
    const unsigned int B1 = 715094163; 
    double t = 0.0; 
    unsigned int* pt = (unsigned int*) &t; 
    unsigned int* px = (unsigned int*) &d; 
    pt[1]=px[1]/3+B1; 
    return t; 
} 

K. Turkowskiによってコードもう少し精密間隔にわたるその立方根に二次近似に続く従来の力 - の二float frにスケーリングすることによって（「およそ6ビット」）、[0.125を提供、1.0）：

/* Compute seed with a quadratic qpproximation */ 
fr = (-0.46946116F * fr + 1.072302F) * fr + 0.3812513F;/* 0.5<=fr<1 */ 

とそれに続く2の指数の復元（3分の1に調整）。指数部/仮数部の抽出と復元は、math library calls~frexpとldexpを使用します。私たちは、他の可能な形態とそれらを比較する必要があり、それらの立方根の近似値を理解するために、他の立方根「シード」の近似

と

比較。最初に、判断のための基準：間隔[1/8,1]での近似を考察し、最良の（最大値を最小にする）相対誤差を使用する。

 error_rel = max | f(x)/x^(1/3) - 1 | on [1/8,1] 

最も簡単な近似はもちろんの間隔上の単一の定数、そして最高の相対誤差を使用することです：f(x)はx^{1/3}に提案した近似であるならば、我々はその相対誤差を発見された

その場合は、端点での値の幾何平均であるf_0(x) = sqrt(2)/2を選択します。これは1.27ビットの相対精度を与え、ニュートン反復のための素早く汚い出発点です。これは、相対精度の4.12ビット、大きな改善が、それぞれの方法によって約束相対精度の5-6ビットのショートを与える

f_1(x) = 0.6042181313*x + 0.4531635984 

：

よりよい近似は最もよく一次多項式であろうKahanとTurkowskiのしかし、それは野球場にあり、1回の乗算（および1回の加算）だけを使用します。

最後に、乗算の代わりに除算を許可すればどうなりますか？

f_M(x) = 1.4774329094 - 0.8414323527/(x+0.7387320679) 

相対精度の7.265ビットを与える：それは1つの部門と2「追加」で、我々は最高の線形分数の機能を持たせることができることが判明しました。

これは魅力的なアプローチのように見えますが、従来の経験則は、3つのFP乗算のようなFP除算のコストを扱うことでした（そして、加算と減算をほとんど無視する）。しかし、現在のFPU設計では、これは現実的ではありません。加算/減算に対する乗算の​​相対コストは、ほとんどの場合、2倍または同等にまで下がっていますが、除算コストは​​低下しませんが、乗算コストの7〜10倍になることがよくあります。したがって、私たちは私たちの部門業務とは悲惨なものでなければなりません。

Answer 3

static double cubeRoot(double num) { 
    double x = num; 

    if(num >= 0) { 
     for(int i = 0; i < 10 ; i++) { 
      x = ((2 * x * x * x) + num)/(3 * x * x); 
     } 
    } 
    return x; 
} 

Answer 4

それはすでに解決されている最適化問題のように思えるが、私は迅速立方根のアルゴリズムを探して、このページにつまずく他の人のために、ここに掲載cubeRoot（）関数に改善を追加したいです。

既存のアルゴリズムは正常に機能しますが、0〜100の範囲外では不正確な結果が得られます。

ここには、 -/+ 1兆（1E15）の数字で動作する改訂版があります。より大きい数値で作業する必要がある場合は、反復回数を増やしてください。

static double cubeRoot(double num){ 
    boolean neg = (num < 0); 
    double x = Math.abs(num); 
    for(int i = 0, iterations = 60; i < iterations; i++){ 
     x = ((2 * x * x * x) + num)/(3 * x * x); 
    } 
    if(neg){ return 0 - x; } 
    return x; 
} 

最適化に関しては、私は、元のポスターは、任意の入力サイズ与えられ、正確な結果のための反復の最小数を予測する方法を求めていた推測しています。しかし、ほとんどの一般的なケースのように、最適化による利益は複雑さを増す価値はありません。上記の機能を使用しても、平均コンシューマハードウェアでは100回の反復が0.2ミリ秒未満です。スピードが最も重要であれば、事前計算ルックアップテーブルの使用を検討したいと思います。しかし、これは組込みシステムエンジニアではなく、デスクトップ開発者からのものです。