Как лучше всего суммировать множество чисел с плавающей запятой?
-
23-08-2019 - |
Вопрос
Представьте, что у вас есть большой массив чисел с плавающей запятой всех размеров.Как наиболее правильно посчитать сумму с наименьшей ошибкой?Например, когда массив выглядит так:
[1.0, 1e-10, 1e-10, ... 1e-10.0]
и вы суммируете слева направо с помощью простого цикла, например
sum = 0
numbers.each do |val|
sum += val
end
всякий раз, когда вы суммируете меньшие числа, они могут упасть ниже порога точности, поэтому ошибка становится все больше и больше.Насколько я знаю, лучший способ — отсортировать массив и начать складывать числа от наименьшего к наибольшему, но мне интересно, есть ли еще лучший способ (более быстрый и точный)?
РЕДАКТИРОВАТЬ:Спасибо за ответ, теперь у меня есть рабочий код, который идеально суммирует двойные значения в Java.Это прямой порт из поста Python с победным ответом.Решение проходит все мои модульные тесты.(Более длинная, но оптимизированная версия доступна здесь. Суммаризатор.java)
/**
* Adds up numbers in an array with perfect precision, and in O(n).
*
* @see http://code.activestate.com/recipes/393090/
*/
public class Summarizer {
/**
* Perfectly sums up numbers, without rounding errors (if at all possible).
*
* @param values
* The values to sum up.
* @return The sum.
*/
public static double msum(double... values) {
List<Double> partials = new ArrayList<Double>();
for (double x : values) {
int i = 0;
for (double y : partials) {
if (Math.abs(x) < Math.abs(y)) {
double tmp = x;
x = y;
y = tmp;
}
double hi = x + y;
double lo = y - (hi - x);
if (lo != 0.0) {
partials.set(i, lo);
++i;
}
x = hi;
}
if (i < partials.size()) {
partials.set(i, x);
partials.subList(i + 1, partials.size()).clear();
} else {
partials.add(x);
}
}
return sum(partials);
}
/**
* Sums up the rest of the partial numbers which cannot be summed up without
* loss of precision.
*/
public static double sum(Collection<Double> values) {
double s = 0.0;
for (Double d : values) {
s += d;
}
return s;
}
}
Решение
Для "более точного": этот рецепт в кулинарной книге Python имеет алгоритмы суммирования, которые сохраняют полную точность (путем отслеживания промежуточных итогов).Код написан на Python, но даже если вы не знаете Python, он достаточно понятен, чтобы адаптироваться к любому другому языку.
Все подробности указаны в Эта бумага.
Другие советы
Смотрите также: Алгоритм суммирования Кахана Он не требует памяти O(n), а только O(1).
Существует множество алгоритмов, в зависимости от того, что вы хотите.Обычно они требуют отслеживания частичных сумм.Если вы сохраните только суммы x[k+1] - x[k], вы получите алгоритм Кахана.Если вы отслеживаете все частичные суммы (что дает алгоритм O(n^2)), вы получаете ответ @dF.
Обратите внимание, что в дополнение к вашей проблеме суммирование чисел разные знаки это очень проблематично.
Есть более простые рецепты, чем отслеживание всех частичных сумм:
- Отсортируйте числа перед суммированием, просуммируйте все положительные и отрицательные значения независимо.Если у вас есть отсортированные числа, отлично, в противном случае у вас есть алгоритм O (n log n).Суммируем по возрастанию.
- Суммируем по парам, затем по парам пар и т. д.
Личный опыт показывает, что обычно не нужны более сложные вещи, чем метод Кахана.
Что ж, если вы не хотите сортировать, вы можете просто сохранить сумму в переменной с более высокой точностью, чем отдельные значения (например,используйте двойной, чтобы сохранить сумму чисел с плавающей запятой, или «квадрат», чтобы сохранить сумму двойных чисел).Это приведет к снижению производительности, но оно может быть меньше, чем стоимость сортировки.
Если ваше приложение основано на числовой обработке, найдите арифметическую библиотеку произвольной точности, однако я не знаю, существуют ли библиотеки Python такого типа.Конечно, все зависит от того, сколько точных цифр вы хотите — вы можете добиться хороших результатов со стандартом IEEE с плавающей запятой, если будете использовать его осторожно.