Численная точность в суммирующей функции [дубликат]

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

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

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

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

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

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

См. также: алгоритм суммирования Kahan Он не требует хранения O (n), а только O (1).

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