Sommation sûre de débordement

Supposons que l'on me donne entiers de largeur fixe (c'est-à-dire qu'ils s'inscrivent dans un registre de largeur w ), a 1 , a 2 , … a n tels que leur somme a 1 + a 2 + ⋯ + a n = S s'inscrit également dans un registre de largeur w .$n$$w$$a_1, a_2, \dots a_n$$a_1 + a_2 + \dots + a_n = S$$w$

Il me semble que l'on peut toujours permuter les nombres à telle sorte que chaque somme de préfixe S i = b 1 + b 2 + ⋯ + b i rentre également dans un registre de largeur w .$b_1, b_2, \dots b_n$$S_i = b_1 + b_2 + \dots + b_i$$w$

Fondamentalement, la motivation est de calculer la somme sur des machines à registre à largeur fixe sans avoir à se soucier des débordements d'entiers à n'importe quel stade intermédiaire.$S = S_n$

Existe-t-il un algorithme rapide (de préférence linéaire) pour trouver une telle permutation (en supposant que les sont donnés comme un tableau d'entrée)? (ou dire si une telle permutation n'existe pas).$a_i$

Stratégie
L'algorithme de temps linéaire suivant adopte la stratégie de vol stationnaire autour de , en choisissant des nombres positifs ou négatifs en fonction du signe de la somme partielle. Il pré-traite la liste des numéros; il calcule la permutation de l'entrée à la volée , tout en effectuant l'addition.$0$

Algorithme

1. Partitionner en a deux listes, les éléments positifs P et les éléments négatifs M . Les zéros peuvent être filtrés.$a_1, \ldots, a_n$$P$$M$
2. Soit .$Sum=0$
3. Bien que les deux listes ne soient pas vides
4. $~~~~~~$Si { S u m : = S u m + tête ( M ) ; M : = queue ( M ) ; }$Sum>0$$Sum:=Sum+\text{head}(M)$$M:=\text{tail}(M)$
5. $~~~~~~$else { ; P : = queue ( P ) ; }$Sum:=Sum+\text{head}(P)$$P:=\text{tail}(P)$
6. Lorsque l' un des deux listes est vide, ajoutez le reste de la liste restante .$S$

Exactitude L'
exactitude peut être établie en utilisant un argument inductif simple sur la longueur de la liste des nombres.

Premièrement, prouver que si sont tous positifs (ou tous négatifs), et que leur somme ne provoque pas de débordement, alors les sommes de préfixe non plus. C'est simple.$a_1, \ldots, a_n$

Deuxièmement, prouver que est dans les limites est un invariant de la boucle de l'algorithme. De toute évidence, cela est vrai lors de l'entrée dans la boucle, comme S u m = 0 . Maintenant, si S u m > 0 , l'ajout d'un nombre négatif dans les limites de S u m ne fait pas sortir S u m des limites. De même, lorsque S u m ≤ 0, l' addition d'un nombre positif qui se trouve dans les limites de la somme ne fait pas sortir S u m des limites. Ainsi, à la sortie de la boucle,$Sum$$Sum=0$$Sum>0$$Sum$$Sum$$Sum\le0$$Sum$ est dans les limites.$Sum$

Maintenant, le premier résultat peut être appliqué, et ensemble, ils sont suffisants pour prouver que la somme ne sort jamais des limites.