Überlauf bei Berechnung erkennen

[himitsu]

N'aben ihr,

wie ihr vielleicht bemerkt habt, arbeite ich grad an 'ner (anfangs) kleinen BigInt-Implementation.

Und obwohl erstmal (hoffentlich) richtig gerechnet wird,
hab ich Probleme einen Integerüberlauf ( {$R+} ) zu erkennen ... ich seh einfach den Wald vor lauter Bäumen nicht mehr

hier mal einige Werte und deren Ergebnisse:

Code:

.                        # OverflowValue

*10000 +    100 =  10100 # $00000000
-10000 +    100 =  -9900 # $00000000
-10000 +   -100 = -10100 # $00000001
*10000 +   -100 =   9900 # $00000001
*10000 +  20000 =  30000 # $00000000
*10000 + -20000 = -10000 # $00000000
-10000 + -20000 = -30000 # $00000001
-10000 +  20000 =  10000 # $00000001

*10000 -    100 =   9900 # $00000000
-10000 -    100 = -10100 # $00000000
-10000 -   -100 =  -9900 # $ffffffff
*10000 -   -100 =  10100 # $ffffffff
*10000 -  20000 = -10000 # $ffffffff
*10000 - -20000 =  30000 # $ffffffff
-10000 - -20000 =  10000 # $00000000
-10000 -  20000 = -30000 # $00000000

//     MinBigInt = -67...03042048
//     MaxBigInt =  67...03042047

MinBigInt +  100 = -67...03041948 # $00000000
MaxBigInt + -100 =  67...03041947 # $00000001
MinBigInt - -100 = -67...03041948 # $ffffffff
MaxBigInt -  100 =  67...03041947 # $00000000

// reIntOverflow
MinBigInt + -100 =  67...03041948 # $00000001
MaxBigInt +  100 = -67...03041949 # $00000000
MinBigInt -  100 =  67...03041948 # $00000000
MaxBigInt - -100 = -67...03041949 # $ffffffff

Welche Werte ich nach der Berechnung noch zur Verfügung hab:

Code:

X +/- Y = Z

Sign(X), Y, Z und OverflowValue
und natürlich auch Sign(Y) und Sign(Z)

da ich direkt mit X rechne, geht dieses verloren und ich würde gern verhindern dieses extra zu speichern


ich hatte zwar schon versucht etwas zusammenzubekommen
und bei einer Berechnung ohne Überlauf stimmte es inzwischen auch,
allerdings liefert B auch bei einem Überlauf true (also speziell bei den letzten 4 Berechnungen)

Delphi-Quellcode:

// für Addition
B := X.isNegaive;
// Berechnung ... Z := X + Y;
B := not (((B = Z.isNegaive) and (B = Y.isNegaive))
  or ((Z.isNegaive <> Y.isNegaive) and (Abs(Z) > Abs(Y)))
  or ((Z.isNegaive = Y.isNegaive) and (Abs(Z) < Abs(Y))));
If B Then Integer_Overflow;


// für Subtraktion
B    := X.isNegaive;
// Berechnung ... Z := X - Y;
B := not (((B = Z.isNegaive) and (B <> Y.isNegaive))
  or ((Z.isNegaive = Y.isNegaive) and (Abs(Z) > Abs(Y)))
  or ((Z.isNegaive <> Y.isNegaive) and (Abs(Z) < Abs(Y))));

meine Addition sieht aktuell etwa so aus
werd' es demnächst auf von Pascal mit 64 Bit auf ASM mit 32 Bit und ADC(SBB) umstellen, wo ich im Carry zumindestens den interen den Überlauf drin hab ... mal sehn wie es nach dem letzen Wert (High Byte) aussieht,
aber auch so (in Pascal) sollte es doch zum Funktionieren bekommen?

Delphi-Quellcode:

Procedure TBigInt._Add(Const i: TBigInt);
  Var B: Boolean;
    i2: LongInt;
    T: TLargeWordRec;

  Begin
    B    := LongInt(Data[High(Data)]) < 0;
    i2   := 0;
    T.Hi := 0;
    Repeat
      T.Org := LargeWord(Data[i2]) + i.Data[i2] + T.Hi;
      Data[i2] := T.Lo;
      Inc(i2);
    Until i2 = Length(Data);
      B := not (((B = (LongInt(Data[High(Data)]) < 0)) and (B = (LongInt(i.Data[High(Data)]) < 0)))
        or (((Data[High(Data)] and $80000000) <> (i.Data[High(Data)] and $80000000)) and (Abs(Self) > Abs(i)))
        or (((Data[High(Data)] and $80000000) = (i.Data[High(Data)] and $80000000)) and (Abs(Self) < Abs(i))));
      {$IFOPT R+} If B Then Error(reIntOverflow) {$ENDIF};
    End;

[gammatester]

Durch Deine Beitrage im anderen Thread nehme ich an, daß Deine TBigInt eine fixe Maximalgröße haben, sonst würde sich das Overflowproblem anders stellen.

Ohne Definition der Typen kann man allerding nix genaues sagen.

Z.B. verstehe ich das 'Geeiere' mit LongInt(Data[High(Data)]) < 0, Abs(Self) >/< Abs(i) nicht. Insbesondere Data[High(Data)] and $80000000 <> 0 sollte doch das gleiche sein wie LongInt(Data[High(Data)]) < 0 ???

Wenn Du Signed-Magnitude-Darstellung benutzt (und nicht 2-er Komplement), hast Du einen Overflow wenn das Carry (T.Hi?) nach der Schleife ungleich 0 ist. Bei dynamischer Arraygröße würde man dann ein neues Digit 'aufmachen' mit Wert T.Hi.

Nebenbei: isNegaive sollte doch wohl isNegative heißen??

Gruß Gammatester

[himitsu]

jup, erstmal 'ne fixe Größe
hab einen Integer mit fixer Größe geplant und einen Float ... die verhalten sich speichertechnisch halt genauso wie eine normale Variable.
und dann soll's noch 'nen variablen Float geben.

Es ist 2-er-Komplement ... halt "nur" 'ner Erweiterung des "normalen" Integers, mit des selben Definition.
Wolte halt mal was anderes erschaffen, als sonst auf dem Markt ist

bei variabler Länge würde ich auch einfach neues "Feld" anlegen und mit dem Überlaufwert füllen,
aber hier geht es ja nicht.

und nein, bei 2-er-Komplement gibt es rechenmäßig auch Überlaufwerte, welche keinen Überlauf darstellen ... das ist ja des Kern meines Problemes.
bei den Berechnungen steht nach dem "#" der Wert im Überlaufregister und der ist nicht immer null.

ich muß halt nur irgendwie eine formel aufstellen, die rüft, wann welche Werte erlaubt sind.

Data[High(Data)] and $80000000 <> 0
stellt wirklich das
LongInt(Data[High(Data)]) < 0
dar, nur ist die Übersetzung kürzer

Delphi-Quellcode:

// Data[15] and $80000000 <> 0
// LongWord(Data[15]) and $80000000 <> 0
MOV EAX, Data[15]
AND EAX, $80000000
CMP EAX, 0  // könnte man eigentlich weglassen ... macht Delphi aber nicht
JNZ ...

// LongInt(Data[15]) < 0
CMP Data[15], 0
JS ...

@isNegative = Tippfehler (hab es halt versucht der Verständnis halber zu verkürzen ... hab dort ja eigentlich das LongInt-Geeiere )

[gammatester]

Hier ein Stück Code, das Overflow detektiert für longints. Ein Problem ist: wenn Delphi-Overflowcheck an ist, darf x+y+c nicht berechnet werden, wenn ovr=true ist.

Weiter solltest Du T.Hi auswerten nach der Schleife, wenn's <>0 ist hast Du mit Sicherheit einen Overflow.

Delphi-Quellcode:

var
  x,y,c,z: longint;
  ovr: boolean;
begin
  x   := $3FFFFFFF;
  y   := $3FFFFFFF;
  c   := 2;
  {ovr=true wenn x+y+c Overflow produziert, Ref. Hacker's Delight 2-12}
  z   := (not (x xor y)) and $80000000;
  ovr := (z and (not ((x xor z) + y + c) xor y)) <> 0;
  writeln(x+y+c, '   Overflow: ', ovr);
end.

Was ist eigentlich mit {$Q+}, Du hast nur {$R+}.

Gruß Gammatester

[himitsu]

Zitat:

Was ist eigentlich mit {$Q+}, Du hast nur {$R+}.

$Q = FloatOverflow
$R = RageCheck + IntegerOverflow

ich hatte zwar auch ers $Q, aber Delphi verwendet $R bei inem Integeroverflowcheck ... ist auch etwas verständlich, da es sich um einen festen Range (MinInt..MaxInt) handelt.

Code:

-10000 +   -100 = -10100 # $00000001

T.Hi = 1 ... also zwar <> 0, aber dennoch kein wirklicher Überlauf

der vermeintliche Überlauf entsteht, da im HiWord des der werte $ffffffff + $ffffffff + T.Hi (T.Hi ist in diesem Fall auch $ffffffff) gerechnet wird, was ja für die negativen Werte korrekt ist.

Hier ein Stück Code, das Overflow detektiert für longints ein Problem hierbei ist, daß, wenn ich diese Formel so überehmen, wieder einigee "große/aufwendige" Berechnugen gemacht werden müßten (not, and, xor, add und "<>") was wiederrum viel Zeit in Anspruch nimmt.


PS: klar wäre z.B. bei Signed-Magnitude einiges Einfacher, aber vorallem die doppelten Werte wie 0 und -0 sind für mich mehr abschreckend
und dazu ist sowas auch nicht binär kompatibel zu Integer und Co.

[gammatester]

Das Carry kann doch nicht negativ sein! Alle 32-Bit-Teile (bis auf das Werthöchste) müssen doch unsigned berechnet werden. Das Carry kann bei Additionen nur 0 oder 1 sein.

Deine Interpretation von Q+ ist übrigens nicht richtig. Delphi-Hilfe: The $Q directive controls the generation of overflow checking code. In the {$Q+} state, certain integer arithmetic operations (+, -, *, Abs, Sqr, Succ, Pred, Inc, and Dec) are checked for overflow.

[himitsu]

stimmt, in der Hilfe stand auch sowas, aber als ich angefangen die Überlauftests einzubauen kamen bei $Q keine Exceptions raus, aber dafür bei $R ... drum hatte ich es damals auf $R geändert.


nja, hast mich zum nochmaligen Testen gebracht und ich werd's morgen ändern (geh gleich schlafen)

mein Fehler war wohl, daß ich zuerst andere Fehler bekam und diese einfach übernahm

tja, wie gesagt, manchmal verstickt man sich einfach so tief, daß man es garnicht merkt ;(

Delphi-Quellcode:

var
  i: LongInt;
  W: LongWord;
begin

{$Q+}{$R-}
try
  i := $7fffffff;
  if i = 0 then ;
  Inc(i);
except
  Application.MessageBox('Inc Q+', '');
end;
if i = 0 then ;
{$Q-}{$R+}
try
  i := $7fffffff;
  if i = 0 then ;
  Inc(i);
except
  Application.MessageBox('Inc R+', '');
end;
if i = 0 then ;


W := $80000000;
{$Q+}{$R-}
try
  i := W;
except
  Application.MessageBox('=  Q+', '');
end;
if i = 0 then ;
{$Q-}{$R+}
try
  i := W;
except
  Application.MessageBox('=  R+', '');
end;
if i = 0 then ;

aber was mein Problem betrifft:
mir ist grad aufgefallen, daß ich ABS im Fall eines <>-Vergleiches garnicht so einfach anwenden kann (bezüglich der Ausnahme mit MinBigInt bzw. Low(TBitBigInt))

ich werd wohl doch mal 'nen Tag auslassen und mir dann das ganz Problem nochmals neu durch den Kopf gehn lassen.

[bigg]

Hi himitsu,

wenn du deine BigInt-Funktionen eh in Assembler kreirst, sollte man den Überlauf doch im 32bit-Register EAX mit "jo" bzw. jc erkennen können?!

[himitsu]

Ja, aber erstmall wird alles "möglichst" in Pascal erstellt
und später kommt eventuell noch eine alternative ASM-Version dazu.

erstmal ist es so einfacher eine andere Version daraus zu erstellen (vermutlich kommt bald noch ... wenn das hier läuft ... eine dynamische BigInt-Variante dazu)

aber ich ha es nun geschafft und das auch ohne die rechnerrich anfallenden Überläufe beachten zu müssen.

das heißt erstmal, daß ich dann bei der ASM-Version auch einiges einfacher wird, da ich das Carry-Flag nicht aus der Rechenschleife irgendwie rausbekommen muß.


Hab heute früh nochmal alles verworfen und komplett neu alles durchgedacht.
Dabei ist für die Addition im Prinzip dieses rausgekommen und es scheint sogar noch zu funktionieren.

Delphi-Quellcode:

// X + Y = Z

B :=
  (
    ((X < 0) = (Y < 0))
    and
    ((Z < 0) = (X < 0))
  )
  or
  (
    ((X < 0) xor (Y < 0))
    and
    (
      (((Z < 0) = (X < 0)) and (Abs(X) <= Abs(Y)))
      or
      (((Z < 0) = (Y < 0)) and (Abs(X) >= Abs(Y)))
    )
  );

If B Then Berechnung_OK;

Zitat von gammatester:

Das Carry kann doch nicht negativ sein! Alle 32-Bit-Teile (bis auf das Werthöchste) müssen doch unsigned berechnet werden. Das Carry kann bei Additionen nur 0 oder 1 sein.

ich hab aktuell ein 32-Bit-Carry und dieses kann $0000000, $00000001 oder $ffffffff sein.

hatte zwar mal die Berechnung zum Test von 32 Bit (64 Bit incl. Carry) auf 16 Bit (32 Bit incl. Carry) umgestellt ... nur war dieses via Pascal langsamer.

[gammatester]

Es muß ja nicht alles in ASM sein. Vielleicht nur für das werthöchste DWORD. Ich verwende zB folgende Funktion (die man notfalls noch optiomieren kann):

Delphi-Quellcode:

{---------------------------------------------------------------------------}
function add32_ovr(x,y: longint; var z: longint): boolean;
  {-add z=x+y with overflow detection}
var
  overflow: boolean;
begin
  asm
            sub  edx,edx
            mov  eax,[x]
            add  eax,[y]
            jno  @@1
            inc  edx
    @@1:    mov  [overflow],dl
            mov  edx,[z]
            mov  [edx],eax
  end;
  add32_ovr := overflow;
end;

Zum Carry: Bei Addition sollten nur 0 oder 1 auf treten, bei Subtraktion 0 oder -1. Wenn -1 bei Addition auftaucht, ist irgendwo der Wurm drin.

Gruß Gammatester