Сложение чисел, сильно различающихся по значению

[Gickle]

Доброго времени суток. Предположим, у нас есть сравнительно большой ($10^6$) массив, сотоящий из чисел формата двойной точности в некотором интервале $\sim [-10^{27};10^{27}]$, распределение более-менее равномерное. Мы разбрасываем их случайным образом по массиву и начинаем складывать.

1. По индексам от $i = 1$ до $i = 10^6$.
2. В обратную сторону.
3. Сортируем числа по их значению, складываем.
4. То же самое, но теперь сумма в формате более высокой точности.

Я понимаю, что верить первым двум ответам нельзя, потому что будут возникать ситуации типа $a + b$ при $\lvert a \rvert \ll \lvert b \rvert$. А вот чему верить из последних двух вариантов? Переполнения быть не должно при суммировании, поскольку формат двойной точности числа до $\sim 10^{38}$ позволяет записывать. Так что не очень понимаю, где можно прикопаться в 3-м варианте. А в 4-м, казалось бы, всё ещё лушче быть должно. Или какие-то хитрые округления всю малину портят?

[atlakatl]

3. В этом варианте сортировать надо по модулю. И суммировать с минимального значения модуля.

[venco]

Может быть ещё ситуация $a+b$ где $a \approx -b$.
Даже без специально подобранных значений абсолютное значение суммы ожидается около $\frac{10^{27}}{\sqrt{10^6}}=10^{24}$.
Самые большие числа имеют абсолютную погрешность представления double и ошибку суммирования порядка $10^{27}\cdot 10^{-15} =10^{12}$, значит относительная точность результата получается $10^{-12}$, заметно хуже точности double.
Возможно, ошибку суммирования можно улучшить, складывая числа в порядке роста абсолютной величины, но всё равно, вряд ли имеет смысл говорить о точности суммы большей, чем точность исходного представления больших чисел.

[Gickle]

atlakatl
Не могли бы вы поподробнее объяснить этот момент? Почему именно так?

venco
В последнем случае, к слову, ответ получается 0, кажущийся мне правдоподобным (задача учебная).

[atlakatl]

Gickle
Если суммировать в обычном порядке, то у нас сумма начнётся с больших отрицательных чисел и по мере приближения к нолю и в его положительной окрестности мелкие значения будут "съедаться" за счёт ограниченной разрядности представления чисел.
Грубый пример. Точность 3 знака. Есть массив $(-16200, -9870, -124, -12, 35, 358, 4560, 13900)$
Точное суммирование даёт -7353. Суммирование с минимального значения - и округления на каждом шаге суммы до трёх знаков - даёт -7300. А аналогичное суммирование в порядке возрастания модуля - $-12+35-124+358+4560-9870+13900-16200$ даёт -7350.

[slavav]

Отличная задача!

Пятый вариант для положительных чисел:
Собираем все числа в кучу, удаляем два наименьших, помещаем обратно их сумму. Повторяем пока в куче не останется одно число. Этот вариант улучшает суммирование отсортированных чисел. О-большое остаётся таким же.

Ещё замечание: сортировать числа не обязательно, достаточно собрать их в корзины по показателям степеней. С точки зрения О-большого это лучше. Можно показать, что точность у корзин и у сортировки будет одинаковая.

Если числа разных знаков, то можно предложить такой "алгоритм": выбираем из набора пару чисел с минимальной по модулю суммой. Числа удаляем, сумму помещаем обратно в набор. Этот алгоритм соответствует кучевому алгоритму для положительных чисел. Осталось додумать как выбирать пару с минимальной суммой.

[Gickle]

atlakatl
Ой-ой, действительно. Стыдно, что сам не подумал об этом. К слову, это получается, что простым способом типа $sum = sum + a[i]$ "жирные" (в смысле суммы) массивы вообще плохая идея суммировать? То есть, грубо говоря, начиная с какого-то момента $sum$ "разгонится" так или иначе, и дальше уже всё плохо будет.

slavav
Да, я вот сейчас тоже задумался в таком направлении. :)

[arseniiv]

Есть ещё способ суммирования с небольшой коррекцией потери точности: Kahan summation algorithm. Или можно делить массив рекурсивно на части, складывая их суммы (упомянуто и в статье в «Alternatives»). Не знаю, насколько лучше объединять эти вещи с сортировкой/разделением по показателям.

[Mihaylo]

Шестой вариант.
Рассуждение:
1. Наиболее лучшими с точки зрения потери точности являются операции с числами, близкими по модулю. Сортируем по модулю. Принцип "разделяй и властвуй": складываем соседние числа попарно, из миллиона чисел получаем $500000$ компонентов суммы. Затем выполняем еще попарное сложение - получаем $250000$ тысяч компонентов и т.д.
2. Для ускорения вычисления суммы: нет смысла вычислять слишком мелкие компоненты суммы, так как они могут выпасть из разрядности формата конечной суммы. Допустим массив компонентов отсортирован по убыванию, первые $i$ компонентов дают в сумме $S_a$, последующие $(n-i)$ компонентов в сумме равны $S_b$. Можно не вычислять $S_b$, если $|S_a|>>|S_b|$. Предлагается находить разрывы между соседними компонентами суммы $S_i$ и $S_{i+1}$. Самое простое - разрывом считать условие $|S_i|>>(n-i)\cdot |S_{i+1}|$. Если условие соблюдается, то $(n-i)$ последних компонент суммы можно отбросить.
Можно придумать другие условия разрывов, которые дадут более эффективное вычисление, в том числе вероятностные.

[arseniiv]

$\gg$ — это в физике, может, и условие, а в CS не условие.

[Mihaylo]

В вычислениях можно определить это условие, зная только характеристики формата вещественного числа.
P.S. Сама сортировка - это очень плохая мысль, пусть уж лучше будет что-то вроде Кэхэна, только на русском языке.

[slavav]

Mihaylo в сообщении #1163654 писал(а):

Сама сортировка - это очень плохая мысль

Почему?
Сортировка значительно улучшает точность в большинстве случаев, и очень просто реализуется. Что с ней не так?

[arseniiv]

(Оффтоп)

Mihaylo в сообщении #1163654 писал(а):

В вычислениях можно определить это условие, зная только характеристики формата вещественного числа.

Так мы же знаем: двойная точность — IEEE 754 binary64. Хотя нет проблем и для произвольных параметров.

[Mihaylo]

slavav в сообщении #1163660 писал(а):

Сортировка значительно улучшает точность в большинстве случаев, и очень просто реализуется. Что с ней не так?

Сортировка+сложение работает медленнее, чем просто точное сложение или некое умное простое сложение. Какова цель алгоритма? Экономия времени или высокая точность?

[slavav]

Цель алгоритма получить достаточно точную сумму быстрее чем это сделает точное сложение.
Есть примеры в которых точное сложение заведомо медленнее сортировки. То есть, сортировку нельзя отбрасывать исходя только из требований производительности.