Введение
Алгоритм в численном анализе
В численном анализе алгоритм суммирования Кахана, также известный как компенсированное суммирование, значительно снижает числовую ошибку в итоговой сумме, полученной при сложении последовательности чисел с плавающей точкой конечной точности, по сравнению с наивным подходом. Это достигается за счет ведения отдельной накопительной компенсации (переменной для аккумулирования малых ошибок), что фактически увеличивает точность суммы на точность переменной компенсации. В частности, простое последовательное суммирование чисел имеет максимальную ошибку, растущую пропорционально , и среднеквадратичную ошибку, растущую как для случайных входных данных (ошибки округления образуют случайное блуждание). При использовании компенсированного суммирования, с компенсационной переменной достаточной точности, максимальная ошибка практически не зависит от , поэтому большое количество значений можно суммировать с ошибкой, зависящей только от точности представления результата числами с плавающей точкой. Иво Бабушка, по-видимому, независимо разработал аналогичный алгоритм (отсюда суммирование Кахана — Бабушки). Схожие, более ранние методы включают, например, алгоритм построения линии Брезенхема, отслеживающий накопленную ошибку в целочисленных операциях (хотя впервые был описан примерно в то же время), и дельта-сигма модуляцию.
In numerical analysis, the Kahan summation algorithm, also known as compensated summation, significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors), in effect extending the precision of the sum by the precision of the compensation variable. In particular, simply summing numbers in sequence has a worst case error that grows proportional to , and a root mean square error that grows as for random inputs (the roundoff errors form a random walk). With compensated summation, using a compensation variable with sufficiently high precision the worst case error bound is effectively independent of , so a large number of values can be summed with an error that only depends on the floating point precision of the result. Ivo Babuška seems to have come up with a similar algorithm independently (hence Kahan–Babuška summation). Similar, earlier techniques are, for example, Bresenham's line algorithm, keeping track of the accumulated error in integer operations (although first documented around the same time) and the delta sigma modulation.
Альтернативы
Хотя алгоритм Кахана обеспечивает рост ошибки при суммировании n чисел, лишь незначительно больший рост можно достичь с помощью попарного суммирования: рекурсивно разделяют набор чисел на две половины, суммируют каждую половину, а затем складывают полученные две суммы. На практике, при ошибках округления случайного знака, среднеквадратичные ошибки попарного суммирования фактически растут как . Другой метод, использующий только целочисленную арифметику, но требующий большого аккумулятора, был описан Кирхнером и Кулишем; аппаратная реализация этого метода была описана Мюллером, Рубом и Рюллингом.
Поддержка библиотеками
В общем, встроенные функции "sum" в компьютерных языках обычно не гарантируют использование какого-либо конкретного алгоритма суммирования, тем более суммирования Кахана. Стандарт BLAS для подпрограмм линейной алгебры явно избегает предписания какого-либо конкретного порядка вычислений из соображений производительности, и реализации BLAS обычно не используют суммирование Кахана. Стандартная библиотека языка Python определяет функцию `fsum` для точного суммирования. Начиная с Python 3.12, встроенная функция `sum` использует суммирование Ноймайера. В языке Julia реализация функции `sum` по умолчанию использует попарное суммирование для достижения высокой точности при хорошей производительности, однако внешняя библиотека предоставляет реализацию варианта Ноймайера под названием `sum kbn` для случаев, когда требуется ещё более высокая точность. В языке C# пакет NuGet HPCsharp реализует вариант Ноймайера и попарное суммирование: как в скалярном виде, так и в параллельном, с использованием инструкций SIMD процессора и многоядерной обработки.