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

Ответ 1

Похоже, вы хотите использовать Kahan Summation.

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

var result = array.Sum();

Ответ 5

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

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();

(этот код предполагает, что числа положительны, обычно очередь должна быть упорядочена по абсолютной величине)

Объяснение: задайте список чисел, чтобы как можно точнее их добавить, вы должны стремиться закрыть числа, t.i. устранить разницу между малыми и большими. Вот почему вы хотите добавить два наименьших числа, увеличивая при этом минимальное значение списка, уменьшая разницу между минимумом и максимумом в списке и уменьшая размер проблемы на 1.

К сожалению, я понятия не имею, как это можно векторизовать, учитывая, что вы используете OpenCL. Но я почти уверен, что это возможно. Вы можете взглянуть на книгу по векторным алгоритмам, удивительно, насколько они эффективны: векторные модели для параллельных вычислений