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

[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

[kingoleg.livejournal.com]

Мне об этом рассказывали. Правда, я на потоке прикладной математики учился.

[http://users.livejournal.com/malfet_/]

Я об этом знаю - жесткие дифференциальные уравнения были любимой темой нашего лектора по выч.матам.

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

[e2pii1.livejournal.com]

Я знал.
Ho я не выпускник CS :-)

[ex-ex-annut.livejournal.com]

Вот эта старая штучка очень полезна
http://citeseer.ist.psu.edu/goldberg91what.html

[kot-ivanovich.livejournal.com]

Ну каждый, кто программировал что-нибудь численное – знает, даже если по образованию и не CS... Это еще счастливый (и не очень реалистичный) случай, когда то, что надо складывать, лежит в массиве, и соответственно, можно самому выбирать порядок сложения. Чаще слагаемые вычисляются/измеряются в независящем от программиста порядке, и памяти запомнить их все нет...

Кстати, предлагаемый алгоритм на питоне для больших N ужасающе неэффективен на современных (Intel/AMD/PowerPC) процессорах – он ходит по памяти с большим шагом, эффективно вырубая L2 кэш...Считать количество сложений в наше время глупо – обращение к памяти медленнее любого сложения...

[alexcohn.livejournal.com]

На самом деле, алгоритм из http://www.ubookcase.com/book/Oreilly/Python.Cookbook.2nd.edition/0596007973/pythoncook2-chp-18-sect-15.html - совсем не практичен даже отвекаясь от L2 кэша: "Most of the time, you probably don't want to pay the price of slowing down a summation by five times in order to increase your digits of accuracy from 10 or 11 to 15" - говорят сами авторы.

В реальности граздо эффективнее пользоваться при обработке floating point повышенной точностью (например, так построены стандартные библиотеки C) - потеря производительности будет значительно меньше. Ну, и есть упомянутый выше Кахан.

[kot-ivanovich.livejournal.com]

В реальности гораздо эффективнее пользоваться при обработке floating point повышенной точностью

Абсолютно согласен. А за Кахана спасибо – не знал.

[ltwood.livejournal.com]

Конечно знал, поскольку именно этим занимаюсь. Хотя мне всегда казалось странным то, насколько много есть людей, которые никогда не складывали 1000 чисел, равных 0.1 и не смотрели на ответ.

Решение с «равномерным» суммированием кажется мне совершенно неинтуитивным, я бы до него никогда не додумался. Алгоритм Кахана, который описан и в упоминаемой выше статье Голдберга, кажется мне гораздо более понятным — кажется совершенно естественным поддерживать переменную, хранящую текущее значение накопленной ошибки (значение этой переменной будет малым и проблем с порядком не возникнет).