Скажем, что у вас есть 100000000 32-битных значений с плавающей запятой в массиве, и каждое из этих чисел имеет значение от 0.0 до 1.0. Если вы попытались их суммировать, пожалуйста,
result = 0.0;
for (i = 0; i < 100000000; i++) {
result += array[i];
}
у вас возникнут проблемы, так как result будет намного больше 1.0.
Итак, каковы некоторые из способов более точного выполнения суммирования?
Похоже, вы хотите использовать 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
Сделайте результат двойным, предполагая C или С++.
Если вы можете терпеть небольшое дополнительное пространство (в 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. Это очень поможет.
Если в .NET используется метод расширения LINQ.Sum(), который существует в IEnumerable. Тогда это будет просто:
var result = array.Sum();
Абсолютно оптимальным способом является использование очереди приоритетов следующим образом:
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. Но я почти уверен, что это возможно. Вы можете взглянуть на книгу по векторным алгоритмам, удивительно, насколько они эффективны: векторные модели для параллельных вычислений