快速近似浮點除法

Question

在現代處理器上，浮點除法比浮點乘法（當通過相互吞吐量測量時）慢好幾個數量級。

我想知道是否有任何算法在那裏計算快速近似x/y，給定某些假設和容忍水平。例如，如果您假設0<x<y並且願意接受任何在真值10％以內的輸出，那麼算法是否比內置FDIV操作更快？

Answer 1

我希望這可以提供幫助，因爲這可能與您要找到的內容相近。

__inline__ double __attribute__((const)) divide(double y, double x) { 
            // calculates y/x 
    union { 
     double dbl; 
     unsigned long long ull; 
    } u; 
    u.dbl = x;      // x = x 
    u.ull = (0xbfcdd6a18f6a6f52ULL - u.ull) >> (unsigned char)1; 
            // pow(x, -0.5) 
    u.dbl *= u.dbl;     // pow(pow(x,-0.5), 2) = pow(x, -1) = 1.0/x 
    return u.dbl * y;    // (1.0/x) * y = y/x 
} 

參見：
Another post about reciprocal approximation.
The Wikipedia page.

Answer 2

FDIV通常爲分外比FMUL慢只是B/C不能用管道輸送象乘法和需要用於迭代多CLK週期匯聚HW尋求過程。

最簡單的方法是簡單地認識到除法只不過是除數y和除數x的倒數的乘積。不那麼直截了當的部分是記住浮動價值x = m * 2^e &其逆x^-1 = (1/m)*2^(-e) = (2/m)*2^(-e-1) = p * 2^q接近這個新的尾數p = 2/m = 3-x, for 1<=m<2。這給出了反函數的粗略分段線性逼近，但是通過使用迭代牛頓根找到方法來改善該近似，我們可以做得更好。

讓w = f(x) = 1/x，此功能f(x)的逆通過的w或x = f^(-1)(w) = 1/w條件求解x發現。爲了用根搜索方法改進輸出，我們必須首先創建一個函數，其零點反映了期望的輸出，即g(w) = 1/w - x, d/dw(g(w)) = -1/w^2。

w[n+1]= w[n] - g(w[n])/g'(w[n]) = w[n] + w[n]^2 * (1/w[n] - x) = w[n] * (2 - x*w[n])

w[n+1] = w[n] * (2 - x*w[n]), when w[n]=1/x, w[n+1]=1/x*(2-x*1/x)=1/x

這些成分再加入以獲得代碼的最後一塊：

float inv_fast(float x) { 
    union { float f; int i; } v; 
    float w, sx; 
    int m; 

    sx = (x < 0) ? -1:1; 
    x = sx * x; 

    v.i = (int)(0x7EF127EA - *(uint32_t *)&x); 
    w = x * v.f; 

    // Efficient Iterative Approximation Improvement in horner polynomial form. 
    v.f = v.f * (2 - w);  // Single iteration, Err = -3.36e-3 * 2^(-flr(log2(x))) 
    // v.f = v.f * (4 + w * (-6 + w * (4 - w))); // Second iteration, Err = -1.13e-5 * 2^(-flr(log2(x))) 
    // v.f = v.f * (8 + w * (-28 + w * (56 + w * (-70 + w *(56 + w * (-28 + w * (8 - w))))))); // Third Iteration, Err = +-6.8e-8 * 2^(-flr(log2(x))) 

    return v.f * sx; 
}