# Overflow safe summation

Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$.

It seems to me that we can always permute the numbers to $b_1, b_2, \dots b_n$ such that each prefix sum $S_i = b_1 + b_2 + \dots + b_i$ also fits in a register of width $w$.

Basically, the motivation is to compute the sum $S = S_n$ on fixed width register machines without having to worry about integer overflows at any intermediate stage.

Is there a fast (preferably linear time) algorithm to find such a permutation (assuming the $a_i$ are given as an input array)? (or say if such a permutation does not exist).

• Follow-up: Detecting overflow in summation — is there a faster method that takes into account typical processor features? – Gilles Apr 22 '12 at 1:17
• Just use two's complement registers and sum them. Even if it overflows in the middle, your pre-condition guarantees that the overflows will cancel out, and the result will be correct. :P – CodesInChaos Apr 22 '12 at 11:51
• @CodeInChaos: Is that really true? – Aryabhata Apr 23 '12 at 16:27
• I think so. You're essentially working in a group modulo 2^n, where you choose the canonical representation from -2^(n-1) to 2^(n-1)-1. It of course requires two's complement and well defined overflow behavior, but in a language like C# it should work. – CodesInChaos Apr 23 '12 at 17:48
• @CodeInChaos: Aren't there two possibilities which give the same remainder modulo $2^n$? You are basically saying, irrespective of the order, one of them can never happen. Or am I missing something? – Aryabhata Apr 23 '12 at 18:01

Strategy
The following linear-time algorithm adopts the strategy of hovering around $0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input on-the-fly, while performing the addition.

Algorithm

1. Partition $a_1, \ldots, a_n$ into a two lists, the positive elements $P$ and the negative elements $M$. Zeros can be filtered out.
2. Let $Sum=0$.
3. While both lists are non-empty
4. $~~~~~~$If $Sum>0$ { $Sum:=Sum+\text{head}(M)$; $M:=\text{tail}(M)$; }
5. $~~~~~~$else { $Sum:=Sum+\text{head}(P)$; $P:=\text{tail}(P)$; }
6. When one of the two lists becomes empty, add the rest of the remaining list to $S$.

Correctness
Correctness can be established using a straightforward inductive argument on the length of the list of numbers.

First, prove that if $a_1, \ldots, a_n$ are all positive (or all negative), and their sum does not cause overflow, then nor do the prefix sums. This is straightforward.

Second, prove that $Sum$ is within bounds is an invariant of the loop of the algorithm. Clearly, this is true upon entry into the loop, as $Sum=0$. Now, if $Sum>0$, adding a negative number that is within bounds to $Sum$ does not cause $Sum$ to go out of bounds. Similarly, when $Sum\le0$ adding a positive number that is within bounds to sum does not cause $Sum$ to go out of bounds. Thus upon exiting the loop, $Sum$ is within bounds.

Now, the first result can be applied, and together these are sufficient to prove that the sum never goes out of bounds.

• Towards an efficient in-place implementation, perform a) Quicksort-partitioning (the two-pointer variant) with implicit pivot $0$ and then b) sum up, moving a pointer each through the area with negative resp. positive numbers. – Raphael Feb 3 '14 at 17:20