о сложении (программистское)

[avva]

Числа с плавающей точкой - вот еще одно в череде компьютерных задач, которыми я занимался мало и понимаю плохо. Сегодня я узнал, что числа с плавающей точкой надо складывать - если их много - не "наивно", а особенным образом. Мне неприятно, что я до сих пор этого не знал; или если знал, то забыл - кажется логичным, чтобы это упоминалось во время курса по численному анализу, который я брал на втором курсе много лет назад, но это был один из наиболее нелюбимых предметов, и после экзамена я с радостью забыл вообще все, что его касается.

Эта тема всплыла в одной внутренней рассылке на работе, где утверждалось, что средний выпускник CS-факультета этого не знает. Я уже давно не выпускник, но честно признаюсь: не знал. А вы, коллеги, знали?

Суть проблемы вот в чем. Предположим, вам надо суммировать миллион чисел с плавающей точкой, находящихся примерно в одном диапазоне - на расстоянии одного-двух порядков друг от друга. Тогда простой, как пробка, цикл от одного до миллиона с накоплением суммы - очень плохой способ суммировать эти числа. Дело в том, что вследствие того, что промежуточные суммы будут со временем намного больше среднего слагаемого, потери точности вследствие округления начнут играть заметную роль. Суммирование миллиона чисел таким образом легко может потерять 3-4 знака точности. Если, скажем, сложить таким образом миллион одинаковых чисел, а потом сравнить с результатом умножения исходного числа на миллион, это легко заметить.

В Перле:

DB<1> $a=0.1234567890123456
DB<2> $x = 1_000_000*$a;
DB<3> for (1..1_000_000) { $y += $a; }
DB<4> x $y;
0 123456.789009695
DB<5> x $x
0 123456.789012346
DB<6> x $y-$x;
0 '-2.65109702013433e-06'


Накопившаяся разница проявляется в шестом знаке после запятой, или, иными словами, четыре последних знака потеряны.

Что делать? В общем случае - помнить об ошибках накопления и учитывать их. В конкретном случае сложения большого количества примерно одинаковых чисел самым простым оказывается складывать их "равномерно". Вместо того, чтобы одна переменная копила сумму, сложим сначала пары чисел-соседей, и получим в два раза меньше промежуточных сумм. Их тоже сложим попарно, и так далее - log(N) шагов. Пример такого алгоритма можно увидеть на этой странице (написан на Питоне).

Comments

[vova-belkin.livejournal.com]

Это еще что! Числа с плавающей точкой и сравнивать нельзя
т.е.

(4.2 - 2.2)^2 не всегда равно (5.2-3.2)^2

Факт очевидный, но на практике всегда о нем зыбываешь.

[avva.livejournal.com]

Как раз вот этот факт я помню - и это, пожалуй, единственное, что помню о проблемах с плавающей точкой. Если бы я писал что-то нетривиальное обрабатывающее много таких чисел, до того, как прочитал об этой теме сегодня, то сравнивал бы я осторожно (сравнивая модуль разницы с подходящей маленькой константой), а вот складывал бы наивно, не задумываясь.

[ltwood.livejournal.com]

К сожалению это тоже неправильно, такой параноидальный стиль часто встречается и часто приводит к еще бОльшим потерям в точности ответа.

[bamsic.livejournal.com]

Я бы поправил.

Нельзя сравнивать на "равенство".
А сравнивать на "больше"/"меньше" допустимо.

[109.livejournal.com]

гы. вы не программист, я правильно догадался?

[bamsic.livejournal.com]

Как раз программист.

[109.livejournal.com]

http://avva.livejournal.com/1794789.html?thread=44230117#t44230117

[ltwood.livejournal.com]

Он прав.

[109.livejournal.com]

http://avva.livejournal.com/1794789.html?thread=44230117#t44230117

[lazyreader.livejournal.com]

Расскажите, пожалуйста, про машину, в которой числа с плавающей точкой нельзя сравнивать на больше/меньше. То есть чтобы число a было математически меньше числа b, но сравнение их машинных представлений давало бы иной результат.

Или нет, не рассказывайте про машину. Просто объясните тёмным, как это возможно в принципе.

[109.livejournal.com]

мля. если равенство даёт неправильный результат, т.е. (a == b) evaluates to false when it should be true, то одно из сравнений (a < b), (a > b) тоже гарантированно даст неправильный результат (will evaluate to true when it should be false). мне трудно себе представить программиста, не понимающего таких простых вещей.

[lazyreader.livejournal.com]

Да, я уже сообразил, после того, как написал. Я не занимаюсь вычислительными задачами, поэтому этот вопрос, так сказать, "не входил в круг моих понятий" (иначе говоря, ответ на него отсутствовал в кэше).

[bamsic.livejournal.com]

Используя больше/меньше мы не требуем точного результата, нам достаточно приближения.

А использование равенства, подразумевает получение точного результата.

[lazyreader.livejournal.com]

С другой стороны, запись

while ( a < b ) {
....
}



в программистском (практическом) смысле ничем не отличается от

while ( b - a > epsilon ) {
...
}



Так что сравнивать плавающие числа на неравенство всё-таки можно.

[109.livejournal.com]

> ничем не отличается

you must be kidding me.

[ltwood.livejournal.com]

К сожалению, сущность проблемы состоит совсем в другом. Никто не предлагал заменить «некорректное» сравнение на равенство логическим выражением с двумя «корректными» неравенствами (а только для случая такой замены приведенное умозаключение представляет ценность). Более того, корректное определение сравнения на равенство (кстати, разное в разных задачах) обычно оказывается совместным с одним из двух неравенств.

Действительная проблема со сравнением на равенство состоит в том, что из-за ошибок, всегда присутствующих в вычислениях с плавающей точкой, сравнение на равенство почти всегда (за исключением тривиальных случаев меры ноль) оказывается не выполненным т.е. равенство просто не является подходящим отношением эквивалентности для сравнения вещественных чисел. [Здесь есть одно важное исключение — сравнение на равенство нулю, которое, как ни странно, в корне отличается от сравнения с ненулевым числом и всегда корректно.] В отличие от равенства сравнение на больше/меньше не доставляет таких неприятностей — хотя на границе действительно наблюдается некоторый «дребезг», тем не менее, при таких сравнениях отсутствует необходимость в дополнительных ухищрениях.

[ltwood.livejournal.com]

чтобы число a было математически меньше числа b, но сравнение их машинных представлений давало бы иной результат.

Кстати, легко привести пример таких чисел a и p, что неравенство p > 0 выполнено, но неравенство a + p > a уже не выполнено. Если Вы подумаете секунду, то сами поймете, что существование таких чисел совершенно очевидно.