Алгоритм Кэхэна

В вычислительной математике алгоритм Кэхэна (также известный как компенсационное суммирование) — это алгоритм вычисления суммы последовательности чисел c плавающей запятой, который значительно уменьшает вычислительную погрешность по сравнению с наивным подходом. Уменьшение погрешности достигается введением дополнительной переменной для хранения нарастающей суммы погрешностей. В частности, простое суммирование чисел в худшем случае имеет погрешность, которая растёт пропорционально и при суммировании случайных чисел имеет среднее квадратичное отклонение, пропорциональное (ошибки округления вызывают случайное блуждание). При компенсационном суммировании погрешность даже в худшем случае не зависит от , так что большое число слагаемых могут быть просуммированы с погрешностью, зависящей только от точности числа с плавающей запятой. Авторство алгоритма приписывают Уильяму Кэхэну.