点积的最坏情况精度是多少? [英] What is the worst case accuracy for dot product?

问题描述

假定处理器仅具有符合IEEE-754的"fadd"和"fmul"操作(没有"dot"或"fma"指令).平凡实现点积运算将实现最差的精度.例如，对于长度为3的向量:

Suppose the processor has only 'fadd' and 'fmul' operations (no 'dot' or 'fma' instructions) which are IEEE-754 compliant. What is the worst case accuracy that will be achieved by the trivial implemention of the dot product operation. For example, for a vector of length 3:

dot(vec_a, vec_b) = vec_a.x*vec_b.x + vec_a.y*vec_b.y + vec_a.z*vec_b.z

这是我的分析，但不确定是否正确: 对于长度为N的向量，有N个乘法和N-1个加法，导致2N-1个浮点运算.在最坏的情况下，对于这些操作中的每一个，对于准确的结果，表示将太小，因此中间结果将被四舍五入.每次四舍五入总计0.5 ULP误差.那么最大误差将是(2N-1)* 0.5 = N-1/2 ULP?

Here is my analysis, but I am not sure if it correct: For a vector of length N, there are N multiplications and N-1 additions, resulting in 2N-1 floating point operations. In the worst case, for each of these operations the representation will be too small for the accurate result, so the intermediate result will be rounded. Each rounding adds up to 0.5 ULP error. So the maximum error will be (2N-1)*0.5 = N-1/2 ULP?

推荐答案

您的推理无法进行加法运算:如果a和b各自已经不精确0.5 ULP，并且a接近于-b ，则a + b的相对准确度可能糟糕，远低于1.5 ULP.实际上，如果没有关于您要计算的点积的向量的进一步信息，就无法保证可以提供结果的相对准确性.

Your reasoning does not work for additions: if a and b are already inaccurate by 0.5 ULP each and a is close to -b, then the relative accuracy of a + b can be terrible, much worse than 1.5 ULP. In fact, without further information about the vectors you are computing the dot-product of, there are no guarantees one can provide about the relative accuracy of the result.

只有乘法时，您的推理思路就可以了，但是它会忽略复合错误.

Your line of reasoning is okay-ish when there are only multiplications, but it ignores compounded errors.

考虑等式:(a + e _a )(b + e _b )= ab + ae _b + be _a + e _a e _b .

Consider the equation: (a + e_a)(b + e_b) = ab + ae_b + be_a + e_ae_b.

如果您假设a和b都在1和2之间，则将两个已经精确到0.5 ULP的结果相乘后的总相对误差只能粗略地近似为1 ULP，并且仍然忽略了误差项e _a e _b 和乘法本身的误差.对于浮点乘法的结果，使它的总相对误差约为1.5 ULP，这只是一个粗略的平均值，而不是声音的最大值.

If you assume that both a and b are between 1 and 2, the total relative error after multiplication of two results that were already accurate to 0.5 ULP each can only, in a rough first approximation, be estimated as 1 ULP, and that is still ignoring the error term e_ae_b and the error of the multiplication itself. Make it about 1.5 ULP total relative error for the result of the floating-point multiplication, and this is only a rough average, not a sound maximum.

这些我的同事已经形式化并证明了双精度浮点点积.其结果的英语翻译是，如果每个向量分量都以1.0为边界，则点积的最终结果将精确到NMAX * B，其中NMAX是向量的维数，而B是一个常数，取决于在NMAX上.链接页面上提供了一些值:

These colleagues of mine have formalized and demonstrated a notion of accuracy of the double-precision floating-point dot-product. A translation to English of their result is that if each vector component is bounded by 1.0, then the end result of the dot product is accurate to NMAX * B, where NMAX is the dimension of the vectors, and B is a constant depending on NMAX. A few values are provided on the linked page:

NMAX     10            100            1000
B        0x1.1p-50     0x1.02p-47     0x1.004p-44

结果中，您可以用足够低的 2的幂替代1.0以确保没有溢出，然后点积的绝对误差变为NMAX * B * P ² .循环不变量分别变为:

In their result, you can substitute 1.0 with any power of two P low enough to ensure the absence of overflow, and the absolute error of the dot product then becomes NMAX * B * P². The loop invariants become respectively:

@ loop invariant \abs(exact_scalar_product(x,y,i)) <= i * P * P;
@ loop invariant \abs(p - exact_scalar_product(x,y,i)) <= i * B * P * P;

这篇关于点积的最坏情况精度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！