Точная сумма
Даны n чисел, записанных в десятичном виде. Каждое прочитайте как обычное число с плавающей запятой двойной точности (float в Python, float64 в Go) и выведите две суммы.
- Сумму, сложенную по порядку слева направо, где после каждого сложения результат округляется до
float64, — то, что делает обычный цикл. - Точную сумму тех же
float64-чисел, как если бы её считали без всяких округлений, округлённую до ближайшегоfloat64один раз, в самом конце.
Вход
В первой строке n (1 ≤ n ≤ 2·10⁵). Дальше n чисел, по одному в строке, например 0.1, -149.90 или 3.5e120; по модулю каждое не больше 10³⁰⁰.
Выход
Две строки: сумма по порядку и точная сумма, каждая — в формате %.17g (17 значащих цифр, как печатают f"{x:.17g}" в Python и fmt.Printf("%.17g") в Go).
Примеры
Пример 1
5 1e100 1 -1e100 0.1 0.2
0.30000000000000004 1.3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первая строка — обычный цикл. Для второй округлять нельзя ни разу до самого конца. Какой точности хватит, чтобы сумма любых float64-чисел считалась без потерь?
2Идея
Любое число float64 — двоичная дробь: не больше 53 значащих бит, а позиции этих бит лежат между 2¹⁰²³ и 2⁻¹⁰⁷⁴. Сумма двух сотен тысяч таких чисел помещается в двоичное число примерно из 2120 бит. Значит, сложение с запасом точности в 2200 бит не потеряет ни одного бита — в Go это big.Float с SetPrec(2200), а в конце Float64() округляет до ближайшего. В Python то же самое делает math.fsum: он хранит сумму как несколько float, которые вместе представляют её точно (алгоритм Шевчука), и округляет один раз.
3Разбор
Поправка Кэхэна, которая выглядит как готовое решение, здесь не годится. Она хранит одну поправку — то, что потерялось при прошлом сложении, — и хорошо исправляет медленный дрейф, когда к большой сумме много раз прибавляют маленькие числа. Но в первом примере между 10¹⁰⁰ и −10¹⁰⁰ стоит единица: при сложении с 10¹⁰⁰ она теряется вся, поправка становится −1, а при вычитании 10¹⁰⁰ поправку уже не к чему применить — она снова теряется на фоне огромного числа. Кэхэн выдаёт 0,3 вместо 1,3. Вариант Ноймайера, который в Python 3.12 стал встроенным в sum(), справляется с этим примером, но и он не гарантирует точного ответа на любых данных; точная сумма — только с запасом бит.
Посмотрите на тесты. В пятом к 10¹⁶ прибавляют сто тысяч единиц: цикл возвращает ровно 10¹⁶: соседние float64 около 10¹⁶ отстоят друг от друга на 2, единица — ровно половина шага, и округление к чётному каждый раз её выбрасывает. В шестом огромные числа гасят друг друга, и сумма по порядку выходит около −10²⁸⁷ вместо −212 тысяч. В четвёртом — дождь за 85 лет в Алматы по дням: сумма по порядку отличается от точной только в 15-м знаке, но отличается.
3+Решение
4Сложность
O(n) для цикла. Точная сумма — O(n) сложений длинных чисел по 2200 бит в Go; math.fsum в Python обычно хранит лишь несколько частей и работает почти так же быстро, как цикл.
5Типичные ошибки
- Поправка Кэхэна. Ошибается, когда маленькое число зажато между огромными разного знака, — первый и шестой тесты.
- Встроенный
sum()для первой строки. С Python 3.12 он складывает с поправкой Ноймайера, и это уже не «по порядку с округлением после каждого шага»: нужен явный цикл. - Сортировка перед сложением. Сложение от маленьких к большим уменьшает ошибку, но не убирает её.