Как избежать ошибок округления в Python: метод Кахана

Почему сумма 0.1 + 0.2 не равна 0.3?

Вы когда-нибудь замечали, что в Python 0.1 + 0.2 даёт 0.30000000000000004? Это не баг, а особенность представления чисел с плавающей точкой. В этой статье мы разберём, почему так происходит, и как избежать накопления ошибок при суммировании больших массивов чисел.

Проблема: числа с плавающей точкой в Python

Python использует стандарт IEEE 754 для хранения чисел с плавающей точкой двойной точности. Это означает, что большинство десятичных дробей (например, 0.1) не могут быть представлены точно в двоичном виде. При сложении множества таких чисел ошибка накапливается, и результат может значительно отличаться от ожидаемого.

Рассмотрим простой пример:

numbers = [0.1] * 1000
sum(numbers)  # 99.9999999999986

Сумма тысячи десятых должна быть равна 100, но мы получаем 99.9999999999986. Это происходит потому, что каждая операция сложения вносит небольшую ошибку, которая со временем накапливается.

Метод Кахана: компенсация ошибок округления

В 1965 году Уильям Кан опубликовал алгоритм, который отслеживает и компенсирует потерянные при округлении биты. Основная идея — использовать дополнительную переменную c для хранения ошибки, возникшей на предыдущем шаге.

Как это работает

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

def kahan_sum(numbers):
    sum_ = 0.0
    c = 0.0  # компенсация
    for x in numbers:
        y = x - c      # добавляем компенсацию из предыдущего шага
        t = sum_ + y   # пробная сумма
        c = (t - sum_) - y  # новая ошибка
        sum_ = t
    return sum_

Разберём по строкам:

• y = x - c — добавляем компенсацию из предыдущего шага.
• t = sum_ + y — выполняем сложение.
• c = (t - sum_) - y — вычисляем, что потерялось при округлении.
• sum_ = t — обновляем сумму.

Ключевая строка — c = (t - sum_) - y. Она восстанавливает биты, которые были отброшены при сложении sum_ + y.

Сравнение: наивный метод против Кахана

Проверим оба метода на наборе данных из 10 миллионов чисел, каждое равно 0.0001:

import time

# 10 миллионов чисел 0.0001
nums = [0.0001] * 10_000_000

# Наивное суммирование
start = time.time()
naive_sum = sum(nums)
print(f"Наивный: {naive_sum}, время: {time.time() - start:.2f} с")

# Суммирование методом Кахана
start = time.time()
kahan_sum_result = kahan_sum(nums)
print(f"Кахана: {kahan_sum_result}, время: {time.time() - start:.2f} с")

Результаты:

• Наивный: 999.9998999965879 (ошибка ~1e-4)
• Кахана: 1000.0000000000001 (ошибка ~1e-13)

Метод Кахана даёт практически точный результат, хотя и работает медленнее (примерно в 3-4 раза). Для финансовых систем, где важна каждая копейка, это оправдано.

Другие подходы: попарное суммирование и decimal

Попарное суммирование

Альтернативный метод — попарное суммирование: массив рекурсивно делится пополам, каждая половина суммируется отдельно, затем результаты складываются. Это уменьшает ошибку, так как числа сравнимы по величине.

def pairwise_sum(arr):
    if len(arr) == 0:
        return 0.0
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    return pairwise_sum(arr[:mid]) + pairwise_sum(arr[mid:])

Для больших массивов рекурсия может переполнить стек, поэтому лучше использовать итеративную версию:

def pairwise_sum_iterative(arr):
    if not arr:
        return 0.0
    queue = arr[:]
    while len(queue) > 1:
        next_queue = []
        for i in range(0, len(queue), 2):
            next_queue.append(queue[i] + (queue[i+1] if i+1 < len(queue) else 0))
        queue = next_queue
    return queue[0]

Модуль decimal

Если нужна абсолютная точность (например, для денежных расчётов), используйте модуль decimal из стандартной библиотеки Python. Он хранит числа как строки и выполняет арифметику с произвольной точностью.

from decimal import Decimal, getcontext

getcontext().prec = 50  # задаём точность

def decimal_sum(numbers):
    return sum(Decimal(str(n)) for n in numbers)

Важно передавать числа в Decimal через строку, иначе Decimal(0.1) унаследует ошибку представления.

Сравнительная таблица методов

Вывод: Если нужна высокая точность без больших затрат производительности — выбирайте метод Кахана. Если требуется абсолютная точность — decimal.

Когда не стоит использовать метод Кахана

• Если вы работаете только с целыми числами, ошибок округления нет.
• Если вы уже используете decimal или fractions.
• Если массив небольшой (менее 1000 элементов), ошибка незначительна.
• В графике реального времени, где важна скорость, а не точность.

Практический вывод

Теперь вы знаете, как бороться с накоплением ошибок при суммировании чисел с плавающей точкой в Python. Попробуйте применить метод Кахана в своих проектах — например, при обработке финансовых данных или научных расчётах. Начните с простого: замените sum() на kahan_sum() и посмотрите на разницу в результатах.

Пишите в комментариях, с какими проблемами точности вы сталкивались и как их решали!