GNURZ - Arithmetik-Unit für große Zahlen

[af0815]

Code: Alles auswählen

function GNZMul(p1, p2: GNZType): GNZType;
var
  l, i:  Integer;
begin
  l := length(p1) + length(p2);  <--------
  setlength(Result, l);    <------
  for i := 0 to l - 1 do begin
    Result[i] := 0;       
  end;
  for i := 0 to l - 1 do begin
    GNZMulInternal(Result[i], p1[0], p2[i], l);
  end;
end;

Da die sich ergebende Länge bei einer Multiplikation, maximal die Summe der Längen egeben kann, sollte es so korrigiert werden.

[mschnell]

Wie wäre es wenn man die größte Länge von beiden: p1, p2 nimmt und nicht nur von p1

Ich denke, die internen Routinen sollten schon "richtig" vom Code aufgerufen werden.

aber da wird dann ja die zahl : p1[0] = 4; p2[0] = 5; nach Result[0] geschrieben, also ist ja dann Result[0] = 0 und die 2( 20 ) wo kommt die hin?

Ich verstehe überhaupt nicht, was Du meinst.

Result[0] ist ein 32-Bit Wert, da passt 20 doch problemlos 'rein. Wen das Ergebnis einer "Stelle" größer als $FFFFFFFF ist, kommt die High-Teil in die nächste "Stelle" (Result[1]). Oder was meinst Du ?

-Michael

[mschnell]

Da die sich ergebende Länge bei einer Multiplikation, maximal die Summe der Längen ergeben kann, sollte es so korrigiert werden.

Halte ich für keine so gute Idee. nach "Aussen" wird immer die Karazuba-Multiplikation exportiert. Innen teilt sie die Arbeit (wenn ich das richtig sehe) in Multiplikationen mit gleich langen Faktoren auf.

Ich habe den Code nicht mit unterschiedlich langen Faktoren getestet. Ich sehe allerdings nicht, warum das nicht gehen sollte (Der ASM-Teil merkt davon ja nix).

Der obige Code ist allerdings ziemlich falsch.

So könnte es gehen:

Code: Alles auswählen

function GNZMul(p1, p2: GNZType): GNZType;
var
  l1, l2, i:  Integer;
begin
  l1 := length(p1);
  l2 := length(p2);
  setlength(Result, l1+l2);
  for i := 0 to l1+l2-1 do begin
    Result[i] := 0;
  end;
  for i := 0 to l2 - 1 do begin
    GNZMulInternal(Result[i], p1[0], p2[i], l1);
  end;
end;

-Michael

[EugenE]

Result[0] ist ein 32-Bit Wert, da passt 20 doch problemlos 'rein. Wen das Ergebnis einer "Stelle" größer als $FFFFFFFF ist, kommt die High-Teil in die nächste "Stelle" (Result[1]). Oder was meinst Du ?

-Michael

Ok das wollte ich nur wissen , dachte der "High"-Teil würde abgeschnitten oder so

[mschnell]

Ok das wollte ich nur wissen , dachte der "High"-Teil würde abgeschnitten oder so

Ein paar interessante Fälle habe ich natürlich getestet

-Michael

[Euklid]

Hier ein Vorschlag für die Primitiv-Multiplikation.

Hervorragend! Die wird sofort mitintegriert...

... mal eine Frage: Kann es sein, dass die Zeilen 4,28 und 35 gestrichen werden können, ohne dass Schlimmeres befürchtet werden muss?

EDIT:
Sicher, dass die ASM-Multiplikations-Routine für Produkte, die größer sind als 4294836225, richtig multipliziert? Habe sie eben implementiert und erhalte 100000*100000=5705032704, was unmöglich richtig sein kann.

[mschnell]

... mal eine Frage: Kann es sein, dass die Zeilen 4,28 und 35 gestrichen werden können, ohne dass Schlimmeres befürchtet werden muss?

Gut beobachtet ! 4 wird gebraucht, 28 und 35 aber wohl nicht.

Sicher, dass die ASM-Multiplikations-Routine für Produkte, die größer sind als 4294836225, richtig multipliziert? Habe sie eben implementiert und erhalte 100000*100000=5705032704, was unmöglich richtig sein kann.

Sicher bin ich da überhaupt nicht. Ich habe bisher nur einige interessante Fälle getestet.
Checke ich morgen.
-Michael

[mschnell]

Habe sie eben implementiert und erhalte 100000*100000=5705032704, was unmöglich richtig sein kann.

Da hast Du irgendwie falsch getestet.
Bei mir kommt bei Deinem Beispiel das richtige heraus. Hier der Test-Code für 100000*100000 (Das ist leicht zu testen, weil das Ergebnis in ein int64 passt und man deshalb keine Umwandling nach dezimal schreiben muss.

-Michael

Code: Alles auswählen

function GNZToIn64(g:GNZType; var i64: Int64): Integer;
var
  i: Integer;
  h64, l64: Int64;
begin
  for i := 2 to Length(g) - 1 do begin
    if g[i] <> 0 then begin
      Result := -1;
      exit;
    end;
  end;
  l64 := g[0];
  h64 := g[1];
  h64 := h64 shl 32;
  i64 := h64 + l64;
  Result := 0;
end;
 
function In64ToGNZ(i64: Int64): GNZType;
var
  i: Integer;
  h64, l64: Int64;
begin
  SetLength(Result, 2);
  for i := 2 to Length(Result) - 1 do begin
    Result[i] := 0;
  end;
  h64 := i64 shr 32;
  h64 := h64 and $FFFFFFFF;
  l64 := i64 and $FFFFFFFF;
  Result[0] := l64;
  Result[1] := h64;
end;
 
function GNZToHex(g: GNZType): String;
var
  i, l1: Integer;
begin
  Result := '';
  l1 := Length(g) -1;
  for I := 0 to l1 do begin
    Result := Result + IntToHex(g[l1-i], 8);
  end;
end;
 
procedure TForm44.Button2Click(Sender: TObject);
var
  ai, bi, ci: Int64;
  ag, bg, cg: GNZType;
  r : Integer;
begin
   ai := 100000;
   bi := 100000;
   ci := ai*bi;
   Memo1.Lines.Add('                ' + IntToHex(ci, 16) + ' = ' + inttostr(ci));
 
   ag := In64ToGNZ(ai);
   bg := In64ToGNZ(bi);
   cg := GNZMul(ag, bg);
   r  := GNZToIn64(cg, ci);
   Memo1.Lines.Add(GNZToHex(cg));
   if r = 0 then begin
     Memo1.Lines.Add('                ' + IntToHex(ci, 16) + ' = ' + inttostr(ci));   
   end;
end;
 
 
Ergebnis: 
                00000002540BE400 = 10000000000
000000000000000000000002540BE400
                00000002540BE400 = 10000000000

[Euklid]

Da hast Du irgendwie falsch getestet.

Oh - dann muss ich den Fehler wohl in meiner Implementierung suchen. Srry für den Aufwand, den ich hier gemacht habe. Sollte ich den Fehler in der Implementierung nicht finden, werde ich den Code hier am Besten schonmal vorab reinstellen.
Im Übrigen ist die native Multiplikation sehr vielversprechend. Mit ihr lässt sich die Geschwindigkeit ganz sicher mehr als verdoppeln. Zudem werde ich mich um Optimierungen des Karazuba-Algorithmus bemühen, mal schauen, wo wir dann hinsichtlich der Ausführungszeit landen.

Viele Grüße, Euklid

[mschnell]

Srry für den Aufwand, den ich hier gemacht habe.

Null Problemo !

-Michael

[indianer-frank]

Code: Alles auswählen

function GNZToIn64(g:GNZType; var i64: Int64): Integer;
var
  i: Integer;
  h64, l64: Int64;
begin
  for i := 2 to Length(g) - 1 do begin
    if g[i] <> 0 then begin
      Result := -1;
      exit;
    end;
  end;
  l64 := g[0];
  h64 := g[1];
  h64 := h64 shl 32;
  i64 := h64 + l64;
  Result := 0;
end;

Mir ist nicht klar, warum Du int64 nimmst und nicht uint64. Bei int64 gibt's doch zB für g[0] im Bereich $80000000 ... $FFFFFFFF entweder einen Rangecheck-Fehler oder es wird mit negativen l64 gerechnet und das Ergebnis ist falsch!?

Frank

Edit: Hab gerade gesehen, daß es wohl bei g[0] in dem Range keinen Fehler gibt, nur ev. Warnung "mixing signed/unsigned". Dafür kann Result allerdings negativ werden bzw. Fehlermeldung, wenn g[1] in dem Bereicht ist.

[mschnell]

Mir ist nicht klar, warum Du int64 nimmst und nicht uint64.

Hast Du recht ! mit uint64 kann man sich die "and $FFFFFFFF" - Geschichten sparen. Für diese Testfunktion hab ich mir da weiter keine Gedanken gemacht. Wenn man es in die Library einbauen will, sollte man natürlich uint64 nehmen und schauen was man optimieren kann.

(da g[i] ein Cardinal (vorzeichenloses 32 Bit) ist, kann es nur ein positives int64 werden, wenn der Compiler korrekt arbeitet.)

-Michael

[Euklid]

Die GNURZ verwendet generell dword. Werde die Funktionen mal dafür umschreiben.

[mschnell]

Die GNURZ verwendet generell dword. Werde die Funktionen mal dafür umschreiben.

Diese (Test-) Funktionen Konvertieren 64 Bit werte und GNZ mit 32 Bit Basis-Typ. Das ist doch gerade der Trick, mit dem man die GNZ-Funktionen testen kann !

-Michael

[Euklid]

Hallo,

ich stehe offenbar auf dem Schlauch und verstehe nicht, warum meine Implementierung so einen Humbuck macht. In völliger Analogie zu deiner (mschnell) GNZPrimitivMul habe ich die GNZMulInternal wie folgt eingebaut:

Code: Alles auswählen

 
//...
//a=1. Faktor, b=2. Faktor, vom Typ GNZTyp
var n,aAnz,bAnz: dword;
    Erg: GNZTyp;
begin
  aAnz:=length(a); bAnz:=length(b);
  setlength(Erg,aAnz+bAnz);
  for n:=0 to aAnz+bAnz-1 do Erg[n]:=0;
  for n:=0 to bAnz-1 do GNZMulInternal(Erg[n], a[0], b[n], aAnz);
  If Erg[aAnz+bAnz-1]=0 then setlength(Erg,aAnz+bAnz-1);
  showmessage(GNZTypToStr(Erg)+'='+GNZTypToStr(a)+'*'+GNZTypToStr(b));
//...
 

Ich verstehe nicht, warum mir Showmessage "5705032704=100000*100000" ausgibt. Gerade für a=b wird doch quasi der selbe Code ausgeführt?!?

Viele Grüße, Euklid