Сумма малых двойных чисел С++

Предположим, что у нас есть массив небольших (около 10^(-15)) двойных чисел в С++. Если мы вычислим сумму чисел в этом массиве последовательно, например

double sum = 0;
for (int i = 0; i < n; i++) sum+=array[i];

получаем значение x.

Но если мы разделим массив на некоторые части, а затем вычислим сумму в каждой части и после этого добавим все частичные суммы вместе, получим некоторое значение x2, которое близко к x, но не точно x. Поэтому я потерял начисление при расчете суммы.

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

Ответ 1

Использование Kahan Summation:

#include <numeric>
#include <iostream>
#include <vector>

struct KahanAccumulation
{
    double sum;
    double correction;
};

KahanAccumulation KahanSum(KahanAccumulation accumulation, double value)
{
    KahanAccumulation result;
    double y = value - accumulation.correction;
    double t = accumulation.sum + y;
    result.correction = (t - accumulation.sum) - y;
    result.sum = t;
    return result;
}

int main()
{
    std::vector<double> numbers = {0.01, 0.001, 0.0001, 0.000001, 0.00000000001};
    KahanAccumulation init = {0};
    KahanAccumulation result =
        std::accumulate(numbers.begin(), numbers.end(), init, KahanSum);

    std::cout << "Kahan Sum: " << result.sum << std::endl;
    return 0;
}

Вывод:

Kahan Sum: 0.011101

Код здесь.

Ответ 2

Абсолютный размер чисел не является проблемой.

Если вы хотите более точное суммирование, считаете ли вы компенсационную сумму? http://en.wikipedia.org/wiki/Kahan_summation_algorithm

Однако, если вы действительно имеете в виду, не теряя любую точность, ваш результат не обязательно будет вписываться в двойной. Если это действительно то, что вы хотите, вы можете посмотреть алгоритм 908 на http://dl.acm.org/citation.cfm?id=1824815 или аналогичный.

Ответ 3

Фокус в этих случаях заключается в том, чтобы сначала упорядочить массив от меньшего до более высокого, а затем суммировать тогда в цикле, который вы сделали. Таким образом, точность лучше.

Вы также можете проверить алгоритм суммирования Kahan

Ответ 4

Предположим применить алгоритм суммирования Kahan как для всего вашего набора, так и для каждого из ваших подмножеств.

Существуют другие questions, ссылающиеся на этот алгоритм, которые могут помочь вам

Ответ 5

Двойные числа на компьютере хранятся в двоичной числовой системе. Поэтому, когда вы видите двойное значение (в десятичной нотации), вы фактически видите двойное значение с некоторым округлением (например, 0,1 - бесконечная доля). Вы можете сделать тот же эксперимент, где двойные значения равны степени 2 (например, 2 ^ (- 30)), а затем вы увидите, что значения будут соответствовать.

Причина, по которой вы наблюдаете разницу при суммировании двойных значений в различной последовательности, заключается в том, что после каждого вычисления результат будет округлен в двоичной числовой системе и поэтому будет немного отличаться от фактического значения.

Ответ 6

Двоичные числа с плавающей запятой, используемые для представления десятичных чисел, имеют большую точность, чем точность. Вы нашли один способ преодоления разницы.

Ответ 7

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

Это может быть не причина, но, возможно, стоит исследовать ее дальше. Посмотрите на выбранный ответ на этот вопрос

Ответ 8

Потеря точности в результате добавления чисел не отличается при работе с очень маленькими числами от обработки чисел нормального размера. Что может быть актуальным: а) ОТНОСИТЕЛЬНО различия в размерах между большими числами? b) имеют ли разные знаки SIGNS?

Последний вопрос обычно поставлен на карту с добавочной точностью. Что вы должны сделать - может быть, не совсем оптимально, но справедливый снимок и легко реализовать - это:

a) разбивают их на подмножества положительных и отрицательных значений соответственно

b) сортировать каждое подмножество

Тогда

c) возьмите наибольший (в абсолютном размере) из двух скомбинированных объединений и инициализируйте свою сумму этим числом и удалите его из своего списка

d) итеративно: всякий раз, когда текущая сумма положительна, возьмите наибольший оставшийся отрицательный элемент и добавьте его к сумме и удалите ее из своего списка; всякий раз, когда текущая сумма отрицательна, делайте то же самое.

Таким образом, у вас есть справедливая вероятность, что вы (почти) минимизировали потерю точности того, что неотъемлемо неизбежно (с учетом представления чисел).