Какой хороший способ добавить большое количество маленьких поплавков вместе?

Question

Скажем, у вас есть 100000000 32-битных значений с плавающей запятой в массиве, и каждое из этих значений с плавающей запятой имеет значение от 0,0 до 1,0.Если бы вы попытались суммировать их все следующим образом

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

, вы столкнулись бы с проблемами, так как result становится намного больше, чем 1,0.

Так каковы некоторые из способов болееточно выполнить суммирование?

Answer 1

Звучит так, как вы хотите использовать Суммирование Кахана .

Согласно Википедии,

Алгоритм суммирования Кахана (также известный как компенсированное суммирование ) значительно уменьшает числовую ошибку в сумме, полученную путем добавления последовательности чисел с плавающей запятой конечной точности, по сравнению с очевидной подход. Это делается путем сохранения отдельной рабочей компенсации (переменная для накопления мелких ошибок).

В псевдокоде алгоритм выглядит так:

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

Answer 2

Если вы можете терпеть немного больше места (в 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];

Стандартный алгоритм «разделяй и властвуй», в основном. Это работает, только если числа разбросаны случайным образом; это не будет работать, если первые полмиллиарда чисел 1e-12, а вторая половина миллиарда намного больше

Но прежде чем делать что-либо из этого, можно просто накопить результат в два раза. Это очень поможет.

Answer 3

Сделать результат двойным, предполагая C или C ++.

Answer 4

Абсолютно оптимальный способ - использовать приоритетную очередь следующим образом:

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. Но я почти уверен, что это может быть. Вы можете взглянуть на книгу о векторных алгоритмах, удивительно, насколько мощными они на самом деле являются: Векторные модели для параллельных вычислений

Answer 5

Если в .NET используется метод расширения LINQ .Sum (), существующий в IEnumerable. Тогда это будет просто:

var result = array.Sum();