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 »

EugenE hat geschrieben:ich habe noch nicht mit dem Testen und dem Operatoren-Overload angefangen jedoch vllt kannst du mir helfen ^^.


Sorry, kenne mich da überhaupt nicht aus.

Kann man die GNZPotenzMod irgendwie verschnellern? ( ich weiß, machs selber xD , aber kp wie^^)

Also mein Rechner ( Dual Core 1.73GHz, mit 2GB Ram) braucht ca 3-5 Minuten fuer diese Rechnung:


Bist du sicher, dass du alle Zahlen gepostet hast? Oder hast du die GNURZ modifiziert?

Mein Rechner (bei 1,0 GHz, also langsamer als deiner) braucht nur 10 Sekunden.


Gibt es da vielleicht irgendwelche Mathematische Lösungen um solche Formeln unter ner Sekunde zu rechnen?

Habe gerade testweise versucht, den Wert mit dem Computer-Algebra-System Maxima zu berechnen. Bekam aber einen "overflow during multiplication of large numbers".

Wie gesagt, die GNURZ lässt sich noch weiter optimieren, wenn man Zeit investieren will. Aber ich denke 10 Sekunden auf einem nur 1-GHZ-PC sind in Ordnung?

EugenE
Beiträge: 440
Registriert: So 10. Dez 2006, 14:59
OS, Lazarus, FPC: MacOSX Lion 10.7 (L 0.9.31 FPC 2.7.1)
CPU-Target: 64Bit
Kontaktdaten:

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

Beitrag von EugenE »

hm ne leider nicht ^^ will ja nicht ne stunde warten bis der Partner das Passwort entschlüsselt um die nachricht zu entschlüsseln, jez auf RSA bezogen ^^ naja ich werde mal noch nen paar andere arithmetic units testen vllt sind diese um paar sekunden schneller ( jede Sekunde zählt ^^ ), jedoch funktioniert GNURZ top muss ich schon sagen^^

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 »

EugenE hat geschrieben:hm ne leider nicht ^^ will ja nicht ne stunde warten bis der Partner das Passwort entschlüsselt um die nachricht zu entschlüsseln, jez auf RSA bezogen ^^

Wie gesagt: Deine Schätzung von 3-5 Minuten kann unmöglich stimmen.

naja ich werde mal noch nen paar andere arithmetic units testen vllt sind diese um paar sekunden schneller ( jede Sekunde zählt ^^ )

Ok, es gibt FreePascal-intern noch die BCDUnit, nach der du mal gucken kannst. Bevor du jedoch eine Nicht-Pascal-Unit einbindest, empfehle ich dir gleich die Verwendung von GnuPG - ist wohl das Einfachste.

Viele Grüße, Euklid

EugenE
Beiträge: 440
Registriert: So 10. Dez 2006, 14:59
OS, Lazarus, FPC: MacOSX Lion 10.7 (L 0.9.31 FPC 2.7.1)
CPU-Target: 64Bit
Kontaktdaten:

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

Beitrag von EugenE »

oh sry sollten 3-5 sekunden werden und nicht minuten

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 »

EugenE hat geschrieben:oh sry sollten 3-5 sekunden werden und nicht minuten


Ok, dann der Hinweis: Das Entschlüsseln des Passworts mittels GNURZ für RSA dauert nicht viel länger als genau diese 3 Sekunden - und keine Stunden. Schließlich kannst du in die Basis den kompletten Schlüssel für die symmentrische Verschlüsselung unterbringen.

Wenn du erwägst die BCDUnit einzuspannen, würden mich die Ergebnisse interessieren.

Viele Grüße, Euklid

EugenE
Beiträge: 440
Registriert: So 10. Dez 2006, 14:59
OS, Lazarus, FPC: MacOSX Lion 10.7 (L 0.9.31 FPC 2.7.1)
CPU-Target: 64Bit
Kontaktdaten:

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

Beitrag von EugenE »

ja eben, auch wenn ich nur den Schlüssel für ein Symmetrisches Verfahren mit RSA verschlüsseln würde, würde es trotzdem jedes mal länger als 10 sec oder mehr (min. 3sec fuer 2buchstaben ( im original text ) ) dauern

versuche es jetzt mit der MPArith-Unit http://home.netsurf.de/wolfgang.ehrhard ... ml#mparith jedoch irgendwie etwas kompliziert ^^ naja werd dann wohl mehrere solcher Arithmetic-Units testen welche am schnellsten das macht^^

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 »

EugenE hat geschrieben:versuche es jetzt mit der MPArith-Unit http://home.netsurf.de/wolfgang.ehrhard ... ml#mparith jedoch irgendwie etwas kompliziert ^^ naja werd dann wohl mehrere solcher Arithmetic-Units testen welche am schnellsten das macht^^


Danke für den Link - die kannte ich selbst noch nicht.

Die Unit ist besser optimiert als meine GNURZ. Die Optimierungen liegen aber nicht im Bereich der Algorithmen, hier ist die GNURZ auf dem gleichen Stand.
Die Hauptoptimierung liegt wohl darin, dass der Mensch nicht die Pascal-Array-Operationen verwendet, sondern optimiert mit Pointern hantiert und der Datentyp maßgeblich aus einem packed array besteht. Zudem wurde zum Teil auf Assembler gesetzt. In der Summe sind die Routinen schneller.

Es ist unwahrscheinlich, dass ähnliche Optimierungen für GNURZ umgesetzt werden, da diese sehr fehleranfällig und daher wartungsaufwendig sind, wofür ich nicht die Zeit habe. Zudem wird wegen der Verwendung von x86-Assembler die Arithmetik-Unit möglicherweise auf x86-Maschienen eingeschränkt.

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: Zudem wird wegen der Verwendung von x86-Assembler die Arithmetik-Unit möglicherweise auf x86-Maschienen eingeschränkt.

Dann baue doch Compiler-Optionen ein, die bei Architekturen, für die sie bereits geschrieben sind, die entsprechenden ASM-Teile einbauen und für solchem wo das noch keiner gemacht hat, den Pascal-Code verwendet.

Ich glaube, dass Du mit 64-Bit Assembler Arithmetik auf einer 64 Bit Maschine doppelt so schnell bist, wie mit Pascal-Code.

-Mxihael

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 glaube, dass Du mit 64-Bit Assembler Arithmetik auf einer 64 Bit Maschine doppelt so schnell bist, wie mit Pascal-Code.

Assembler würde sich besonders in zeitkritischen Bereichen lohnen, da stimme ich dir zu. Wenn du möchtest, kannst du versuchen es umzusetzen?

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 »

Ich hab's so was zwar lange nicht mehr (im Zusammenhang mit Pascal und für PC) gemacht, aber ich kann ja 'mal schauen.

Poste doch 'mal eine kurze Routine, (z.B. Multiplikation), bei der sich möglicherweise eine ASM Optimierung lohnen könnte.

-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 »

EugenE hat geschrieben:(min. 3sec fuer 2buchstaben ( im original text ) ) ^


Wiso verschlüsselst du nicht gleich mehr als 2 Buchstaben Klartext auf einmal? Es sollte möglich sein, so viele Bits auf einmal zu verschlüsseln, wie N-1 an Speicherplatz belegt. Egal welche Arithmetik-Unit du verwendest - die Dauer der Berechnung dürfte sich auf einen Bruchteil verringern.

mschnell hat geschrieben:Poste doch 'mal eine kurze Routine, (z.B. Multiplikation), bei der sich möglicherweise eine ASM Optimierung lohnen könnte.


Die Multiplikation ist ein ganz schöner brocken, da sie diverse Fallunterscheidungen macht. Diese Routine ist wesentlich kürzer und Ergebnisse hinsichtlich der Geschwindigkeit könnten daran schon gesehen werden (glaube ich):

Code: Alles auswählen

function TGnurz.GNZPotenzMod(Basis,Exponent,Modulo:GNZTyp):GNZTyp;
var z,e,Erg,eins,zwei:GNZTyp;
begin
  z:=Basis;//copy(Basis);
  e:=Exponent;//copy(Exponent);
  setlength(eins,1);
  eins[0]:=1;
  Erg:=eins;
  zwei:=GNZadd(eins,eins);
 
  while not ((length(e)=1)and(e[0]=0)) do
  begin
    If GNZistgerade(e) then
    begin
      e:=GNZdiv(e,zwei);
      z:=GNZmul(z,z);
      z:=GNZmod(z,Modulo);
    end else
    begin
      e:=GNZsub(e,eins);
      Erg:=GNZmul(Erg,z);
      Erg:=GNZmod(Erg,Modulo);
    end;
  end; //while
  Result:=Erg;
end; // GNZPotenzMod



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 »

Warum sollte der Pascal Compiler bei dieser Funktion wenig effektiven Code erzeugen ?

Für ASM-Optimierung eignen sich normalerweise nur Leaf-Funktionen, also solche, die keine weiteren Funktionen aufrufen.

Außerdem ist meiner Ansicht nach zuallererst da ASM sinnvoll wo es mit Pascal wirklicht nicht geht (z.B. 64Bit*64Bit -> 128 Bit, Variable schiften und die herausgeschoben Bits anderswo ablegen, oder gleichzeitig Modulo und und Divisions-Ergebnis verwenden, ...

-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:Warum sollte der Pascal Compiler bei dieser Funktion wenig effektiven Code erzeugen ?


Da hast du wohl recht. Ich hatte die Funktion eher wegen der Kürze gewählt und dabei außer Acht gelassen, dass Assembler bei dieser Funktion nicht allzu viel bringen wird.

Außerdem ist meiner Ansicht nach zuallererst da ASM sinnvoll wo es mit Pascal wirklicht nicht geht (z.B. 64Bit*64Bit -> 128 Bit, Variable schiften und die herausgeschoben Bits anderswo ablegen, oder gleichzeitig Modulo und und Divisions-Ergebnis verwenden, ...


Da stimme ich dir zu. Es ließe sich hinsichtlich letzteren Punktes auch ein Algorithmus schreiben, der GNZdiv und GNZmod "in einem Schritt" macht. Beide Funktionen nutzen zudem Routinen wie

Code: Alles auswählen

while n_dent<>0 do
        begin
          ZwSp:=ZwSp + Divident[n_dent];
          Erg[n_dent]:=ZwSp div Divisor[0];
          ZwSp := (ZwSp mod Divisor[0])*qword(GNZ_GlobZahlenbasis);
          dec(n_dent);
        end;//while


In denen eine Umsetzung in Assembler die Sache beschleunigen würde.

64Bit*64Bit -> 128 Bit ist glaube auch ein wichtiger Punkt.

Die größte Geschwindigkeitsteigerung nach meiner Einschätzung würde die Unit erfahren, wenn der Daten-Typ GNZTyp kein dynamisches, sondern ein statisches Array wäre. Viel Zeit geht u.U. sowohl bei der Pascalinternen Umsetzung von Dynamischen Arrays verloren, erst Recht aber durch meine defensive Programmierweise: Die Arrays sind nur so lange wie unbedingt notwendig. D.h. Wenn bei einer Division eine Zahl ihre Stellenzahl halbiert, muss durch setlength die Länge des Arrays laufend nachreguliert werden. Wenn es auf Geschwindigkeit ankommt, ist eine feste Speichergröße ideal. Die MPunit, die EugenE angesprochen hatte, verwendet z.B. statt ein dynamisches Array ein statisches array [0..30000] of cardinal. Dieses wird bei den Rechenoperationen von einem einfachen Pointer abgetastet. Das bringt Geschwindigkeit ins Haus, birgt aber zwei Nachteile: 1. Miserable Speicherverwertung; 2. Keine beliebig große Zahlen möglich.

Bei der Konstruktion des GNZTyps habe ich ebenfalls über ein statisches Array fester Größe nachgedacht. Ich fand es (und finde es immernoch) im hohen Maße unästhetisch und lehnte es ab. Schneller wäre es sicher - und es ließe sich zudem mit wenigen Handgriffen in der jetzigen GNURZ-Unit umsetzen.

Nun, die GNURZ ist quelloffen und steht unter der GPL. Damit kann sich jeder, der sie schneller machen will, betätigen.

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 »

Ich versuche 'mal eine ASM-Version der 7 Pascal-Zeilen mit gleichzeitiger mod und div-Berechnung.

Was ist denn "GNZ_GlobZahlenbasis" ?

Setlength kann ganz schlecht für die Performance sein. Wenn mit Setlength ein dynamisches Array vergrößert wird, muss es u.U. komplett kopiert werden, weil es ja am Ursprungs-Ort nicht mehr zwischen die davor und dahinter angelegten Variablen passt.

Ansonsten glaube ich, dass statische Arrays nicht viel besser als dynamische sind. Auf eine einzelne Pointer-Operation am Anfang der Berechnung des ganzen Arrays kommt es sicher nicht an.

Man könnte sich aber angucken, ob der Compiler Schleifen wie

Code: Alles auswählen

for i := 0 to length-1 do begin
  a[i] := a[i] + b[i];
end;

gut optimiert, d.h. mit laufenden Pointern arbeitet, statt immer wieder die Adresse über den Index auszurechnen. Ansonsten kann man von Hand mit Pointern arbeiten (unästhetisch (wie C :) ), aber schneller, ohne dass man ASM braucht) und dynamische Arrays tun da nicht weh. Dann bleiben die Zahlen beliebig lang. Alternativ kannst Du aber auch ohne dynamische Arrays mit Pointern arbeiten (wieder wie bei C ), indem Du diese mit getmem auf dem Heap anlegst. Der Nachteil gegenüber dynamischen Arrays ist dann, dass Du die Länge von hand verwalten musst. Ich glaube nicht, dass sich ein Geschwindigkeits-Unterschied gegenüber "ordentlicher" Verwendung von dynamischen Arrays (ohne mehrfachem Setlength) ergibt.

-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:Was ist denn "GNZ_GlobZahlenbasis" ?


Die GNURZ-Routinen sind so flexibel, dass sie mit beliebiger Zahlenbasis (Zehnersystem=10, Hexadezimalsystem=16, u.s.w.) rechnen können. Die Leistung der CPU wird dann ideal ausgenutzt, wenn die Zahlenbasis so gewählt wird, dass der verwendete Datentyp (dword) in seiner vollen Breite genutzt wird. Das wird durch die Variable GNZ_GlobZahlenbasis festgelegt.

Setlength kann ganz schlecht für die Performance sein. Wenn mit Setlength ein dynamisches Array vergrößert wird, muss es u.U. komplett kopiert werden, weil es ja am Ursprungs-Ort nicht mehr zwischen die davor und dahinter angelegten Variablen passt.


Ok, das leuchtet ein. Habe die Routinen so programmiert, dass es möglichst sparsam benutzt wird. Eine Frage: Es kostet also vermutlich weniger Rechenzeit, ein Array zu verkleinern als es zu vergrößern? Wenn ja würde ich den Code nochmal schnell durchschauen und entsprechende Optimierungen durchnehmen, denn darauf hatte ich bei der Programmierung nicht geachtet.

Man könnte sich aber angucken, ob der Compiler Schleifen wie
[...]
gut optimiert


Die Zeilen

Code: Alles auswählen

for n:=0 to aAnz-1 do
    begin
      ZwSp:= ZwSp + a[n] + b[n];


des Additionsalgorithmus wandelt der FPC wie folgt in Assembler um:

Code: Alles auswählen

# [270] for n:=0 to aAnz-1 do
   movl   -72(%ebp),%eax
   movl   $0,%edx
   subl   $1,%eax
   sbbl   $0,%edx
   movl   %eax,%ecx
   movl   $0,%ebx
   cmpl   %ebx,%ecx
   jb   .Lj478
   decl   %ebx
   .balign 4,0x90
.Lj479:
   incl   %ebx
   .stabn 68,0,272,.Ll102 - GNURZ_TGNURZ_$__GNZADD$GNZTYP$GNZTYP$$GNZTYP
.Ll102:
# [272] ZwSp:= ZwSp + a[n] + b[n];
   movl   12(%ebp),%eax
   movl   (%eax,%ebx,4),%esi
   addl   -68(%ebp),%esi
   movl   8(%ebp),%eax
   movl   (%eax,%ebx,4),%eax
   addl   %eax,%esi
   movl   %esi,-68(%ebp)
   .stabn 68,0,273,.Ll103 - GNURZ_TGNURZ_$__GNZADD$GNZTYP$GNZTYP$$GNZTYP


mit laufenden Pointern arbeitet, statt immer wieder die Adresse über den Index auszurechnen.


scheint er zu machen. Das würde demnach die lästige Arbeit mit Pointern ersparen :)

Danke für die Hinweise


Euklid

Antworten