Переполнение безопасного суммирования

Предположим, мне дано целых чисел фиксированной ширины (т.е. они помещаются в регистр ширины ), , так что их сумма a 1 + a 2 + ⋯ + a n = S также помещается в регистр ширины ш .$n$$w$$a_1, a_2, \dots a_n$$a_1 + a_2 + \dots + a_n = S$$w$

Мне кажется, что мы всегда можем переставить числа в $b_1, b_2, \dots b_n$ , чтобы каждая префиксная сумма $S_i = b_1 + b_2 + \dots + b_i$ также помещалась в регистр ширины $w$ .

По сути, мотивация состоит в том, чтобы вычислять сумму $S = S_n$ на машинах с фиксированной шириной, не беспокоясь о целочисленных переполнениях на любом промежуточном этапе.

Существует ли быстрый (предпочтительно линейное время) алгоритм для поиска такой перестановки (при условии, что заданы как входной массив)? (или скажем, если такой перестановки не существует).$a_i$

Стратегия
Следующий алгоритм линейного времени принимает стратегию зависания около , выбирая положительные или отрицательные числа на основе знака частичной суммы. Он предварительно обрабатывает список номеров; он вычисляет перестановку входных данных на лету при выполнении сложения.$0$

Алгоритм

1. Partition 1 , ... , п в двух списках, положительные элементы P и отрицательные элементы M . Нули можно отфильтровать.$a_1, \ldots, a_n$$P$$M$
2. Пусть .$Sum=0$
3. Хотя оба списка не пусты
4. $~~~~~~$Если { S u m : = S u m + головка ( M ) ; М : = хвост ( М ) ; }$Sum>0$$Sum:=Sum+\text{head}(M)$$M:=\text{tail}(M)$
5. $~~~~~~$иначе { ; P : = хвост ( P ) ; }$Sum:=Sum+\text{head}(P)$$P:=\text{tail}(P)$
6. Когда один из двух списков станет пустым, добавьте остальную часть оставшегося списка на .$S$

Корректность
Корректность может быть установлена ​​с помощью прямого индуктивного аргумента длины списка чисел.

Прежде всего, докажите, что если все положительные (или все отрицательные) и их сумма не вызывает переполнения, то и суммы префиксов не делайте. Это просто.$a_1, \ldots, a_n$

Во-вторых, доказать, что находится в пределах границ, является инвариантом цикла алгоритма. Понятно, что это верно при входе в цикл, так как S u m = 0 . Теперь, если S u m > 0 , добавление отрицательного числа, которое находится в пределах границ к S u m , не приводит к тому, что S u m выходит за пределы. Аналогично, когда S u m ≤ 0, добавление к сумме положительного числа, которое находится в пределах границ, не приводит к выходу S u m за пределы. Таким образом, выходя из цикла,$Sum$$Sum=0$$Sum>0$$Sum$$Sum$$Sum\le0$$Sum$ находитсяпределах границ.$Sum$

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