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

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

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

Beitrag von Euklid »

mschnell hat geschrieben:Ich erweitere gleich 'mal die "Add" und "Sub" ASM-Prozeduren zu Funktionen, die den Carry vom obersten Wort der Langzahl als Funktionswert zurückgeben. Dann kann Der Pascal-Teil damit entsprechend verfahren.


Ok, danke. Werde die neuen Routinen gleich in den Code einfügen.

Es ist aber nicht unbedingt eine gute Idee bei einer längeren Rechnung mit Langzahlen variabler Länge zu arbeiten. Darüber hatten wir schon gesprochen.
In jedem Fall sollte es eine Variante der (Pascal) "Add" und "Sub"-Funktionen geben, die nicht das Ergebnis zwingend ein Wort größer als die Summenden macht, oder dynamisch (also mit Umkopieren) das Ergebnis je nach Wert verlängert oder verkürzt.


Wir hatten letztens darüber diskutiert, dass ein Array länger zu machen wesentlich umständlicher ist als es kürzer zu machen, da es u.U. beim Verlängern an einen anderen Speicherort kopiert werden muss.
Folglich werde ich bei der Addition das Ergebnis-Array um 1 zu lang einrichten (dauert selbe Zeit) und nachträglich um 1 verkürzen (geht schnell, da nix umkopiert werden muss), sollte es nicht zum Überschlag kommen. Dann dürften die zeitlichen Verluste minimal sein.

Auch die Arithmethik-Unit, auf die dein obiger Link verweist, verwendet dynamische Arrays, wenn ich das richtig durchschaut habe.

Benutzt Deine Langzahlen zu Dezimal-String Funktion die GNZ-Arithmetik-Funktionen ?


Ja, benutzt sie. Das muss aber garnicht schneller sein, da deine eben gepostete Umwandlungsroutine auf sehr schnelle Befehle zugreift.

Noch eine Bemerkung zum Konzept der GNURZ: Hatte sie ursprünglich so programmiert, dass sie sehr ausfallsicher, wenig fehleranfällig und leicht zu warten ist (defensive Programmierung). Ich bin mir sicher, dass durch die Integration deiner ASM-Multiplikation ein _ganz erheblicher_ Geschwindigkeitsvorteil rausgeholt werden kann, nicht nur weil so die Fähigkeiten des Prozessors ideal ausgenutzt werden können, sonder auch weil dessen Struktur auch eine effiziente Optimierung das Karazuba-Algorithmus erlaubt. Ich schätze, dass sich die Geschwindigkeit mindestens verfünffacht. Benchmarkergebnisse werden hier gepostet, sobald ich die Optimierungen abgeschlossen habe.

Viele Grüße, Euklid

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Euklid hat geschrieben:Folglich werde ich bei der Addition das Ergebnis-Array um 1 zu lang einrichten (dauert selbe Zeit) und nachträglich um 1 verkürzen (geht schnell, da nix umkopiert werden muss), sollte es nicht zum Überschlag kommen. Dann dürften die zeitlichen Verluste minimal sein.

Stimmt zwar, resultiert aber in einer fürchterlichen Heap-Fragmentierung. Bei fast jeder Addition entsteht durch die Verkürzung ein Loch von 4 Byte im Heap-Speicherbereich, das nicht wieder verwendet werden kann, (bis ein angrenzender größerer Bereich gelöscht wird und die Lücken dann vereinigt werden.

Somit ist das keine wirklich gute Methode und sollte nur dann verwendet werden, wenn im Hauptprogramm die verwendete Zahlengröße wirklich nicht von vorne herein festlegbar ist.

"Von Außen" sollten also beide Möglichkeiten verwendbar sein.

-Michael
Zuletzt geändert von mschnell am Mi 17. Dez 2008, 15:46, insgesamt 1-mal geändert.

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Euklid hat geschrieben:...weil dessen Struktur auch eine effiziente Optimierung das Karazuba-Algorithmus erlaubt.

Brauchst Du auch die AddAdd und SubSub Routinen als Funktionen, die den letzten Übertrag zurückgeben ? (Achtung: der Übertrag kann da 2 bzw -2 sein.) Kann ich gerne machen.

Übrigens: Dezimal-String nach Langzahl müsste in ähnlicher weise wie die GNZToStr realisierbar sein.

-Michael

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

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

Beitrag von Euklid »

Deine ASM-Addition klappt wunderbar. Die Multiplikation auch. Werde mich jetzt an den Karazuba-Algo begeben. Sage dir dann später noch Bescheid bzgl addadd und subsub...

Edit: Werde die Karazuba-Methode nochmal komplett neu schreiben. Die lässt sich nicht so leicht umwandeln.

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

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

Beitrag von Euklid »

Abend!

Habe eben die ASM-Multiplikation und die ASM-Subtraktion von mschnell eingefügt. Habe ebenfalls versucht, den Karazuba-Algo zu optimieren. Das hat sich als sehr umfangreiche Aufgabe erwiesen, sodass ich diese Optimierung abgebrochen habe und auf unbestimmte Zeit in die Zukunft verschiebe.

Offenbar zeigt aber schon die Optimierung der Primitiv-Multiplikation durchschlagende Wirkung, wie folgende Benchmark-Ergebnisse zeigen. Gestoppt wurde die Zeit, die benötigt wird, um 50000 mal 400-stellige Zahlen miteinander zu multiplizieren:

Herkömmliches GNZmul: 26,7 sek
ASM-optimiertes GNZmul: 1,3 sek

Würde schätzen, dass sich für besonders lange Zahlen ein eventuell ähnlich hoher Faktor durch Optimierung des Karazuba-Algorithmus ergibt.

Damit ist die 32bit-ASM-Optimierung abgeschlossen. Die neue GNURZ-Unit wird von mir morgen veröffentlicht. Ich werde sie parallel zur nicht-asm-opt. GNURZ anbieten, welche wahrscheinlich fast bugfrei ist.

Dank nochmal an mschnell für den schnellen ASM-Code!

Viele Grüße, Euklid

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Euklid hat geschrieben:Würde schätzen, dass sich für besonders lange Zahlen ein eventuell ähnlich hoher Faktor durch Optimierung des Karazuba-Algorithmus ergibt.

Zunächst kannst Du ja mal ein paar Messungen machen und die Karazuba-Grenze an die neuen Gegebenheiten anpassen. Ich fände es interessant die optimale Karazuba-Grenze mit und ohne ASM zu wissen.

-Michael

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Euklid hat geschrieben:Folglich werde ich bei der Addition das Ergebnis-Array um 1 zu lang einrichten (dauert selbe Zeit) und nachträglich um 1 verkürzen (geht schnell, da nix umkopiert werden muss), sollte es nicht zum Überschlag kommen. Dann dürften die zeitlichen Verluste minimal sein.


Ich habe mir darüber nochmal Gedanken gemacht. Ich glaube, es wäre ideal, das Array nur dann um eines größer einzurichten, wenn nach einem einfachen Test (der obersten 31 Bit), der schnell in Pascal implementiert werden kann tatsächlich ein Übertrag auftreten kann und es, wenn er doch nicht auftritt wieder zu kürzen.

Setlength macht sogar wilde Sachen, wenn die Länge garnicht geändert werden muss, also lieber vermeiden !

Hier ein Vorschlag für den entsprechenden

Code: Alles auswählen

function GNZAdd(s1, s2: GNZType): GNZType;
var
  l: Integer;
  c: GNZBaseType;
begin
  l := length(s1);
  if (((s1[l-1] shr 1) + (s2[l-1] shr 1) + 1) > (High(GNZBaseType) shr 1) ) then begin
    setlength(Result, l+1);
    c := GNZAddInternal(Result[0], s1[0], s2[0], length(s1));
    if c<>0 then begin
      Result[High(Result)] := c;
     end else begin
      setlength(Result, l);
    end;
   end else begin
    setlength(Result, l);
    GNZAddInternal(Result[0], s1[0], s2[0], length(s1));
  end;
end;
-Michael
Zuletzt geändert von mschnell am Do 18. Dez 2008, 20:31, insgesamt 1-mal geändert.

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

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

Beitrag von Euklid »

mschnell hat geschrieben:Zunächst kannst Du ja mal ein paar Messungen machen und die Karazuba-Grenze an die neuen Gegebenheiten anpassen. Ich fände es interessant die optimale Karazuba-Grenze mit und ohne ASM zu wissen.


Die Karazuba-Grenze hat sich kaum verändert (im Rahmen der Messungenauigkeit). Sie profitiert aber auch ohne Optimierung von der Primitiv-Multiplikation, da sie letztlich darauf basiert. Ich werde gleich den Quellcode veröffentlichen, dann wird das leicher einsehbar.

EDIT: Sie wurde eben dem ersten Beitrag angefügt.

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6198
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

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

Beitrag von af0815 »

Euklid hat geschrieben: ...Sie profitiert aber auch ohne Optimierung von der Primitiv-Multiplikation, da sie letztlich darauf basiert. Ich werde gleich den Quellcode veröffentlichen, dann wird das leicher einsehbar ...


Kommt gnurz_asm auch ins die gnurz.pas hinein ? Wäre doch sinnvoll, wenn man mittels bedingter Compilerung sich aussuchen kann, wie es kompiliert wird.

SVN ist auf aktuellen Stand.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

af0815 hat geschrieben:Wäre doch sinnvoll, wenn man mittels bedingter Compilerung sich aussuchen kann, wie es kompiliert wird.
Das halte ich auch für sehr sinnvoll !

Ich würde das machen, indem sie übergeordneten Funktionen gleich bleiben und Pascal-Varianten der "Internal" Funktionen bereitgestellt werden.

Außerdem muss ASM natürlich abgeschaltet werden, wenn die Prozessor-Plattform, für die kompiliert wird, nicht unterstützt ist. (Momentan haben wir ja nur X86_32, X86_64 ist geplant.)

Bei "High-Endian" Prozessoren (PPC) würde ich die Darstellung der langen Zahlen auch entsprechend der Hardware umgekehrt als bei X86 auslegen. Das erfordert natürlich bedingte Kompilierung auch innerhalb diverser Pascal-Funktionen.

-Michael

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Mein Sohn Julian, der hier auch mitliest, hat die kompatible StrToGNZ-Funktion geschrieben;

Code: Alles auswählen

const
  BaseLength = sizeof(GNZBaseType) * 8;
 
function StrToGNZ(s: string): GNZType;
var
  l: integer;
  i,i2: integer;
  c: GNZBaseType;
 
  function StrDiv2(var s: string): GNZBaseType;
  var
    i: integer;
    ch: byte;
  begin
    result:= 0;
    for i := 1 to length(s) do begin
      ch:= byte(s[i]);
      ch:= ch - $30;
      ch:= ch + (result * 10);   
      result:= ch and 1;
      ch:= ch shr 1;
      s[i]:= char(ch + $30);
    end;
    if s[1] = '0' then begin
      s:= copy(s, 2, high(integer));
    end;
    result:= result shl (BaseLength -1);
  end;
 
begin
  i2:= 0 ;
  l:= length(s);
  l:= ((l + 2) div 3) * 10; //just in case
  l:= (l + (BaseLength -1)) div (BaseLength); //just in case
  setlength(result, l);
  for I := low(result) to high(result) do begin
    result[i]:= 0;
  end;
  i:= 0;
  while s <> '' do begin
    c:= StrDiv2(s);
    i2:= i div (BaseLength);     
    result[i2]:= (result[i2] shr 1) or c;
    inc(i);
  end;
  i:= i mod BaseLength;
  if i > 0 then begin
    result[i2]:= result[i2] shr ((Baselength) - (i mod BaseLength));
  end;
  while result[high(result)] = 0  do begin
    l:= length(result);
    SetLength(Result, l-1);
  end;
end;

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

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

Beitrag von Euklid »

mschnell hat geschrieben:Mein Sohn Julian, der hier auch mitliest, hat die kompatible StrToGNZ-Funktion geschrieben;


Danke Julian für die Unterstützung!
Im Moment bekomme ich noch eine Range ckeck error (RunError 201) in Zeile 27.
Verstehe ich es richtig, dass Baselength der GNZ_GlobZahlenbasis entspricht? Wenn nicht, liegt hier ev. der Fehler. Ich habe die Gnurz-Unit mit deiner StrToGNZ einmal angehängt, damit der Fehler reproduziert werden kann (habe sie in StrToGNZTyp umbenannt).

af0815 hat geschrieben:Kommt gnurz_asm auch ins die gnurz.pas hinein ? Wäre doch sinnvoll, wenn man mittels bedingter Compilerung sich aussuchen kann, wie es kompiliert wird.


Dies wird in der gnurz_asm bereits so geregelt. Sie enthält also umgekehrt die nicht optimierte gnurz - für den Fall, dass kein x86 vorliegt.

Die ursprüngliche gnurz ist relativ gut bugbereinigt, zwar langsam aber dafür recht flexibel handhabbar. Daher möchte ich sie parallel zur gnurz_asm fortführen. Für deine LazInfos ist es wahrscheinlich ratsam, die schnelle Version (gnurz_asm) zu integrieren.


mschnell hat geschrieben:Das erfordert natürlich bedingte Kompilierung auch innerhalb diverser Pascal-Funktionen.

Zur Zeit wird das so geregelt: Jede Funktion gibt es in mehrfacher Ausführung - jenachdem, für welches System kompiliert wird.

Viele Grüße, Euklid

PS: Sollten mittel- oder langfristig sich tatsächlich mehrere Personen an der Gnurz-Arithmetikunit beteiligen, ist die Nutzung von SVN vorteilhaft. In diesem Fall würde ich gerne auf das Angebot von af0815 eingehen. Äußert Euch mal dazu. Dann würden die Optimierungen nicht über diesen Thread des Forums laufen müssen, sondern sie könnten direkt eingebaut werden.
Dateianhänge
gnurz.pas
Hier die GNURZ mit der nicht funktionierenden StrToGNZTyp-Funktion.
(72.18 KiB) 51-mal heruntergeladen

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Euklid hat geschrieben:Im Moment bekomme ich noch eine Range ckeck error (RunError 201) in Zeile 27.
Hmmm. Hier klappt's. Mit welchem String klappt's bei Dir nicht ?
Euklid hat geschrieben:Verstehe ich es richtig, dass Baselength der GNZ_GlobZahlenbasis entspricht?
Baselength ist die Anzahl der Bits in einem Wort des Basis-Types (32 Bei DWORD, 64 (demnächst) bei UINT64). Eine solche Konstante sollten wir Überall verwenden, wo diese Zahl benötigt wird.
-Michael

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Euklid hat geschrieben:Nutzung von SVN
Wenn das SNV mit HTTP zugreifbar ist (wie z.B. GIT) geht das. Ansonsten scheitert es an unserem Firewall.
-Michael

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

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

Beitrag von Euklid »

mschnell hat geschrieben:
Euklid hat geschrieben:Verstehe ich es richtig, dass Baselength der GNZ_GlobZahlenbasis entspricht?
Baselength ist die Anzahl der Bits in einem Wort des Basis-Types (32 Bei DWORD, 64 (demnächst) bei UINT64). Eine solche Konstante sollten wir Überall verwenden, wo diese Zahl benötigt wird.


Ok, dann hatte ich es nicht richtig verstanden, sorry. Jetzt funktioniert es jedenfalls.

Habe eben mal Geschwindigkeitsmessungen durchgeführt. Julians Code erschien mir auf den ersten Blick besser optimiert und direkter. Leider bringt er aber keinen Geschwindigkeitsvorteil. Trotzdem danke für die gemachte Arbeit!

Wenn das SNV mit HTTP zugreifbar ist (wie z.B. GIT) geht das. Ansonsten scheitert es an unserem Firewall.


Hier kann uns vielleicht der af0815 mal genauer informieren. Wenn ich ihn richtig verstanden habe, verwendet er für das SVN SourceForge.

Antworten