在现代处理器上,浮点除法比浮点乘法(当通过相互吞吐量测量时)慢好几个数量级。快速近似浮点除法
我想知道是否有任何算法在那里计算快速近似x/y
,给定某些假设和容忍水平。例如,如果您假设0<x<y
并且愿意接受任何在真值10%以内的输出,那么算法是否比内置FDIV操作更快?
在现代处理器上,浮点除法比浮点乘法(当通过相互吞吐量测量时)慢好几个数量级。快速近似浮点除法
我想知道是否有任何算法在那里计算快速近似x/y
,给定某些假设和容忍水平。例如,如果您假设0<x<y
并且愿意接受任何在真值10%以内的输出,那么算法是否比内置FDIV操作更快?
我希望这可以提供帮助,因为这可能与您要找到的内容相近。
__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.
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;
}
你有没有考虑改变你的算法结构,避免分裂,而不是试图找到一个更快的分工技术? – AlchemicalApples
每次划分10%的错误会导致重用时出现指数错误,这是否值得?可能不是 – WorldSEnder
这纯粹是因为没有计划的应用程序,对知识的好奇心。 – dshin