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) шагов. Пример такого алгоритма можно увидеть на этой странице (написан на Питоне).