Как лучше всего суммировать множество чисел с плавающей запятой?

Представьте, что у вас большой массив чисел с плавающей запятой, всех видов. Каков наиболее правильный способ вычисления суммы с наименьшей ошибкой? Например, когда массив выглядит так:

[1.0, 1e-10, 1e-10, ... 1e-10.0]

и вы складываете слева направо с помощью простого цикла, например

sum = 0
numbers.each do |val|
    sum += val
end

всякий раз, когда вы добавляете меньшие числа, может опускаться ниже порога точности, поэтому ошибка становится все больше и больше. Насколько я знаю, лучший способ - отсортировать массив и начать добавлять номера от самого низкого до самого высокого, но мне интересно, есть ли еще лучший способ (быстрее, точнее)?

EDIT. Спасибо за ответ. Теперь у меня есть рабочий код, который прекрасно суммирует двойные значения в Java. Это прямой порт с поста Python выигрышного ответа. Решение проходит все мои модульные тесты. (Более длинная, но оптимизированная версия доступна здесь Summarizer.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;
    }
}

Ответы

Ответ 1

Для "более точного": этот рецепт в Поваренной книге Python содержит алгоритмы суммирования, которые сохраняют полную точность (отслеживая промежуточные итоги), Код находится на Python, но даже если вы не знаете Python, он достаточно ясен, чтобы адаптироваться к любому другому языку.

Все подробности приведены в этой статье.

Ответ 3

Существует много алгоритмов, в зависимости от того, что вы хотите. Обычно они требуют отслеживания частичных сумм. Если вы сохраните только суммы x [k + 1] - x [k], вы получите алгоритм Кахана. Если вы отслеживаете все частичные суммы (следовательно, получаем алгоритм O (n ^ 2)), вы получите ответ @dF.

Обратите внимание, что в дополнение к вашей проблеме суммирование чисел разных знаков очень проблематично.

Теперь существуют более простые рецепты, чем отслеживание всех частичных сумм:

  • Сортируйте числа перед суммированием, суммируйте все отрицательные и положительные значения независимо. Если вы отсортировали числа, отлично, в противном случае вы получите алгоритм O (n log n). Суммируйте по величине.
  • Суммы по парам, затем пары пар и т.д.

Личный опыт показывает, что вам обычно не нужны более интересные вещи, чем метод Кахана.

Ответ 4

Ну, если вы не хотите сортировать, вы можете просто сохранить общее количество в переменной с более высокой точностью, чем отдельные значения (например, использовать double для сохранения суммы поплавков или "квад" ) чтобы сохранить сумму удвоений). Это налагает штраф за производительность, но это может быть меньше стоимости сортировки.

Ответ 5

Если ваше приложение полагается на поиск числовой обработки для произвольной арифметической библиотеки точности, однако я не знаю, существуют ли такие библиотеки Python. Конечно, все зависит от того, сколько цифр точности вы хотите - вы можете добиться хороших результатов со стандартной плавающей точкой IEEE, если будете использовать ее с осторожностью.

Ответ 6

используйте math.fsum для сохранения точности.

Прочитайте это также.