12

假设您在一个数组中有 100000000 个 32 位浮点值，每个浮点数的值都在 0.0 和 1.0 之间。如果你试着像这样总结它们

result = 0.0;
for (i = 0; i < 100000000; i++) {
    result += array[i];
}

你会遇到result比 1.0 大得多的问题。

那么有哪些方法可以更准确地进行求和呢？

4

5 回答 5

30

听起来你想使用Kahan Summation。

根据维基百科，

与显而易见的方法相比， Kahan 求和算法（也称为补偿求和）显着降低了通过添加一系列有限精度浮点数获得的总数中的数值误差。这是通过保持单独的运行补偿（累积小误差的变量）来完成的。

在伪代码中，算法是：

function kahanSum(input)
 var sum = input[1]
 var c = 0.0          //A running compensation for lost low-order bits.
 for i = 2 to input.length
  y = input[i] - c    //So far, so good: c is zero.
  t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
  c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
  sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
 next i               //Next time around, the lost low part will be added to y in a fresh attempt.
return sum
于 2010-03-16T16:58:09.253 回答
1

如果您可以容忍一点额外的空间（在 Java 中）：

float temp = new float[1000000];
float temp2 = new float[1000];
float sum = 0.0f;
for (i=0 ; i<1000000000 ; i++) temp[i/1000] += array[i];
for (i=0 ; i<1000000 ; i++) temp2[i/1000] += temp[i];
for (i=0 ; i<1000 ; i++) sum += temp2[i];

基本上是标准的分治算法。这仅在数字随机分散时才有效；如果前 5 亿个数字是 1e-12 而后 5 个亿更大，它就行不通了。

但在做任何这些之前，一个人可能只是将结果累积成双倍。这会有很大帮助。

于 2010-03-16T17:30:50.757 回答
1

假设 C 或 C++，使结果为双精度。

于 2010-03-16T16:52:21.463 回答
0

绝对最佳的方式是使用优先级队列，方式如下：

PriorityQueue<Float> q = new PriorityQueue<Float>();
for(float x : list) q.add(x);
while(q.size() > 1) q.add(q.pop() + q.pop());
return q.pop();

（此代码假定数字为正数；通常队列应按绝对值排序）

解释：给定一个数字列表，要尽可能精确地将它们相加，您应该努力使数字接近，以消除大小之间的差异。这就是为什么要将两个最小的数字相加，从而增加列表的最小值，减小列表中最小值和最大值之间的差，并将问题大小减少 1。

不幸的是，考虑到您使用的是 OpenCL，我不知道如何对其进行矢量化。但我几乎可以肯定它可以。您可能会看一下有关矢量算法的书，令人惊讶的是它们实际上是多么强大：用于数据并行计算的矢量模型

于 2010-03-17T08:28:55.647 回答
0

如果在 .NET 中使用 IEnumerable 上存在的 LINQ .Sum() 扩展方法。那么它就是：

var result = array.Sum();
于 2010-03-16T16:57:23.770 回答