Soma segura de estouro

Suponha que eu receba números inteiros de largura fixa (ou seja, eles se encaixam em um registro de largura w ), a 1 , a 2 , … a n de modo que sua soma a 1 + a 2 + ⋯ + a n = S também se encaixe em um registro de largura w .$n$$w$$a_1, a_2, \dots a_n$$a_1 + a_2 + \dots + a_n = S$$w$

Parece-me que sempre podemos permutar os números para modo que cada soma de prefixo S i = b 1 + b 2 + ⋯ + b i também se ajuste a um registro de largura w .$b_1, b_2, \dots b_n$$S_i = b_1 + b_2 + \dots + b_i$$w$

Basicamente, a motivação é calcular a soma em máquinas de registro de largura fixa sem ter que se preocupar com estouros de número inteiro em qualquer estágio intermediário.$S = S_n$

Existe um rápido (tempo de preferência linear) algoritmo para encontrar uma tal permutao (assumindo a são dadas como uma matriz de entrada)? (ou diga se essa permutação não existe).$a_i$

Estratégia
O algoritmo de tempo linear a seguir adota a estratégia de pairar em torno de , escolhendo números positivos ou negativos com base no sinal da soma parcial. Ele processa previamente a lista de números; calcula a permutação da entrada on-the-fly , enquanto executa a adição.$0$

Algoritmo

1. Particionar em um duas listas, os elementos positivos P e os elementos negativos M . Os zeros podem ser filtrados.$a_1, \ldots, a_n$$P$$M$
2. Deixe .$Sum=0$
3. Embora as duas listas não estejam vazias
4. $~~~~~~$Se { S u m : = S u m + cabeça ( H ) ;$Sum>0$$Sum:=Sum+\text{head}(M)$ ; }$M:=\text{tail}(M)$
5. $~~~~~~$outro { ; P : = cauda ( P ) ; }$Sum:=Sum+\text{head}(P)$$P:=\text{tail}(P)$
6. Quando uma das duas listas fica vazio, adicione o resto da lista restante para .$S$

Correção A
correção pode ser estabelecida usando um argumento indutivo direto no comprimento da lista de números.

Em primeiro lugar, provar que se são todos positivos (ou todos negativos), e sua soma não causa excesso, em seguida, nem as somas de prefixo. Isso é direto.$a_1, \ldots, a_n$

Em segundo lugar, provar que é dentro de limites é uma invariante do ciclo do algoritmo. Claramente, isto é verdade em cima da entrada para o circuito, como S u m = 0 . Agora, se S u m > 0 , adicionando um número negativo que está dentro de limites para a S u m não causa S u m para ir fora dos limites. Da mesma forma, quando S u m ≤ 0, adicionar um número positivo dentro dos limites da soma não causa S u m sair dos limites. Assim, ao sair do loop,$Sum$$Sum=0$$Sum>0$$Sum$$Sum$$Sum\le0$$Sum$ é dentro de limites.$Sum$

Agora, o primeiro resultado pode ser aplicado e, juntos, são suficientes para provar que a soma nunca sai dos limites.