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

[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

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

[mummy1.livejournal.com]

Я очень мало знаю о числах с плавающей точкой, и меня это сердит. И на численном анализе о них ничего не расказывали.

[avva.livejournal.com]

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

[spamsink.livejournal.com]

Прежде чем их складывать попарно, их еще и отсортировать полезно.

[eraplee.livejournal.com]

Мне кажется вопрос поставлен неправильно -- знал/не знал. То, что ошибка при арифметической операции будет (для очень маленьких чисел, не обязательно для всех с плавающей точкой) -- очевидно. И то, что она будет накапливаться очевидно тоже любому. Отсюда же можно легко сделать вывод, что наивный метод сложения даст довольно неточный результат. А вот как лучше сделать вместо наивного -- тут конечно уже не каждый сразу сообразит ;)

[michk.livejournal.com]

Средний выпускник действительно не знает (т.е. может учит, но всё равно не знает). Но вот если с этим делом работаешь - быстро на такие вещи наталкиваешься. Самый простой пример - арифметическая прогрессия с маленьким шагом.

[eraplee.livejournal.com]

а можно чуть конкретней? что даст сортировка?

[e2k-4d-x-ussr.livejournal.com]

правильнее тогда выбирать 2 минимальных и их складвать? и так пока не останется только ОДИН. :)

[akater.livejournal.com]

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

Более того, имхо, это проблема тех, кто преподаёт как раз математику, а не CS. Если курсы анализа и численных методов (в т.ч. компьютерных вычислений) не сопрягать, всё будет очень плохо.

[nine_k]

Если складывать сначала меньшие числа, их точность потеряется не так быстро.
Пример.
Пусть у вас есть число 1e+9 и миллион чисел 1; знаков в мантиссе, скажем, 8. Подумайте, что будет, если вы начнёте их складывать сразу с большего :)
Вариант с попарным сложением сначала самых маленьких тоже прикиньте.

[dizzy57.livejournal.com]

Как что? При сложении чисел разного порядка маньшее из них «нормализуется» отбрасыванием младших знаков. Таким образом, сумма массива [1, 10^-9, 1, 10^-9, …] длины порядка 10⁹ будет отличаться разительно при суммировании с сортировкой и без.

[nine_k]

Imho, да.
Мой первоначальный вариант -- отсортировать и складывать от меньших к большим.
Если складывать сначала наименьшие пары, получится и сложений меньше, и потому потенциальная потеря точности будет ещё меньше.

[nine_k]

Да можно вообще оперировать числами произвольной точности. И даже местами абсолютной, применяя рациональные дроби.
Только медленно это и места много занимает.

[igorlord.livejournal.com]

"и так далее - log(N) шагов"

There are still N-1 steps. :)

It's just that the "outer loop" of the algorithm runs log(N) times.

[ygam.livejournal.com]

По-моему, это описывается в книжке по численному анализу в серии McGraw Hill International Series on Pure and Applied Mathematics; она 13 лет назад была в майкрософтовской корпоративной библиотеке.

[ygam.livejournal.com]

http://www.emis.de/journals/NNJ/DavIns-HM.html

Does anyone believe that the difference between the Lebesgue and Riemann integrals can have physical significance, and that whether, say, an airplane would or would not fly could depend on this difference? If such were claimed, I should not care to fly in that plane. --Richard W. Hamming

[squadette.livejournal.com]

WECSSKAFPA

[igorlord.livejournal.com]

получится и сложений меньше

??? No matter what algorithm you use, there will only be N-1 сложений

[amarao-san.livejournal.com]

Вас плохо сношали в моск. Первое что нам на вычмате в голову вбили, что "математика компьютера это не математика". И десять лабораторных работ, в которых вместо ответа получалось фиг знает что, пока не "примешь меры".

[vrml.livejournal.com]

На физтехе на численных методах рассказывали.

[talash.livejournal.com]

Not a computer science graduate or student as of today, but the issue is not new to me. Programmers of the patriot missile defense system should have known better though (http://www.ima.umn.edu/~arnold/disasters/patriot.html)

[spamsink.livejournal.com]

Реальные примеры различия плавающих точек на разных архитектурах приводились в брошюре "Ошибки и ловушки при программировании на фортране" из серии "Библиотечка программиста". В качестве разных архитектур брались ЕС ЭВМ и БЭСМ-6. Первая проигрывала в длине мантиссы (24 против 40), а последняя - в диапазоне порядков (+/- 19 против +/- 38), так что нужно было заботиться и о потере значащих цифр - не только при сложении далеких чисел, но и при вычитании близких, и о пере-недо-полнениях в промежуточных результатах.

[dizzy57.livejournal.com]

Просто-таки код Хаффмена какой-то.

[dmpogo.livejournal.com]

+1

Dlja teh kto zanimaetsja chislennymi raschetami, skzazhem nauchnnymi, eto nachal'nye bazowye znanija. Ljuboj malo-malo prilichnyj chislennyj algoritm zabotitsja o wozmozhnoj poteri tochnosti.

[e2k-4d-x-ussr.livejournal.com]

как вариант 2:
написать математику сложения произвольных целых, записанных в виде строк. сконвертировать даблы в безразмерные целые (не более 1000 знаков) и поскладывать.

С умножением и делением сложнее.