13
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ Follow-up: Detecting overflow in summation — is there a faster method that takes into account typical processor features? $\endgroup$ – Gilles Apr 22 '12 at 1:17
  • $\begingroup$ 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 $\endgroup$ – CodesInChaos Apr 22 '12 at 11:51
  • $\begingroup$ @CodeInChaos: Is that really true? $\endgroup$ – Aryabhata Apr 23 '12 at 16:27
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Apr 23 '12 at 17:48
  • $\begingroup$ @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? $\endgroup$ – Aryabhata Apr 23 '12 at 18:01
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 3 '14 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.