Überlaufsichere Summierung

13

Angenommen, ich habe Ganzzahlen mit fester Breite (dh sie passen in ein Register der Breite w ), a 1 , a 2 , ... a n, so dass ihre Summe a 1 + a 2 + + a n = S auch in ein Register passt der Breite w .nwa1,a2,ana1+a2++an=Sw

Es scheint mir, dass wir die Zahlen immer auf vertauschen können, so dass jede Präfixsumme S i = b 1 + b 2 + + b i auch in ein Register der Breite w passt .b1,b2,bnSi=b1+b2++biw

Grundsätzlich besteht die Motivation darin, die Summe auf Registermaschinen mit fester Breite zu berechnen , ohne sich in irgendeiner Zwischenstufe um Ganzzahlüberläufe sorgen zu müssen.S=Sn

Gibt es einen schnellen (vorzugsweise linearen) Algorithmus, um eine solche Permutation zu finden (unter der Annahme des ai als Eingabearray gegeben ist)? (oder sagen Sie, wenn eine solche Permutation nicht existiert).

Aryabhata
quelle
3
Follow-up: Überlauf in Summe erkennen - Gibt es eine schnellere Methode, die typische Prozessormerkmale berücksichtigt?
Gilles 'SO- hör auf böse zu sein'
1
Verwenden Sie einfach die Zweierkomplementregister und addieren Sie diese. Selbst wenn es in der Mitte überläuft, garantiert Ihre Vorbedingung, dass sich die Überläufe aufheben und das Ergebnis korrekt ist. : P
CodesInChaos
@CodeInChaos: Stimmt das wirklich?
Aryabhata
1
Ich glaube schon. Sie arbeiten im Wesentlichen in einer Gruppe modulo 2 ^ n, in der Sie die kanonische Darstellung von -2^(n-1)bis auswählen 2^(n-1)-1. Es erfordert natürlich das Zweierkomplement und ein klar definiertes Überlaufverhalten, aber in einer Sprache wie C # sollte es funktionieren.
CodesInChaos
@CodeInChaos: Gibt es nicht zwei Möglichkeiten, die das gleiche Restmodulo ? Sie sagen im Grunde, unabhängig von der Reihenfolge, eine von ihnen kann nie passieren. Oder vermisse ich etwas? 2n
Aryabhata

Antworten:

10

Strategie
Der folgende Linearzeitalgorithmus verwendet die Strategie, um schweben , indem entweder positive oder negative Zahlen basierend auf dem Vorzeichen der Teilsumme ausgewählt werden. Die Liste der Nummern wird vorverarbeitet. Es berechnet die Permutation der Eingabe im laufenden Betrieb0 , während die Zugabe durchgeführt wird .

Algorithmus

  1. Teilen Sie in zwei Listen, die positiven Elemente P und die negativen Elemente Ma1,,anPM . Nullen können herausgefiltert werden.
  2. Sei Sum=0 .
  3. Während beide Listen nicht leer sind
  4.       Wenn { S u m : = S u m + Kopf ( M ) ; M : = Schwanz ( M ) ; }Sum>0Sum:=Sum+head(M)M:=tail(M)
  5.       sonst { ; P : = Schwanz ( P ) ; }Sum:=Sum+head(P)P:=tail(P)
  6. Wenn eine der beiden Listen leer wird, fügen Sie den Rest der verbleibenden Liste zu .S

Richtigkeit
Richtigkeit kann durch ein einfaches induktives Argument über die Länge der Zahlenliste festgestellt werden.

Beweisen Sie zunächst, dass, wenn alle positiv (oder alle negativ) sind und ihre Summe keinen Überlauf verursacht, auch die Präfixsummen nicht. Das ist unkompliziert.a1,,an

SumSum=0Sum>0SumSumSum0SumSum ist in Grenzen.

Nun kann das erste Ergebnis angewendet werden, und zusammen reichen diese Ergebnisse aus, um zu beweisen, dass die Summe niemals über die Grenzen hinausgeht.

Dave Clarke
quelle
Führen Sie für eine effiziente In-Place-Implementierung Folgendes aus: a) Quicksort-Partitionierung (die Variante mit zwei Zeigern) mit implizitem Pivot 0und dann b) zusammenfassen, indem jeweils ein Zeiger durch den Bereich mit negativem bzw. negativem Wert bewegt wird. positive Zahlen.
Raphael