C++

Вычисление суммы элементов массива с сохранением точности

На сайте вакансий Яндекса предлагают вычислить сумму элементов массива и предлагают три варианта решения задачи. Их можно посмотреть тут. Эти примеры намеренно не оптимальны и существует лучшее решение задачи. Рассмотрим сначала предлагаемый вариант решения:


double sum1(std::vector<double>& v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}


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

Для оценки этой ошибки напишем простую тестовую программу:

const double x = 0.01;   // суммируем эту величину 10000 раз
double sum = 1000000000.0;  // начальное значение суммы
for (int i = 0; i < 10000; ++i ) {
    sum = sum + x;
}
const double error = 1000000100.0 - sum;
std::cout << error << std::endl;

Результат: 9.53674e-05 


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

Есть вариант решения данной задачи не за линейно-логарифмическое время O(n*logn), а за линейное O(n). Данный алгоритм предложил автора стандарта IEEE 754, Уильям Мортон Кэхэн (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Вот пример его реализации:


const double x = 0.01;
double e = 0; // будем держать ошибку тут. Начальная ошибка 0
double sum = 1000000000.; // начальное значение суммы
for (int i = 0; i < 10000; ++i ) {
    const double y = x - e;     // компенсируем ошибку
    const double t = sum + y;
    e = (t - sum) - y;          // сохраним новую ошибку
    sum = t;
}
const double error = 1000000100. - sum;
std::cout << error << std::endl;

Результат: 0


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

Похожие записи




Комментарии (0)

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.

Warning: Unknown: write failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5) in Unknown on line 0