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

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
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 »

OK, svn funktioniert (zumindest auf Linux, Windows probiere ich vielleicht noch ).

-> Euklid,

Ich beteilige mich aber erst mit Uploads, wenn Du die Sourcen so bereinigt hast, dass keine Runtime-Abfragen auf GNZ_GlobZahlenbasis mehr gemacht werden. Oder hast Du damit irgendetwas bestimmtes vor ? Ich verstehe auch nicht, wie Du man die GNZ_GlobZahlenbasis auf 2^32 setzen kann, was doch momentan der Stanad der Technik ist (später 'mal 2^64...)

Irgendwo in der Doku habe ich auch gelesen, dass negative Zahlen durch ein zusätzlichen Boolean definiert werden. Das halte ich auch nicht für sinnvoll. Ich meine die Darstellung der Zahlen im Speicher sollte voll kompatibel zu der von der CPU vorgegeben Darstellung sein (2-Komplemen also ist das oberste Bit das Vorzeichen). Dann braucht man beim addieren und Subtrahieren das Vorzeichen garnicht zu berücksichtigen, sondern es geht automatisch, weil der Algorithmus für vorzeichenbehaftete und Vorzeichenlose Zahlen gleich ist.

Gruß,
-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:Ich beteilige mich aber erst mit Uploads, wenn Du die Sourcen so bereinigt hast, dass keine Runtime-Abfragen auf GNZ_GlobZahlenbasis mehr gemacht werden. Oder hast Du damit irgendetwas bestimmtes vor ? Ich verstehe auch nicht, wie Du man die GNZ_GlobZahlenbasis auf 2^32 setzen kann, was doch momentan der Stanad der Technik ist (später 'mal 2^64...)


Du wirst bei deiner Durchsicht des Codes sicher festgestellt haben, dass die GNZ_Globzahlenbasis im Fall von x86-Prozessoren hinsichtlich der Operationen mul, add, sub nicht mehr verwendet wird. Von den übrigen Funktionen wird sie nur noch in der div-Routine verwendet.
Die GNZ_GlobZahlenbasis existiert momentan aus 2 Gründen:
1. Wir haben noch keine 32bit-optimierte Variante der Division. Die Divisions-Routine ist also noch die Alte und enthält noch die GNZ_GlobZahlenbasis.
2. Für den Fall, dass die CPU nicht x86-kompatibel ist, wird nach den alten Routinen gerechnet, welche die GNZ_GlobZahlenbasis enthalten.

Irgendwo in der Doku habe ich auch gelesen, dass negative Zahlen durch ein zusätzlichen Boolean definiert werden. Das halte ich auch nicht für sinnvoll. Ich meine die Darstellung der Zahlen im Speicher sollte voll kompatibel zu der von der CPU vorgegeben Darstellung sein (2-Komplemen also ist das oberste Bit das Vorzeichen). Dann braucht man beim addieren und Subtrahieren das Vorzeichen garnicht zu berücksichtigen, sondern es geht automatisch, weil der Algorithmus für vorzeichenbehaftete und Vorzeichenlose Zahlen gleich ist.


Das wäre ein Ansatz, um den GNZTyp abzuschaffen und vollständig durch den GRaZTyp zu ersetzen. Momentan frage ich mich, ob sich das so einfach realisieren lässt - denn nicht jede Komponente des Arrays wird ein Vorzeichen benötigen, sondern nur das Array als ganzes. Zur Zeit basiert der GRaZTyp tatsächlich auf dem GNZTyp, zusammen mit einem Vorzeichen-Boolean.

Gruß, 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:1. Wir haben noch keine 32bit-optimierte Variante der Division. Die Divisions-Routine ist also noch die Alte und enthält noch die GNZ_GlobZahlenbasis.
2. Für den Fall, dass die CPU nicht x86-kompatibel ist, wird nach den alten Routinen gerechnet, welche die GNZ_GlobZahlenbasis enthalten.
Die Funktionen sollten sich aber doch leicht umstellen so lassen, dass es nur noch zwei Optionen gibt: Zahlenbasis 2^32 und Zahlenbasis 2^64, und diese Abfrage mit $Ifdefs passiert und kein code dafür erzeugt wird.
Euklid hat geschrieben:Das wäre ein Ansatz, um den GNZTyp abzuschaffen und vollständig durch den GRaZTyp zu ersetzen. Momentan frage ich mich, ob sich das so einfach realisieren lässt - denn nicht jede Komponente des Arrays wird ein Vorzeichen benötigen, sondern nur das Array als ganzes. Zur Zeit basiert der GRaZTyp tatsächlich auf dem GNZTyp, zusammen mit einem Vorzeichen-Boolean.
Es wäre schön das zu vereinheitlixchen. Fast jede CPU arbeitete hardwaremäßig mit 2-Komplimenten (alle Bits gesetzt = -1), weil dann eben dieselbe Hardware für vorzeichenlose und vorzeichenbehaftete Addition und Subtraktion verwendet werden kann. Finde ich sehr praktisch und platzsparend. Man muss aber dann für die Multiplikation und die Division verschiedene Funktionen vorzeichenlose und vorzeichenbehaftete Werte zur Verfügung stellen.

-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:Die Funktionen sollten sich aber doch leicht umstellen so lassen, dass es nur noch zwei Optionen gibt: Zahlenbasis 2^32 und Zahlenbasis 2^64, und diese Abfrage mit $Ifdefs passiert und kein code dafür erzeugt wird.


Ja, es wird bereits durch ifdefs unterschieden und nur soviel Code wie unbedingt nötig erzeugt. Dennoch halte ich die Eingrenzung auf x86-Prozessoren für nicht notwendig, da allgemeine Routinen (welche allerdings auf GNZ_Zahlenbasis angewiesen sind) bereits existieren und deren Rauswurf keinen Sinn machen.
Hinsichtlich 32bit und 64bit wird die GNZ_Zahlenbasis nicht mehr notwendig sein, wenn die Grundoperationen add, mul, div, sub für die jeweilige Architektur angepasst werden.

Es wäre schön das zu vereinheitlixchen. Fast jede CPU arbeitete hardwaremäßig mit 2-Komplimenten (alle Bits gesetzt = -1), weil dann eben dieselbe Hardware für vorzeichenlose und vorzeichenbehaftete Addition und Subtraktion verwendet werden kann. Finde ich sehr praktisch und platzsparend. Man muss aber dann für die Multiplikation und die Division verschiedene Funktionen vorzeichenlose und vorzeichenbehaftete Werte zur Verfügung stellen.


Ich befürworte diese Pläne und werde mich deren Umsetzung keinesfalls in den Weg stellen.


Gruß, Euklid

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:Ja, es wird bereits durch ifdefs unterschieden und nur soviel Code wie unbedingt nötig erzeugt. Dennoch halte ich die Eingrenzung auf x86-Prozessoren für nicht notwendig, da allgemeine Routinen (welche allerdings auf GNZ_Zahlenbasis angewiesen sind) bereits existieren und deren Rauswurf keinen Sinn machen.
Hinsichtlich 32bit und 64bit wird die GNZ_Zahlenbasis nicht mehr notwendig sein, wenn die Grundoperationen add, mul, div, sub für die jeweilige Architektur angepasst werden.


Bitte nicht aus den Augen zu verlieren, das es auch andere Prozessoren als Target gibt, speziell genannt arm und armel, mit Linux bzw. WinCe. Nachdem dort oft mit Emulation von Flotingpoint gearbeitet wird, ist natürlich auch eine eigene Geschichte.
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 »

Euklid hat geschrieben:Dennoch halte ich die Eingrenzung auf x86-Prozessoren für nicht notwendig,
Habe ich nie gesagt !
Eingrenzen wollte ich nur auf alternativ 32 oder 64 Bit. und andere CPUs, auf denen Lazarus läuft, gibt es nicht.
Ich würde allerdings auch für alte PowerPC MACs das Zahlenformat kompatibel zur Hardware aufbauen (höchstwertiges Wort auf niedrigster Adresse). Das wäre sauberer, greift natürlich tief in die einzelnen Funktionen ein. Musst Du entscheiden, ob Du das willst.

P.S.: Gibt es für die Division irgendetwas intelligentes ? gibt es da eine "innerste Schleife", die man leicht in ASM umsetzen kann ?

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

af0815 hat geschrieben:Bitte nicht aus den Augen zu verlieren, das es auch andere Prozessoren als Target gibt

Ich habe immer vertreten, die für alle ASM-Funktionen voll 1:1 kompatible Pascal-Funktionen zu haben und ASM nur mit entsprechenden Compiler-Optionen einzuschalten. Dann können weitere Targets nach und nach optimiert werden.

-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:Eingrenzen wollte ich nur auf alternativ 32 oder 64 Bit. und andere CPUs, auf denen Lazarus läuft, gibt es nicht.


ok. die "allgemeinen Routinen" sind durchweg 32bit. D.h. für 64bit bräuchte man auch hier Assembler-Lösungen für die anderen Archtiekturen.

Ich würde allerdings auch für alte PowerPC MACs das Zahlenformat kompatibel zur Hardware aufbauen (höchstwertiges Wort auf niedrigster Adresse). Das wäre sauberer, greift natürlich tief in die einzelnen Funktionen ein. Musst Du entscheiden, ob Du das willst.


Ich kenne mich mit PPC nicht aus, kann hierzu wohl wenig beitragen - daher kann ich die Entscheidung nicht fällen und überlasse sie dir, da du wahrscheinlich die Hauptarbeit erledingen müsstest. Ausschließlich die Funktionen mul, div, add, sub sind architekturabhängig. Die anderen bauen alle auf diese 4 Grundfunktionen auf. Das würde die von dir erwähnte Umstellung erleichtern.
Gibt es für die Division irgendetwas intelligentes ? gibt es da eine "innerste Schleife", die man leicht in ASM umsetzen kann ?

Das ist eine sehr gute Frage! Die Divisionsroutinen baut auf dem Prinzip der schriftlichen Division auf - einen besserer Algorithmus ist mir weder eingefallen, noch habe ich einen besseren gefunden. Aber selbst die Umsetzung der schriftlichen Divisionsmethode stellte sich als schwierig heraus. Kann mir vorstellen, dass eine Assembler-Optimierung hier besonders knifflig werden würde.

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:PPC...da du wahrscheinlich die Hauptarbeit erledingen müsstest.
Nö klann ich nicht. Dazu habe ich gar keine Test-Hardware.
Euklid hat geschrieben:Ausschließlich die Funktionen mul, div, add, sub sind architekturabhängig. Die anderen bauen alle auf diese 4 Grundfunktionen auf. Das würde die von dir erwähnte Umstellung erleichtern.
Genau. (Bei Mult ist hier aber Langzahl * Teilwort gemeint, bei div wissen wir nioch nicht so recht :) )
Bezüglich der Kompatibilität der ASM-Sachen ist die wichtigste Vorarbeit, dass alle Arithmetik-Funktionen immer über die definierten ASM Funktionen ausgeführt werden. Es muss dann von den ASM-Funktionen aber auch eine voll kompatible Pascal-Version geben, die verwendet wird, wenn die entsprechende ASM-Funktion für die vorliegende Implementierung nicht existiert (gesteuert durch entsprechende Compiler-Switches).

Euklid hat geschrieben:Das ist eine sehr gute Frage! Die Divisionsroutinen baut auf dem Prinzip der schriftlichen Division auf - einen besserer Algorithmus ist mir weder eingefallen, noch habe ich einen besseren gefunden. Aber selbst die Umsetzung der schriftlichen Divisionsmethode stellte sich als schwierig heraus. Kann mir vorstellen, dass eine Assembler-Optimierung hier besonders knifflig werden würde.
Fällt mir im Moment auch nix zu ein. Ich habe mir aber Deinen Code noch nicht angeschaut.

-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:Nö klann ich nicht. Dazu habe ich gar keine Test-Hardware.
Ok, dann können wir diese Architektur erstmal ausklammern.
Bezüglich der Kompatibilität der ASM-Sachen ist die wichtigste Vorarbeit, dass alle Arithmetik-Funktionen immer über die definierten ASM Funktionen ausgeführt werden. Es muss dann von den ASM-Funktionen aber auch eine voll kompatible Pascal-Version geben, die verwendet wird, wenn die entsprechende ASM-Funktion für die vorliegende Implementierung nicht existiert (gesteuert durch entsprechende Compiler-Switches).

Ja, die Pascal-Version ist derzeit die nichtoptimierte GNURZ.

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:Ja, die Pascal-Version ist derzeit die nichtoptimierte GNURZ.

Eben nicht ! zumindest nicht bei mult.
-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:Eben nicht ! zumindest nicht bei mult.


Doch, die - wie du es nennst - "kompatible Pascalversion" gibt es. Du wirst bei der Durchsicht des Quelltextes sicherlich bemerkt haben, dass die ifdef bei mult ausgekommentiert ist, und daher kann ich die Verwirrung deinerseits zumindest nachvollziehen.

Aus Gründen des Debuggings habe ich die alte GNZmul vorübergehend in GNZmul2 umbenannt, um sie mit den neuen Routinen vergleichen zu können.

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 »

OK, dann schaue ich mir das am Montag 'mal genauer an.

Trotzdem möchte ich an dem Sourcefile in dieser Form nicht basteln. Vielleicht stellst Du ein File unter anderem Namen (oder in einem anderen (svn Branch) zur Verfügung, das nur jeweils eine Version enthält.

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

Das kann ich machen. Werde heute Abend mal schaun, ob ich das mit SVN hinbekomme. Wenn nicht, kann ich die Version hier hochladen.

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:Werde heute Abend mal schaun, ob ich das mit SVN hinbekomme
Kann ich dir irgendwie helfen ?
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Antworten