随机排序的 IEEE 754 双精度浮点数的总和结果

Question

这是我的问题的伪代码。

我有一个 IEEE 754 双精度正数数组。

数组可以随机排列，但数字总是相同的，只是在它们的位置上打乱了。此外，在 double 表示的有效 IEEE 范围内，这些数字 可以在很大范围内变化 。

获得列表后，我初始化一个变量：

double sum_result = 0.0;

然后我在整个数组的循环中累加 sum_result 上的总和。我做的每一步：

sum_result += my_double_array[i]

是否保证无论double的初始数组顺序如何，如果数字相同，打印出的总和结果总是相同的？

Answer 1

没有

举个简单的例子，0x1p53 加 1 得到 0x1p53。（这里使用十六进制浮点数表示法，“p”之前的部分是尾数，用十六进制表示，与C十六进制整数常量相同，只是它可以有一个“.”来标记小数的开始部分。“p”后面的数字表示尾数乘以的 2 的幂。）这是因为数学上精确的和 0x1.00000000000008p+53 不能用 IEEE-754 64 位二进制浮点数表示, 所以它被四舍五入到最接近的值，它的有效位甚至是低位，即 0x1p53.

因此，0x1p53+1 产生 0x1p53。所以 0x1p53+1+1，从左到右计算，也产生 0x1p53。但是，1+1 是 2，而 2+0x1p53 可以精确表示为 0x1.0000000000001p+53，所以 1+1+0x1p53 是 0x1.0000000000001p+53.

为了以十进制显示更容易理解的示例，假设我们只有两位小数。然后 100+1 产生 100，所以 100+1+1+1+1+1+1 产生 100。但是 1+1+1+1+1+1+100 累积到 6+100 然后产生 110（由于四舍五入到两位有效数字）。

Answer 2

Is it guaranteed that, whatever the order of the initial array of double, if the numbers are the same, the printed out sum result will be always the same?

不，FP加法不是associative. Remember it is called floating point - the absolute precision "floats" about relative to 1.0. Any given operation like addition (+) is subject to round-off error。

然而，如果求和完成并且 不精确 标志明确，那么是的，顺序不相关。**

简单的反例。

#include <math.h>
#include <float.h>
#include <fenv.h>
#include <stdio.h>

int main(void) {
  double a[3] = { DBL_MAX, -DBL_MAX, 1.0 };
  fexcept_t flag;

  feclearexcept(FE_ALL_EXCEPT);
  printf("%e\n", (a[0] + a[1]) + a[2]);
  fegetexceptflag(&flag, FE_INEXACT);
  printf("Inexact %d\n", !!(flag & FE_INEXACT));

  feclearexcept(FE_ALL_EXCEPT);
  printf("%e\n", a[0] + (a[1] + a[2]));
  fegetexceptflag(&flag, FE_INEXACT);
  printf("Inexact %d\n", !!(flag & FE_INEXACT));

  printf("%d\n", FLT_EVAL_METHOD);
  return (EXIT_SUCCESS);
}

输出

1.000000e+00  // Sum is exact
Inexact 0

0.000000e+00  // Sum is inexact
Inexact 1

0    // evaluate all operations ... just to the range and precision of the type;

根据FLT_EVAL_METHOD，FP 数学可能会使用更宽的岁差和范围，但上述极端示例总和仍然会有所不同。

** 除了可能是 0.0 与 -0.0

的结果

要了解原因，请尝试使用 4 位精度的基于 10 个文本的示例。相同的原则适用于 double，其通常具有 53 位二进制精度。

a[3] = +1.000e99, -1.000e99, 1.000
sum = a[0] + a[1]   // sum now exactly 0.0 
sum += a[2]         // sum now exactly 1.0 
// vs.
sum = a[1] + a[2]   // sum now inexactly -1.000e99
sum += a[0]         // sum now inexactly 0.0

回复："printed out sum result will be always the same"：除非代码以足够高的精度打印 "%a" 或 "%.*e"，否则打印的文本可能缺乏意义并且两个 不同的总和 可能 看起来一样 。参见 Printf width specifier to maintain precision of floating-point value

Answer 3

举个例子：为了简单起见，我使用10进制的模型转置浮点数问题，为了简单起见，运算结果四舍五入。

假设我们必须对 3 个数字求和 9.9 + 8.4 + 1.4
确切的结果是 19.7 但我们只有两位数字所以它应该四舍五入到 20.

如果我们首先对 9.9 + 8.4 求和，我们得到 18.3，然后四舍五入为 18.
然后我们对 18. + 1.4 求和，得到 19.4 四舍五入为 19..

如果我们首先对最后两项求和 8.4 + 1.4，我们得到 9.8，还不需要四舍五入。
然后 9.9 + 9.8 我们得到 19.7 四舍五入到 20.，一个不同的结果。

(9.9 + 8.4) + 1.4 不同于 9.9 + (8.4 + 1.4)，求和运算不结合，这是由于中间舍入。我们也可以用其他舍入模式展示类似的例子...

问题与 53 位有效数的基数 2 完全相同：无论基数或有效数长度如何，中间舍入都会导致非关联性。

要消除这个问题，您可以对数字进行排序，使顺序始终相同，或者消除中间舍入，只保留最后一个，例如使用这样的超级累加器 https://arxiv.org/pdf/1505.05571.pdf
...或者只是接受一个近似的结果（由您分析平均或更差的错误并决定是否可以接受...）。

随机排序的 IEEE 754 双精度浮点数的总和结果

Result of the sum of random-ordered IEEE 754 double precision floats

floating-point

precision

ieee-754