Что хороший путь состоит в том, чтобы добавить большое количество маленьких плаваний вместе?
Скажите, что у Вас есть 100 000 000 32-разрядных значений с плавающей точкой в массиве, и каждое из этих плаваний имеет значение между 0,0 и 1.0. Если Вы пытались суммировать их всех как это
result = 0.0;
for (i = 0; i < 100000000; i++) {
result += array[i];
}
Вы столкнулись с проблемами как result становится намного больше, чем 1,0.
Таким образом, что некоторые пути состоят в том, чтобы более точно выполнить суммирование?
5 ответов
Похоже, вы хотите использовать Суммирование Кахана .
Согласно Википедии,
Алгоритм суммирования Кахана (также известный как компенсированное суммирование ) значительно снижает числовую ошибку в общей сумме, полученной путем добавления последовательности с плавающей запятой конечной точности. количество точек по сравнению с очевидным подходом. Для этого используется отдельная компенсация хода (переменная для накопления небольших ошибок).
В псевдокоде алгоритм следующий:
function kahanSum (input) var sum = input [1] var c = 0.0 // Текущая компенсация потерянных младших битов . для i = 2 для input.length y = input [i] - c // Пока все хорошо: c равно нулю. t = sum + y / / Увы, сумма большая, y мала, поэтому младшие разряды y теряются. c = (t - sum) - y // (t - sum) восстанавливает старшую часть y; вычитание y восстанавливает - (младшая часть y) sum = t // Алгебраически c всегда должно быть равно нулю. Остерегайтесь оптимизировать компиляторы! next i // В следующий раз потерянная младшая часть будет добавлена к y при новой попытке. return sum
Если в .NET использовать метод расширения LINQ .Sum(), который существует для IEnumerable. Тогда это будет просто:
var result = array.Sum();
Если вы можете терпеть немного лишнего места (в 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, а вторая половина миллиарда намного больше.
Но прежде чем делать что-либо из этого, можно просто накопить результат в виде двойного. Это очень поможет.
Абсолютно оптимальный способ - использовать очередь с приоритетом в следующим образом:
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. Но я почти уверен, что это возможно. Вы можете взглянуть на книгу по векторным алгоритмам, удивительно, насколько они мощны на самом деле: Векторные модели для параллельных вычислений с данными