Wie erkennen dass eine Multiplikation ein Überlauf wird?

[GPI]

Also von nicht Float und Double. Momentan mach ich das recht kompliziert. Vorzeichen killen und dann den maximalwert durch einen der Faktoren teilen und kontrollieren, ob das Ergebnis größer oder gleich den anderen Faktor ist.

Code: Alles auswählen

#max_a=127
#max_b=255
#max_u=32767
CompilerIf #PB_Unicode
  #max_c=#max_u
CompilerElse 
  #max_c=#max_b
CompilerEndIf
#max_w=32767
#max_l=2147483647
#max_q=9223372036854775807
CompilerIf #PB_Compiler_Processor=#PB_Processor_x86
  #max_i=#max_l
CompilerElse
  #max_i=#max_q
CompilerEndIf

Macro _createcheck(type)
  Procedure CheckMul#type(a.type,b.type)
    If a<0:a=-a:EndIf
    If b<0:b=-b:EndIf
    If a=0 Or b=0 Or a=1 Or b=1
      ProcedureReturn #True
    EndIf    
    ProcedureReturn Bool( #max_#type/b>=a )
  EndProcedure  
EndMacro
  
_createcheck(w)
_createcheck(l)
_createcheck(q)



Define c.q,cc.q
Define i
Define k

c=15:cc=15
k=15
For i=2 To 29
  k=-k
  
  c=cc*k
  Debug "I:"+i+"  c:"+c
  If Not CheckMulQ(cc,k)
    Debug "NICHT SICHER!"
  EndIf
  
  ;zweiter check....
  If (c<cc And c>0) Or (-c<cc And c<0)
    Debug "c überlauf!"+i
  ElseIf c>0
    cc=c
  Else
    cc=-c
  EndIf
  
Next
Debug c

Theoretisch ist die Funktion sogar überreaktiv, der negative Bereich ist ja immer eine Zahl größer.

Alternativ könnte man auch in double berechnen und vergleichen - nur die Genauigkeit reicht für Quad nicht mehr aus.

Ich weis, das in Assembler es ein schönes Flag gibt, das man einfach überprüfen kann. Leider hab ich keine Ahnung, wie ich darauf zugreifen kann. Das wäre natürlich endlos eleganter.
Sollte dann aber in 64 oder 32-Bit funktionieren.

Edit: einfacheres Beispiel

[Helle]

Tja, die Multiplikation erscheint immer so simple; bei der Division rechnet man viel eher mit Schweinereien. In ASM gibt es für Ganzzahlen das vorzeichenlose MUL und das vorzeichenbehaftete IMUL. Wenn ich das noch richtig auf der Platte habe verwendet PB grundsätzlich IMUL in der 2-Operanden-Variante (gibt auch 1 und 3). Das heißt, das Ergebnis muss in 1 Register passen, bei einem Überlauf wird gnadenlos abgeschnitten. Dies signalisiert die CPU mit dem setzen des Overflow-und Carry-Flags (passt es, werden beide gelöscht). Da das O-Flag sich länger "hält", sollte man dies für Auswertungen verwenden:

Code: Alles auswählen

;simpler Code, verändere A und/oder B
A.q=1234567891
B.q=987654321
C.q=A*B
!jno @f  ;spring wenn kein Overflow aufgetreten; Carry geht auch (jnc)
Debug "Zu groß!"
Debug Hex(C)
End
!@@:
Debug "Passt!"
Debug Hex(C)

A und/oder B können auch negativ sein; das MSB ist Signum.
Die Auswertung der Flags sollte so schnell wie möglich erfolgen (besonders im Debug-Modus!).

Gruß
Helle

[GPI]

Danke schon mal.

Was jno bedeutet ist mir klar (vermutlich irgendwas mit jump und overflow), was bedeutet das @f ? wird dann automatisch zum nächsten !@@: (wohl ein Assemblerlabel?) gesprungen?

edit:
Leider nicht universell einsetzbar...

Code: Alles auswählen

;simpler Code, verändere A und/oder B
A.w=11
B.w=4321
C.w=A*B
!jno @f  ;spring wenn kein Overflow aufgetreten; Carry geht auch (jnc)
Debug "Zu groß!"
Debug Hex(C)+" "+c
End
!@@:
Debug "Passt!"
Debug Hex(C)+" "+c

mit word klappt das nicht mehr. Oder berechnet PB prinzipiell erstmal alles in quad (bei 64bit) und schneidet dann weg?

[Helle]

Sorry,
jno = jump if not overflow
Label ist richtig; ist anonymer Label, muss ich mir keine Gedanken um Label-Namen machen (Label schon vorhanden usw.).
Geht aber genauso:

Code: Alles auswählen

;simpler Code, verändere A und/oder B
A.q=1234567891
B.q=987654321
C.q=A*B
!jno passt  ;spring wenn kein Overflow aufgetreten; Carry geht auch (jnc)
Debug "Zu groß!"
Debug Hex(C)
End
!passt:
Debug "Passt!"
Debug Hex(C)

Dein Edit zu spät gesehen! PB macht mit Word folgendes:

Code: Alles auswählen

; A.w=11
  MOV    word [v_A],11
; B.w=4321
  MOV    word [v_B],4321
; C.w=A*B
  MOVSX  r15,word [v_A]
  MOVSX  rax,word [v_B]
  IMUL   r15,rax
  MOV    rax,r15
  MOV    word [v_C],ax     

Tja, so funktioniert das natürlich nicht... PB erweitert Word auf Quad (64-Bit-OS) und multipliziert erst dann . Shit, böse Falle. IMUL Reg16, Mem16 geht durchaus. Könnte man fast als Bug ankreiden.

[GPI]

Mist, schade. Ich schätze mal, das ist eine einfache Möglichkeit verschiedene Typen miteinander zu multiplizieren. Leider gibts keinen Check vorher, was der kleinste gemeinsame "Nenner" ist, sondern mit gleich einfach quad...

Die Idee ist wohl damit gestorben und doch recht unsicher...

Aber könntest du mir folgendes machen?

Code: Alles auswählen

global warning_overflow.i
procedure.q Mul(a.q,b.q)
  warning_overflow=#false
  ;assemblercode für a=a*b ;also ergebnis in a speichern. 
  !jno @f  
  warning_overflow=#true
  !@@:
  procedurereturn a
endprocedure
procedure.q add(a.q,b.q)
  warning_overflow=#false
  ;assemblercode für a=a+b ;also ergebnis in a speichern. 
  !jno @f  
  warning_overflow=#true
  !@@:
  procedurereturn a
endprocedure
procedure.q shl(a.q,b.q)
  warning_overflow=#false
  ;assemblercode für a=a<<b ;also ergebnis in a speichern. 
  !jno @f  
  warning_overflow=#true
  !@@:
  procedurereturn a
endprocedure

Dann hätte ich den Quad-Fall abgedeckt und in den anderen Fällen wandle ich die Zahlen in Quad um, multipliziere und schau ob ich den Wertebereich sprenge. Wen PB das intern eh umrechnet, ist das auch schon wurscht

edit: Wenn die Mulitplikation/Addition/Shift über Assemblercode direkt gemacht wird, ist das ganze sehr zukunftsicher. Ich könnte natürlich auch A=A*B dafür schreiben, wenn aber PB irgendwas ändert, dann funktioniert der Code nicht mehr. Wenn das ganze bis zur Abfrage manuell in Assembler erfolgt, kann nichts mehr passieren, das dürfte auch in Zukunft sicher sein.

Wie gesagt, müsste sowohl in 64bit als auch 32bit funktionieren.

Wird bei 32Bit auch in Quad berechnet?

[Helle]

Ja, PB(x64) setzt auch DWord in Quad um. Da heute Freitag ist, nahe Monatsende und soooviel Minus-Stunden, schaue ich mir den Rest heute nachmittag mal in aller Ruhe auf Arbeit an.

[GPI]

Ne ich meinte den PureBasic x86-compiler. Ich hab mal ein bischen in den ASM-output reingeschaut. Für Quads wird eine Unterfunktion Mul64 aufgerufen. Klingt für mich logisch, weil der 32Bit-Prozessor wohl keine native Quad-Unterstützung hat. Das gibt ein Problem, da ich nie sicherstellen kann, was die Routine wirklich macht und was für Flags sie setzt.

Also wenn du eine Lösung für Quads hast (für x86 und x64) wäre ich dir sehr dankbar. Aber stress dich nicht unnötig rein, so wichtig ists auch nicht. Ich hab auch mal ein Wunsch in englischen Forum geäußert, spezielle Funktionen anzubieten, die dann das Overflow-Flag zurückliefern können. ( http://www.purebasic.fr/english/viewtop ... =3&t=63469 ). Mal schaun, ob da was kommt. Ab und zu ist es halt schon praktisch festzustellen, ob da ein Fehler passiert ist.

[Helle]

Öha, Quad-Berechnungen mit PB(x86) und dann davon Flags auswerten? Da hätte ich aber kein Vertrauen zu (ohne mir jetzt die PB-Routinen anzuschauen). Was da wohl beim Aufrufer noch richtig ankommt...
Anders bei x64; da geht (halbwegs) sicher das oben gezeigte. Es sei denn, es soll wirklich eigener Code PB ersetzen. Sollte aber natürlich auch wieder PB-konform sein...
Für ADD und SUB könnte man Über-und Unter-Lauf feststellen (Schema wieder wie oben).
Was aber soll der Test fürs Shiften bringen? Das, was dort Sinn ergibt (z.B. Vorzeichen-Wechsel), bezieht sich aufs shiften um eine Stelle, alles andere ist rel. witzlos. Evtl. noch Test, ob Operand Null geworden ist, aber sonst?

Gruß
Helle

[NicTheQuick]

Müsste das nicht ganz einfach so gehen, wie es hier auf stackoverflow beschrieben wurde: multiplication of large numbers, how to catch overflow

[Sven]

Könnte man nicht beide Ausgangswerte / 256 teilen, multiziplieren und schauen, ob das Ergebnis zwischen -32k und 32k (-127 und 127) liegt? Wenn ja, passt das Ergebnis der Ausgangswerte auch in den Quad (Word).