При последовательном сложении чисел с плавающей точкой часть младших битов теряется из-за округления. На больших массивах эта ошибка постепенно накапливается.
Алгоритм Кэхэна хранит потерянную часть в отдельной переменной и компенсирует её на следующем шаге:
float kahanSum(const float *nums, int count)
{
float sum = 0.0f;
float correction = 0.0f;
for (int i = 0; i < count; ++i)
{
float adjusted = nums[i] - correction;
float next = sum + adjusted;
correction = (next - sum) - adjusted;
sum = next;
}
return sum;
}
Здесь
correction запоминает ошибку округления, которая потерялась при предыдущем сложении.Обычная сумма быстрее, но Kahan Summation полезен там, где важна численная точность:
- научные расчёты;
- статистика и аналитика;
- графика и симуляции;
- обработка больших массивов;
- накопление очень маленьких значений рядом с большими.
Метод предложил Уильям Кэхэн в 1965 году. Небольшое усложнение цикла может заметно уменьшить ошибку без перехода на более тяжёлый числовой тип.
