与顺序无关的浮点求和

Question

我知道浮点加法不是关联的：(a + b) + c 通常不等于 a + (b + c)。所以这个求和的算法可以根据输入的顺序给出不同的结果：

float naive_sum(float[] input) {
  float accumulator = 0;
  for (float x : input) {
    accumulator += x;
  }
  return accumulator;
}

是否可以使此顺序无关，以便 returns 即使输入被打乱也能得到相同的结果？我不是要减少舍入误差：我只是希望它与顺序无关。

一个想法是先对输入进行排序：

float sort_sum(float[] input) {
  return naive_sum(sort(input));
}

sort 不必按数字顺序排列浮点数；它只需要满足 sort(input) == sort(shuffle(input))。我认为这可行，但它不再像 naive_sum 那样恒定 space 和线性时间。

另一个想法是使累加器成为一个巨大的整数类型：大到足以容纳任何浮点数而无需四舍五入。如果浮点数有 11 位指数，则需要大约 2^11 位，即大约 2000 位。

float fixedpoint_sum(float[] input) {
  int2048 accumulator = 0;
  for (float x : input) {
    accumulator += float_to_fixed(x);
  }
  return fixed_to_float(accumulator);
}

现在又是常量 space 和线性时间了，但是有这么大的累加器，也许它是一个非常慢的线性时间。 :)

有没有实用的浮点数求和顺序无关的算法？

Answer 1

“(a+b)+c 不等于 a+(b+c)”的问题是因为计算机不能无限精确地工作，它们在数学上并不精确；但他们使用某种丢失数字的表示形式。

阅读 What Every Computer Scientist Should Know About Floating-Point Arithmetic 了解详细说明。

这种表示具有粒度，这意味着两个连续表示之间的差异不是恒定的。大数不能与小数相加：1.1E20 + 1E-5 = 1.1E20

一些小改进：

为了减少这个大大小小的问题，您可以对数字进行排序。所以小值的总和可能达到大的足够大值和加法可能更准确。还是没有保证好结果。
另一种技术可能是以不同的顺序多次求和 (1,2,3... 或 3,2,1... 或 1,20,2,19,3,18... 或...) 然后计算所有总和的平均值。

最常用的（我相信）技术是扩大使用的位数。例如 64 位或 128 位而不是 32 位。或任意精度算术。价格是128位或更高的精度使计算速度变慢。

存在 "Robust Predicates" 和 this EGC site，它们试图将误差降至最低，低于 float/double epsilon。

Answer 2

如果您的语言具有高精度小数类型，例如 Java 的 java.math.BigDecimal，请使用它来进行求和。从 float 或 double 到 BigDecimal 的转换是准确的。如果不指定需要舍入的 MathContext BigDecimal 加法也是精确的。最终的 BigDecimal 值将是输入的实数和，实数加法是结合和交换的。唯一的舍入和舍入错误是在转换回 float 时，无论输入顺序如何，都会转换相同的数字。

这类似于您的累加器想法，但利用了已经测试过的数据类型和内存管理来限制 "accumulator" 的大小。

private static float sum(float[] data) {
    BigDecimal adder = new BigDecimal(0);
    for(float f : data) {
        adder = adder.add(new BigDecimal(f));
    }
    return adder.floatValue();
}

与顺序无关的浮点求和

Order-independent floating point summation

algorithm

floating-point

non-deterministic