Bezpieczne podsumowanie przelewu

Załóżmy, że podano mi liczb całkowitych o stałej szerokości (tzn. Mieszczą się one w rejestrze szerokości ), tak że ich suma również mieści się w rejestrze szerokości .w a 1 , a 2 , … a n 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$

Wydaje mi się, że zawsze możemy permutować liczby na tak, że każda suma prefiksu również mieści się w rejestrze szerokości .S i = b 1 + b 2 + ⋯ + b i$b_1, b_2, \dots b_n$$S_i = b_1 + b_2 + \dots + b_i$$w$

Zasadniczo motywacją jest obliczenie sumy na maszynach o stałej szerokości bez martwienia się o przelanie liczb całkowitych na dowolnym etapie pośrednim.$S = S_n$

Czy istnieje szybki (najlepiej liniowy czas) algorytm do znalezienia takiej permutacji (zakładając, że podano jako tablicę wejściową)? (lub powiedzieć, czy taka permutacja nie istnieje).$a_i$

Strategia
Poniższy algorytm czasu liniowego przyjmuje strategię najechania kursorem około , wybierając liczby dodatnie lub ujemne na podstawie znaku sumy częściowej. Przetwarza listę liczb; oblicza permutację danych wejściowych w locie podczas wykonywania dodawania.$0$

Algorytm

1. Partycja do obu listach, pozytywne elementy i negatywne elementy . Zera można odfiltrować. P $a_1, \ldots, a_n$$P$$M$
2. Niech .$Sum=0$
3. Chociaż obie listy nie są puste
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. Gdy jeden z dwóch list staje się pusta, dodać resztę pozostałego do listy .$S$

Poprawność
Poprawność można ustalić za pomocą prostego argumentu indukcyjnego dotyczącego długości listy liczb.

Po pierwsze, udowodnij, że jeśli są dodatnie (lub wszystkie ujemne), a ich suma nie powoduje przepełnienia, to też nie sumują prefiksu. To jest proste.$a_1, \ldots, a_n$

Po drugie, udowodnienie, że mieści się w granicach, jest niezmiennikiem pętli algorytmu. Oczywiście jest to prawdą po wejściu do pętli, ponieważ . Teraz, jeśli , dodanie liczby ujemnej mieszczącej się w granicach do nie spowoduje, że przekroczy granice. Podobnie, gdy dodanie liczby dodatniej, która jest w granicach do sumy, nie powoduje, że wychodzi poza granice. Zatem po wyjściu z pętli mieści się w granicach.S u m = 0 S u m > 0 S u m S u m S u m ≤ 0 S u m S u $Sum$$Sum=0$$Sum>0$$Sum$$Sum$$Sum\le0$$Sum$$Sum$

Teraz można zastosować pierwszy wynik i razem są one wystarczające, aby udowodnić, że suma nigdy nie wychodzi poza granice.