Multiplikation liefert falsches Produkt

[Weizenbaum]

Guten Tag Lazarusforum,
derzeit verwende ich Lazarus v2.0.6 in der 32Bit - Version. Bei einer Multiplikation ist mir ein falsches Ergebnis untergekommen.
110658 * 17279 = 1.912.059.582 <-- Sollte das Ergebnis sein aber....

Code: Alles auswählen

var
  iMul1, iMul2: int32;
  iProdukt: int64;
begin
  iMul1:= 100658;
  iMul2:= 17279;
  iProdukt:= iMul1 * iMul2;  // 1739269582 statt 1.912.059.582
  //0111 0001 1111 0111 1011 0110 1011 1110 = 1.912.059.582
  //0110 0111 1010 1011 0010 0101 1100 1110 = 1.739.269.582

es kommt hierbei 1.739.269.582 raus. Dabei sollte doch ein 64Bit-Integer doch trotz Vorzeichen das korrekte Ergebnis erhalten oder?
Weiß da jemand Rat?

[Sieben]

Guck dir noch mal deine Zahlen an...

[Weizenbaum]

Oh, ok da hab ich im Taschenrechner das falsch eingegeben bei der Gegenkontrolle.
Jetzt steht diesen Algorithmus hoffentlich nichts mehr entgegen, wenn das Ergebnis über 32 Bit hinaus geht.
Ich hatte zuerst befürchtet, der * Operator bräuchte ein 64Bit - Pendant, da ich ja die 32Bit Version von FPC verwende.

Code: Alles auswählen

    {send carry into next iteration}
    iCarry := iProdukt shr DIGIT_BIT; // Um 32 Bit nach rechts.

[Timm Thaler]

Interessant, denn eigentlich verstößt es gegen Regel 3b: https://www.freepascal.org/docs-html/ref/refsu4.html int32*int32 sollte int32 bleiben.

Liegt vielleicht daran, dass der Code auf einem 64-bit Rechner läuft.

[Timm Thaler]

Ach, gerade gesehen, Dein Ergebnis geht nicht über int32 hinaus: -2147483648..2147483647 longint

Und für den AVR liefert der Compiler auf jeden Fall ein int32 zurück.

Iiiiich würd das nochmal überprüfen.

[Weizenbaum]

Hallo Timm,
ja das befürchte ich auch, habe da auch schon eine Lösung bei C++ gefunden über DuckDuckGo, die allerdings sehr sperrig ist und auch nicht richtig zu funktionieren scheint. Wenn diese eine Zeile oben die Bits der 64Bit Variable, die über 32 Bit sind, nicht in die andere Variable schiebt währe das wohl leider vonnöten. Hoffe ich kann das vermeiden und die Multiplikation schreibt auch über 32Bit hinaus in die 64Bit Variable.

Code: Alles auswählen

#define LOW_WORD(x)  (((x) << 16) >> 16)
#define HIGH_WORD(x) ((x) >> 16)
#define ABS(x) (((x) >= 0) ? (x) : -(x))
#define SIGN(x) (((x) >= 0) ? 1 : -1)

#define UNSIGNED_MULT(a, b) \
    (((LOW_WORD(a)  * LOW_WORD(b))  <<  0) + \
     (((int64_t)((LOW_WORD((a)) * HIGH_WORD((b))) + (HIGH_WORD((a)) * LOW_WORD((b))))) << 16) + \
     ((int64_t)(HIGH_WORD((a)) * HIGH_WORD((b))) << 32))

#define MULT(a, b)  (UNSIGNED_MULT(ABS((a)), ABS((b))) * SIGN((a)) * SIGN((b)))

[Sieben]

Warum castest du deine Ausgangswerte nicht einfach auf Int64...? Oder nimmst nicht überhaupt gleich Int64?

[Weizenbaum]

Int64 dient lediglich nur als Hilfsvariable, wenn es einen Überlauf bei einer Int32 Addition oder die Wiederholung von Additionen sprich Multiplikation gibt. Grundsätzlich arbeite ich nur mit 32Bit, darum auch die 32Bit - Version von FPC. Falls das alles so läuft wie es laufen soll, plane ich langfristig diesen Algorithmus auf die SSE-Register oder waren es MMX? die 128 Bit fassen können, auszuweiten. Für einen Überlauf dort währe dann ein 256Bit - Register zuständig, da dies ja über 1 sein kann. Habe jetzt vorhin erst gesehn, daß die oberen 32Bit der 64Bit - Variable den Wert 5 hatten nach einer Multiplikation.
Das ganze sieht derzeit so aus:
pa ist ein Zeiger auf ein Int32-Array-Element.

Code: Alles auswählen

  for n:=0 to a.used-1 do begin
    {compute product and carry sum for this term}
    r := pa^ * bw + u;
    inc(pa);
    {mask off higher bits to get a single digit}
    pc^ := r and MP_MASK;
    ic:= pc^;
    inc(pc);
    ic:= pc^;
    {send carry into next iteration}
    u := r shr DIGIT_BIT;
  end;

  {store final carry [if any]}
  pc^ := mp_digit(u);
  ic:= pc^;

[Timm Thaler]

Ähem:

Code: Alles auswählen

var
  iMul1, iMul2: int32;
  iProdukt: int64;
begin
  iMul1:= 100658;
  iMul2:= 17279;
  iProdukt:= int64(iMul1) * iMul2;

Mehr isses nicht. Man beachte, dass man erst die eine Variable casten muss und dann Multiplizieren.

int64 := uint32 * int32; wird übrigens korrekt mt 64 Bit gerechnet, weil automatische auf int64 erweitert wird.

int64 := int32 * int32 wird mit 64 Bit FPC und auf einer 64er Maschine auch korrekt gerechnet - weil automatisch mit 64 Bit gerechnet wird.

Ja, es ist mitunter verwirrend.

[Winni]

Int64 dient lediglich nur als Hilfsvariable, wenn es einen Überlauf bei einer Int32 Addition oder die Wiederholung von Additionen sprich Multiplikation gibt. Grundsätzlich arbeite ich nur mit 32Bit, darum auch die 32Bit - Version von FPC. Falls das alles so läuft wie es laufen soll, plane ich langfristig diesen Algorithmus auf die SSE-Register oder waren es MMX? die 128 Bit fassen können, auszuweiten. Für einen Überlauf dort währe dann ein 256Bit - Register zuständig, da dies ja über 1 sein kann. Habe jetzt vorhin erst gesehn, daß die oberen 32Bit der 64Bit - Variable den Wert 5 hatten nach einer Multiplikation.

Hi!
Und zu 8-Bit Zeiten hast Du auch nie über 255 hinaus gerechnet?

Das ganze sieht derzeit so aus:
pa ist ein Zeiger auf ein Int32-Array-Element.

Code: Alles auswählen

  for n:=0 to a.used-1 do begin
    {compute product and carry sum for this term}
    r := pa^ * bw + u;
    inc(pa);
    {mask off higher bits to get a single digit}
    pc^ := r and MP_MASK;
    ic:= pc^;
    inc(pc);
    ic:= pc^;
    {send carry into next iteration}
    u := r shr DIGIT_BIT;
  end;

  {store final carry [if any]}
  pc^ := mp_digit(u);
  ic:= pc^;

Du hast echt Talent Dir das Leben schwer zu machen.

Code: Alles auswählen

var lo32, hi32 : integer;
     i64 : Int64;
    .....
    lo32 := lo(i64);
    hi32 := hi(i64);
   ....

Winni

[Weizenbaum]

Damals hab ich einfach Assembler dafür hergenommen, war natürlich sehr sperrig, aber mit der Abfrage des Carryflag ging es. Multiplikationen waren dann einfach nur eine Schleife von Additionen - braucht natürlich mehr Rechenzeit. Heute kann man übrigens noch immer prima Assembler mit einbauen bei FPC, ist nicht so seltsam wie bei minGW C++ der Syntax. Aber natürlich ist FPC in Reinform viel übersichtlicher als C++ oder gar Assembler.

Hier mal eine kleine Kostprobe von Assembler

Code: Alles auswählen

    push ECX; // Hauptzähler sichern
    mov  ECX, DWCount; // DW-Zeiger laden
    mov  EAX, [tmpSum1][ECX]; // Summand 1 in EAX laden
    mov  EBX, [tmpSum2][ECX]; // Summand 2 in EBX laden
    add  ECX, 4;              // Nächstes DW 4x8Byte = 32 Bit
    mov  DWCount, ECX;        // DW-Zeiger für das nächste DoppelWort
    pop  ECX; // Hauptzähler wiederherstellen

    add  EAX, EBX; // Beide Doppel-Wörter addieren
    jc   @@CarryBit; // Bei 32+1 Bit Übertrag auf das nächste DW
    // Register sichern
    push EAX; // Ergebnis sichern
    push ECX; // Hauptzähler sichern
    mov  ECX, MAXDW; // Anzahl der Kopiervorgänge
    // Restliche Bits nachschieben
    cmp  bCarryBit, 0;
    je   @@Schieben;
    // Carry steht eh schon in EAX
    cmp  CX, 1; // Zuvor prüfen, ob die Obergrenze überschritten wurde
    je   @@Error_Overbit; // Wenn ja, Abbruch und Fehlerflag setzen

[Timm Thaler]

Ja nur, warum?

Der Compiler arbeitet schon oft recht optimal.

Ich verwende auch Asm, auf dem AVR. Aber das ist seeehr speziell. Für den PC würd ich mir das nicht antun.

[Winni]

Hmmm

Manche machen ja Assembler auch als Hobby ...

Aber wenn Du was optimieren möchtest:
Mach ein einfaches Programm Deines Problems in *Pascal*.

Irgendein Zauber-Parameter von fpc verhindert das Löschen des Assembler-Files.
Nun kannst Du kontrollieren, ob alles gut ist oder ob Du noch ne Idee hast.

Deine Idee spart bestimmt ein paar µsec .

Winni

[Weizenbaum]

Guten Morgen,
ich danke für die Antworten. Momentan läuft es wieder so, wie es soll. Wegen Assembler, also da bin ich nicht allzusehr abgeneigt, es gibt da schon bei mir hin und wieder den Drang, mich damit zu beschäftigen, wenn ich könnte würde ich sogar direkt im Addierwerk der CPU was rumtüfteln. Da kommt dann wieder die Begeisterung fürs Detail auf, schätze einen Schweizer Uhrmacher geht es da genauso. Andererseits kann ich auch die Leute verstehen, die bei Assembler genervt abwinken.