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

[Euklid]

Habe es immerhin geschafft, den SVN-Ordner mit kdesvn zu öffnen. Im Moment scheitert es an der Erstellung eines Arbeitsverzeichnisses...

Kann ich dir irgendwie helfen ?

Nehme das Angebot gerne an - aber am Besten, wenn wir uns mal im Chat treffen. Bin ja relativ regelmäßig dort.

mschnell: Gewünschte Version im Anhang.

[mschnell]

mschnell: Gewünschte Version im Anhang.

Hmm. Da ist immer noch die globale Zahlenbasis drin. Kann ich auch nicht ausbauen, weil ich da nicht genügend durchblicke.
Ich bin der Ansicht. Als Basis zur weiteren Bearbeitung brauchen wir eine Version, in der die globale Zahlenbasis als Wert nicht vorkommt (2^64 ist als Wert in keinem Typ darstellbar), sondern nur als in {$if abfragbarer Form mit den beide Möglichkeiten 2^32 und 2^64 also z.B. ist "GNURZBasis64" definiert oder nicht. Dann können wir später den Ausbau auf 64 Bit in Angriff nehmen.

Voll Kompatible Pascal- und ASM-Versionen derselben Funktionen (der "Internal"-Funktionen) sehe ich auch nicht. Soll ich die basteln ?

Frage: Warum ist das überhaupt eine Klasse ? Wenn die Funktionen sowieso GNZxyz heißen, braucht man doch beim Aufruf nicht immer noch "g." dazuzuschreiben. Wenn man ohnehin nur eine Instanz von irgendetwas erzeugten will, macht es nur dann Sinn, eine Klasse dafür zu definieren, wenn man in dem Ding auch noch jede Menge Daten verwalten will. Das macht TGNURZ aber nicht (die Variable für die Zahlen-Basis entfällt und die Karazubagrenze ist eine Konstante, die sich aus der Basis (32 oder 64 Bit) und möglicherweise ob mit oder ohne ASM-Beschleunigung ergibt - mit {$if, ohne dass man Code dafür braucht).

-Michael

[Euklid]

Hmm. Da ist immer noch die globale Zahlenbasis drin.

Genau. Wie oben erwähnt, wird die für die Division noch benötigt. Wenn man die GNZdiv löscht, wird auch die GNZ_GlobZahlenbasis nicht mehr benötigt.

Ich bin der Ansicht. Als Basis zur weiteren Bearbeitung brauchen wir eine Version, in der die globale Zahlenbasis als Wert nicht vorkommt (2^64 ist als Wert in keinem Typ darstellbar), sondern nur als in {$if abfragbarer Form mit den beide Möglichkeiten 2^32 und 2^64 also z.B. ist "GNURZBasis64" definiert oder nicht. Dann können wir später den Ausbau auf 64 Bit in Angriff nehmen.

Voll Kompatible Pascal- und ASM-Versionen derselben Funktionen (der "Internal"-Funktionen) sehe ich auch nicht.

Die Pascalversion, die ohne Assembler auskommt (dafür aber mit der Zahlenbasis) habe ich extra für dich entfernt, da du ja "nur eine Version" der Routinen in der Unit haben wolltest. Zumindest hatte ich dich so verstanden.

Soll ich die basteln ?

Kannst du gerne machen - ich muss aber fairerweise dazu sagen, dass ich momentan wenig Zeit habe, mich um GNURZ zu kümmern. Aber die Unit ist ja OpenSource und kann von jedem weiterentwickelt werden, der Interesse daran hat - das ist der Vorteil von OpenSource. Der Performancegewinn durch Deine Assembler-Routinen ist enorm Durch 64bit ließe sich dies für die Prozessoren der Zukunft sicherlich nochmals erheblich ausbauen.
GNURZ ist ja strenggenommen nur ein kleiner Teil eines größeren Projektes: Promathika. Hier stehen noch sehr viele Dinge an, um die ich mich kümmern muss: Vereinfachung von Termen, Lösungsroutinen zur Lösung von nichtlinearen Gleichungssystemen, Routinen zur Integration und Differentiation sowie einige numerische Funktionen (Kurvenanpassung, Berechnung der Lagrange- bzw. Newton-Polynome). Diese Dinge verschlingen im Moment die meiste Zeit, in der ich programmiere.

Frage: Warum ist das überhaupt eine Klasse ?

Das ist eine gute Frage! Als ich die GNURZ aus Promathika heraus extrahiert habe, damit sie noch anderen Pascal-Programmierern nützlich sein kann, dachte ich, eine Klassenstruktur wäre das vernünftigste. Allerdings hast du recht, dass dies mit dem Wegfall der Zahlenbasis und der festen Implementierung der Karazubagrenze die Klassenstruktur nicht mehr notwendig ist.

Viele Grüße, Euklid

[mschnell]

Wenn man die GNZdiv löscht, wird auch die GNZ_GlobZahlenbasis nicht mehr benötigt.

Ich will nicht in Deiner Datei 'rumlöschen. Ich warte auf eine Version von Dir, die als Startpunkt für weitere (gemeinsame) Arbeiten (im SVN Archiv) dient. Alles andere ist mir zu chaotisch.

-Michael

[Euklid]

Ich will nicht in Deiner Datei 'rumlöschen. Ich warte auf eine Version von Dir, die als Startpunkt für weitere (gemeinsame) Arbeiten (im SVN Archiv) dient.

Ich habe nichts dagegen, wenn die GNURZ ganz im Sinne von OpenSource weiterentwickelt wird, im Gegenteil. Deswegen ist sie ja OpenSource.
Aber wie gesagt: Ich kann meine Freizeit nur einmal verwenden, und da setze ich Schwerpunkte. Und um das mal mit aller Deutlichkeit zu sagen: Die Schwerpunkte liegen nicht darin, zu erraten, wie für dich ein Startpunkt für weitere Arbeit aussieht. Das kannst nur du selbst wissen und auch umsetzen, wenn du gewillt bist.

Alles andere ist mir zu chaotisch.

Die GNURZ ist in seinen Ursprüngen hinsichtlich seiner GNZ-Arithmetik ein sehr sauberes Projekt ohne bekannte Bugs - und das trotz regelmäßigem Einsatz und umfangreicher Prüfung. Das ist alles andere als chaotisch.

Die assembleroptimierte GNURZ betrachte ich als noch nicht fertiggestellt. Sie leistet genau das selbe, wie die ursprüngliche GNURZ - nur eben mit erheblichen Optimierungen, die die Grundoperationen add, mul und sub betreffen und an denen du maßgeblich beteiligt bist. Aber auch diese Unit hat eine innere Ordnung - denn hier wird per ifdef eine genaue Codeauswahl zur entsprechenden Archtiektur getroffen. Die Strukturen sind also schon geschaffen. Um die GNURZ_ASM zu erweitern müssen also bloß die bereits vorhandenen Strukturen genutzt werden. Wem das noch nicht "Startpunkt für weitere Arbeit" genug ist, dem kann ich nicht weiter helfen und er führt am Besten selbst entsprechende Anpassungen durch, die den persönlichen Geschmack eher treffen.

Euklid

[mschnell]

Ich habe genau spezifiziert, was als Startpunkt für weitere Arbeiten notwendig ist. Da brauchst Du wirklich nichts "raten". (Schau 'mal einige Messages zurück.) Wichtig für eine gemeinsame Arbeit ist, dass eine von allen akzeptierte Basis existiert und alle, wenn möglich, mit der jeweils aktuellen Version arbeiten.

Deshalb hat AF die "Professionalisierung" des Arbeitsprozesses über SVN vorgeschlagen.

Aber wenn Du keine Zeit hast ist halt nix zu machen.

Schade dass, das Projekt somit stirbt

Ich hoffe trotzdem dir mit der ASM-Optimierung geholfen zu haben.

-Michael

[af0815]

Schade dass, das Projekt somit stirbt

Wegen einer kleinen Sache stirbt kein Projekt

Bezüglich SVN, siehe Post dort.

[Euklid]

Ich hatte bereits in einen der ersten Beiträge dieses Threads erwähnt, dass meine Zeit knapp wird. Ich habe versucht, die Struktur der GNURZ so aufzubauen, dass sie von anderen Programmierern leicht erweitert werden kann. Dank af's SVN-Zugang wurde endgültig eine Öffnung des Projektes möglich.
Meine Beiträge hinsichtlich der Optimierung der GNURZ sind generell nur gering, da ich kaum Assembler-Kenntnisse besitze. Daher sollte die Weiterentwicklung der GNURZ auch nicht allzu stark von mir abhängen. Natürlich werde ich die weitere Entwicklung der GNURZ verfolgen und wünsche Euch viel Erfolg!

[mschnell]

Ich habe versucht, die Struktur der GNURZ so aufzubauen, dass sie von anderen Programmierern leicht erweitert werden kann. Dank af's SVN-Zugang wurde endgültig eine Öffnung des Projektes möglich.

Ich wüsste momentan nicht, wie die Variable globale Zahlenbasis komplett (bei der Division) ausgebaut werden könnte

Vielleicht schien wir uns das am Montag 'mal genauer an.

-Michael

[mschnell]

Hat noch jemand Interesse an dem Thema ?

Vielleicht schauen wir uns 'mal das an: http://www.delphiforfun.org/Programs/Li ... tegers.htm" onclick="window.open(this.href);return false;

Ich hab' noch nicht 'reingeschaut. Vielleicht kann man ja eine optimale Lösung finden

- Dynamic array
- "freundliches" User-Interface mit functions
- zusätzlich Operator overload (FPC)
- 32 und 64 Bit Basistyp (u.u. auch High Word First für Power Mac)
- Karazuba Multiplikation
- Assembler Optimierung

-Michael

[mschnell]

"NX - Numerics" ( http://www.ellipsa.net/public/nx/nx.html" onclick="window.open(this.href);return false; ) ist ein weiteres Open Source Projekt, das in Object-Pascal und Assembler Großzahlen-Arithmetik anbietet. Sowohl Integer als auch Real. Für die Multiplikation wird auch hier Karatsuba verwendet. Bei ganz vielen Bits (> 80000) soll der Toom-3 Algorithmus noch schneller sein. Der ist da auch implementiert.

"NX - Numerics" verwendet keine dynamischen Arrays und ist deshalb in der Anwendung lange nicht so praktisch wie GNURZ.

-Michael

[indianer-frank]

Ich weiß zwar nicht, was Du genau unter dynamischen Arrays verstehst, aber selbstverständlich hat NX keine Arrays mit festen Grenzen. Scheint die gleiche Fehleinschätzung zu sein wie in früheren Beiträgen für MPArith http://home.netsurf.de/wolfgang.ehrhard ... ml#mparith.

Beide Bibliotheken benutzen Records (keine Klassen) mit Zeigern auf die Digit-Arrays, beide unterstützen übrigens explizit Freepascal (während DelphiForFun's big_integers nur für Delphi ist) und beide sind auchvor kurzem aktualisert worden.

Frank

[mschnell]

Natürlich hat NX keine Arrays mit festen Grenzen .
Wenn ich das richtig sehe, muss man bei den NX-Funktionen für jeden Parameter das Datenfeld und die Länge angeben. Ein Design-Merkmal von GNURZ war, dass die Aufrufe Funktionen sind, die zwei "Langzahlen" als Parameter erhalten und eine Langzahl als Result zurückgeben. Deshalb sind die Lanzahlen "Dynamic Arrays" (Typefef TGNURZ = array of DWord; oder so ähnlich). Dabei kann die länge der Parameter unterschiedlich sein und die des Ergebnisses wird entsprechend angepasst.

Das ist von der Performance manchmal nicht ideal (siehe Diskussion) aber sehr praktisch.

-Michael

[indianer-frank]

Natürlich hat NX keine Arrays mit festen Grenzen .
Wenn ich das richtig sehe, muss man bei den NX-Funktionen für jeden Parameter das Datenfeld und die Länge angeben.

Grundsätzlich siehst Du das nicht richtig . Die "normalen" Funktionen verhalten sich in etwa so, wie Du es für GNURZ erwartest, zB

Code: Alles auswählen

//======================================
// A := A * B
//======================================
procedure IMul(A,B: PBigInt);
 
 
//======================================
// A <- A div B (B is not modified)
// Result := TRUE iff A mod B = 0
//======================================
function IDiv(A,B: PBigInt): Boolean;

Gewöhnungsbedürfig ist allerdings dabei, daß in der Regel eine Eingabe überschrieben wird, bei einigen Operationen gibt es "xxxTO"-Funktionen, die dies Verhalten nicht zeigen

Code: Alles auswählen

//===============================
// R := A + B
//===============================
procedure IAddTo(R,A,B: PBigInt);

Längenparameter sind normalerweise nur für Low-Level-Proceduren "raw..." erforderlich, die direkt auf dword-Arrays arbeiten. Diese werden allerdings von Otto Normaluser nicht gebraucht.

Frank

[Euklid]

Hat noch jemand Interesse an dem Thema ?

Hallo mschnell,

ich interessiere mich noch für das Thema und werde es verfolgen. Komme in letzter Zeit überhaupt nicht mehr zum Programmieren. Werde mich in den Osterferien an Promathika setzen und um einige Funktionen erweitern. Wahrscheinlich wird innerhalb eines halben Jahres die Unterstützung von Gleitkommazahlen anfallen, die dann auch der GNURZ zugute kommen wird. Mal schaun, wie sich das entwickelt.

Viele Grüße, Alexander