Скажем, у вас есть 100000000 32-битных значений с плавающей запятой в массиве, и каждое из этих значений с плавающей запятой имеет значение от 0,0 до 1,0. Если вы попытаетесь суммировать их все так
result = 0.0;
for (i = 0; i < 100000000; i++) {
result += array[i];
}
вы столкнетесь с проблемами, так как result становится намного больше, чем 1.0.
Итак, каковы некоторые из способов более точного выполнения суммирования?
Похоже, вы хотите использовать суммирование Кахана.
Согласно Википедии,
Алгоритм суммирования Кэхана (также известный как компенсированное суммирование) значительно снижает числовую ошибку в сумме, полученной путем добавления последовательности чисел с плавающей запятой конечной точности, по сравнению с очевидным подходом. . Это делается путем сохранения отдельной рабочей компенсации (переменная для накопления небольших ошибок).
В псевдокоде алгоритм такой:
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
--ffast-math. (Этот флаг намеренно нарушает некоторые гарантии, предоставляемые IEEE-754, поэтому, насколько я знаю, он никогда не включается, если вы не попросите об этом явно). Насколько я знаю, ни один компилятор по умолчанию не выполняет оптимизацию, предполагающую арифметику с бесконечной точностью, именно потому, что такие операции будут нарушены.
- person Daniel Pryden; 16.05.2012
Сделайте результат двойным, предполагая C или 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];
Стандартный алгоритм «разделяй и властвуй», в общем. Это работает, только если числа разбросаны случайным образом; это не сработает, если первые полмиллиарда чисел равны 1e-12, а вторые полмиллиарда намного больше.
Но прежде чем делать что-либо из этого, можно просто накопить результат в двойнике. Это очень поможет.
Если в .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();
(этот код предполагает, что числа положительные; обычно очередь должна быть упорядочена по абсолютному значению)
Объяснение: дан список чисел, чтобы сложить их как можно точнее, нужно стремиться к тому, чтобы числа были близкими, т.е. устранить разницу между маленькими и большими. Вот почему вы хотите сложить два наименьших числа, тем самым увеличив минимальное значение списка, уменьшив разницу между минимумом и максимумом в списке и уменьшив размер задачи на 1.
К сожалению, я понятия не имею, как это можно векторизовать, учитывая, что вы используете OpenCL. Но я почти уверен, что это может быть. Вы можете взглянуть на книгу о векторных алгоритмах, удивительно, насколько они на самом деле эффективны: Векторные модели для параллельных вычислений
math.fsum(docs.python.org/library/math.html# math.fsum). - person kennytm schedule 16.03.2010