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

— Aryabhata
źródło

Dalsze działania: Wykrywanie przepełnienia sumowania - czy istnieje szybsza metoda, która uwzględnia typowe funkcje procesora?

— Gilles 'SO - przestań być zły'

Wystarczy użyć rejestrów uzupełnienia do dwóch i zsumować je. Nawet jeśli przepełni się w środku, twój warunek wstępny gwarantuje, że przepełnienia zostaną anulowane, a wynik będzie prawidłowy. : P

— CodesInChaos

@CodeInChaos: Czy to naprawdę prawda?

— Aryabhata

Chyba tak. Zasadniczo pracujesz w grupowym module 2 ^ n, w którym wybierasz reprezentację kanoniczną od -2^(n-1)do 2^(n-1)-1. Wymaga to oczywiście uzupełnienia dwóch i dobrze zdefiniowanego zachowania przepełnienia, ale w języku takim jak C # powinno działać.

— CodesInChaos

@CodeInChaos: Czy nie ma dwóch możliwości, które dają tę samą resztę modulo ? Mówisz w zasadzie, bez względu na zamówienie, jeden z nich nigdy się nie wydarzy. A może coś mi brakuje?

2^{n}

$2^n$

— Aryabhata

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

Partycja do obu listach, pozytywne elementy i negatywne elementy . Zera można odfiltrować. $a_1, \ldots, a_n$ $P$ $M$
Niech . $Sum=0$
Chociaż obie listy nie są puste
$~~~~~~$ If { ; ; } $Sum>0$ $Sum:=Sum+\text{head}(M)$ $M:=\text{tail}(M)$
$~~~~~~$ else { ; ; } $Sum:=Sum+\text{head}(P)$ $P:=\text{tail}(P)$
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. $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.

— Dave Clarke
źródło

W kierunku wydajnej implementacji w miejscu wykonaj a) Szybkie dzielenie na partycje (wariant z dwoma wskaźnikami) z niejawną osią a następnie b ) zsumuj , przesuwając wskaźnik przez obszar z ujemnym resp. liczby dodatnie.

0

$0$

— Raphael