有效地爲立方根提供牛頓迭代

如何以有效的方式找到數字的立方根？我認爲可以使用Newton-Raphson方法，但我不知道如何以編程方式猜測初始解決方案以最小化迭代次數。有效地爲立方根提供牛頓迭代

來源

2011-09-18 SnoopyMe

「數字」是什麼意思？ – starblue

這是一個看似複雜的問題。 Here是一些可能的方法很好的調查。

來源

2011-09-18 18:34:19

我聽起來很粗魯，但我認爲萬一鏈接死了，你應該在你的答案中加入* some *內容。（如果你想複製和粘貼） – Astrobleme

鑑於超越接受答案的「鏈接腐爛」，我將給出一個更爲獨立的答案，重點是快速獲得適合超線性迭代的初始猜測。

metamerist（Wayback link）的「調查」爲各種起始值/迭代組合（包括Newton和Halley方法）提供了一些時間比較。它的參考文獻是W. Kahan，「計算真實立方根」和K. Turkowski，「計算立方根」。

超媒體技術更新W. Kahan的DEC-VAX時代位擺動技術，該「片假定32位整數」並依靠IEEE 754格式進行雙打「以5位精度生成初始估計」：

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（調整爲三分之一）。指數/尾數提取和恢復利用math library calls至frexp和ldexp。

與其他立方根「種子」近似

比較爲了欣賞我們需要把它們與其他可能的形式比較這些立方根近似。首先是判斷標準：我們考慮區間[1/8,1]的近似值，並且我們使用最好的（最小化最大值）相對誤差。

也就是說，如果f(x)是提出近似x^{1/3}，我們發現它的相對誤差：

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

當然最簡單的近似值是使用在間隔一個常數，最好的相對誤差在這種情況下，通過選取f_0(x) = sqrt(2)/2（端點值的幾何平均值）來實現。這給出了1.27比特的相對準確度，這對牛頓迭代來說是一個快速但很髒的起點。

更好的近似將是最好的一次多項式：

f_1(x) = 0.6042181313*x + 0.4531635984

這給相對精度，一個很大的進步，但短期由各自的方法答應相對精度的5-6位的4.12位Kahan和Turkowski。但它是在球場上，只使用一個乘法（和一個加法）。

最後，如果我們允許自己一個部門，而不是一個乘法？事實證明，一個師，兩個「加法」，我們可以有最好的線性分式函數：

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

這給相對準確的7.265位。

一眼看起來這似乎是一個有吸引力的方法，但一個古老的經驗法則是處理FP部門的成本，如三個FP乘法（並且大多忽略加法和減法）。然而，對於目前的FPU設計來說，這是不現實的。雖然乘法與增加/減少的相對成本已經下降，在大多數情況下降低到2倍甚至相等，但分裂的成本並沒有下降，而是經常增加到乘法成本的7-10倍。因此，我們必須吝嗇我們的分工業務。

來源

2014-09-09 15:45:54 hardmath

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; 
}

來源

2014-10-11 21:25:47 user2974606

好像優化問題已經解決，但我想改善添加此處發佈的cubeRoot（）函數，對於其他人絆倒此頁上尋找一個快速的立方根算法。

現有的算法效果很好，但在0-100範圍之外它會給出不正確的結果。

這是一個修訂版本，適用於 -/+ 1 quadrillion（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毫秒。如果速度是最重要的，我會考慮使用預先計算的查找表。但這是來自桌面開發人員，而不是嵌入式系統工程師。

來源

2017-02-14 07:12:59 Beejor

有效地爲立方根提供牛頓迭代

回答

相關問題