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

Zur Vorstellung von Komponenten und Units für Lazarus

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

Beitragvon Euklid » 17. Dez 2008, 12:54 Re: GNURZ - Arithmetik-Unit für große Zahlen

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
Euklid
 
Beiträge: 2760
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon mschnell » 17. Dez 2008, 14:52 Re: GNURZ - Arithmetik-Unit für große Zahlen

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 17. Dez 2008, 15:46, insgesamt 1-mal geändert.
mschnell
 
Beiträge: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mschnell » 17. Dez 2008, 15:01 Re: GNURZ - Arithmetik-Unit für große Zahlen

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
mschnell
 
Beiträge: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon Euklid » 17. Dez 2008, 20:56 Re: GNURZ - Arithmetik-Unit für große Zahlen

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
 
Beiträge: 2760
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon Euklid » 18. Dez 2008, 01:35 Re: GNURZ - Arithmetik-Unit für große Zahlen

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
Euklid
 
Beiträge: 2760
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon mschnell » 18. Dez 2008, 09:45 Re: GNURZ - Arithmetik-Unit für große Zahlen

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: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mschnell » 18. Dez 2008, 12:30 Re: GNURZ - Arithmetik-Unit für große Zahlen

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 18. Dez 2008, 20:31, insgesamt 1-mal geändert.
mschnell
 
Beiträge: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon Euklid » 18. Dez 2008, 17:54 Re: GNURZ - Arithmetik-Unit für große Zahlen

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.
Euklid
 
Beiträge: 2760
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon af0815 » 19. Dez 2008, 10:31 Re: GNURZ - Arithmetik-Unit für große Zahlen

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).
af0815
 
Beiträge: 3605
Registriert: 7. Jan 2007, 10:20
Wohnort: Niederösterreich
OS, Lazarus, FPC: FPC 3.2 Lazarus 2.0 per fpcupdeluxe | 
CPU-Target: 32Bit (64Bit)
Nach oben

Beitragvon mschnell » 19. Dez 2008, 11:21 Re: GNURZ - Arithmetik-Unit für große Zahlen

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: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mschnell » 19. Dez 2008, 13:24 Re: GNURZ - Arithmetik-Unit für große Zahlen

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;
mschnell
 
Beiträge: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon Euklid » 21. Dez 2008, 15:24 Re: GNURZ - Arithmetik-Unit für große Zahlen

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.
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Euklid
 
Beiträge: 2760
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon mschnell » 22. Dez 2008, 00:01 Re: GNURZ - Arithmetik-Unit für große Zahlen

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: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mschnell » 22. Dez 2008, 00:03 Re: GNURZ - Arithmetik-Unit für große Zahlen

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
mschnell
 
Beiträge: 3287
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon Euklid » 22. Dez 2008, 00:42 Re: GNURZ - Arithmetik-Unit für große Zahlen

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.
Euklid
 
Beiträge: 2760
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

» Weitere Beiträge siehe nächste Seite »
VorherigeNächste

Zurück zu Units/Komponenten



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron
porpoises-institution
accuracy-worried