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

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
Hitman
Beiträge: 512
Registriert: Mo 25. Aug 2008, 18:17
OS, Lazarus, FPC: ArchLinux x86, WinVista x86-64, Lazarus 0.9.29, FPC 2.4.1
CPU-Target: x86
Wohnort: Chemnitz

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

Beitrag von Hitman »

indianer-frank hat geschrieben:Trivial ist, daß man ein Produkt mit Compilerfehler nicht als fertig bezeichnen kann. Deine Bemerkungen würde ich für Hints/Notes gelten lassen, aber nicht für Warnungen. Selbst eine 'Note: Local variable "xxx" not used' zeigt doch, daß der Programmierer seinen Quellcode noch nicht fertig überarbeitet hat (da gab's mal die benutzte Variable "xxx", der Code wurde geändert, und jetzt ist die Deklarationsleiche noch da).

Solche Aussagen sind höchst subjektiv ... "fertig" ist etwas dann, wenn man es so einschätzt - man also ersteinmal nichts besser machen würde. Wie man Versionen vergibt ist ebenso subjektiv. Wenn jede "1.0" hochpoliert und feature-complete wäre, hätten wir nie Versionen darüber ;-) (wozu dann eine 1.01, 1.2, 2.0?). Umgekehrt kann man ebenso wenig schlussfolgern, dass ein Produkt mit Version "0.0.5" nicht stabil wäre. Möglicherweise hat dessen Autor dann einfach mehr Wert auf Stabilität gesetzt und misst mit der Version lediglich die Feature-Komplettheit.

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

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

Beitrag von indianer-frank »

Hitman hat geschrieben:
indianer-frank hat geschrieben:Trivial ist, daß man ein Produkt mit Compilerfehler nicht als fertig bezeichnen kann. ...

Solche Aussagen sind höchst subjektiv ... "fertig" ist etwas dann, wenn man es so einschätzt - man also ersteinmal nichts besser machen würde.

Also wie man ein Produkt, daß man noch nicht mal kompilieren kann, als subjektiv fertig bezeichnen kann, will mir nicht einleuchten (es sei denn, man ist in der Marketing-Abteilung der Sirius Cybernetics Corporation beschäftigt).

Im übrigen gibt es in vielen (?) Software-Entwicklungs-Abteilungen SOPs, in denen steht, daß ein Produkt ohne Warnungen kompilierbar sein muss.

Hitman hat geschrieben:Möglicherweise hat dessen Autor dann einfach mehr Wert auf Stabilität gesetzt und misst mit der Version lediglich die Feature-Komplettheit.

Siehe Bugs und fehlende Features. Und darauf sollte der Fokus liegen.

Gruß Frank

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 »

indianer-frank hat geschrieben:Noch ein paar elementare Fehler auf die Schnelle:


Es so, wie Hitman das angedeutet hat: Die Arithmetik-Unit ist von der Funktionalität her abgeschlossen. Ich hatte zudem Grund zur Annahme, dass die Unit nur noch sehr wenige Bugs enthält: Die Grundoperationen (+,-,*,/) wurden mit je 100 000 Zufallszahlen getestet. Die übrigen Funktionen wurden stichprobenartig getestet. Zudem ist das Projekt seit einer Ewigkeit hier im Forum verfügbar und es sind keine Fehlerberichte von außen bei mir eingetroffen.

Ich danke dir in jedem Fall für das Berichten der elementaren Fehler! Für künftige Fehler habe ich einen Bugtracker auf der Projekthomepage eingerichtet, der den Prozess der Fehlerbereinigung etwas übersichtlicher macht.

Viele Grüße, Euklid

Hitman
Beiträge: 512
Registriert: Mo 25. Aug 2008, 18:17
OS, Lazarus, FPC: ArchLinux x86, WinVista x86-64, Lazarus 0.9.29, FPC 2.4.1
CPU-Target: x86
Wohnort: Chemnitz

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

Beitrag von Hitman »

indianer-frank hat geschrieben:Also wie man ein Produkt, daß man noch nicht mal kompilieren kann, als subjektiv fertig bezeichnen kann, will mir nicht einleuchten (es sei denn, man ist in der Marketing-Abteilung der Sirius Cybernetics Corporation beschäftigt).

Im übrigen gibt es in vielen (?) Software-Entwicklungs-Abteilungen SOPs, in denen steht, daß ein Produkt ohne Warnungen kompilierbar sein muss.

Du sagst es ja selbst: "Abteilungen" ... wir reden hier nicht von einem Softwarekonzern, der GNURZ anbietet, sondern von einem Hobby-Projekt einer einzelnen Person. Und da sind alle Maßstabe rein subjektiv. Eventuelle Qualitätssicherungen und -maßstäbe wären freiwillig und ebenso subjektiv (mangels Review ...). Ich weiß nicht für wie perfekt du dich selbst hältst, aber ich zweifel an meinen eigenen Projekten ebenso, und würde keine Garantie geben, dass sie fehlerfrei sind. Soll ich deswegen auf einen Version "1.0" Tag verzichten? Das mindert dann wieder das allgemeine Interesse, weil viele der Ansicht sind, dass es sich nicht lohnt, etwas auszuprobieren, das nicht "fertig" ist ... und so bekäme ich nie Input von außen. Also was soll ich tun? Teure externe Entwickler und Tester anheuern?
Bevor du hier andere Leute in Grund und Boden stampfst, überleg lieber erstmal, was realistische Annahmen wären und ob du deine jetzigen dazu zählen würdest und auch selbst einhalten könntest ...

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 »

Aus genau diesem Grund ist es meist sinnvoll, auf vorhandenen Code zurückzugreifen und diesen zu verbessern, statt alles neu zu machen.

Hier würde sich eben NX anbieten, das man eingehend testen und um ein freundlicheres Programm-Interface erweitern könnte. Über NX haben sich schon diverse Leute Gedanken gemacht und es wäre dumm die nicht aufzugreifen.

-Michael
Zuletzt geändert von mschnell am Di 21. Jul 2009, 09:38, insgesamt 2-mal geändert.

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

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

Beitrag von indianer-frank »

Mein Bugreport "a := GO.StrToGNZTyp('2147483647'); ergibt a=1!" von gestern trifft nur bedingt zu, was die Sache allerdings noch beunruhigender macht. Mit dem Testgrogramm:

Code: Alles auswählen

{$mode objfpc}{$H+}
program t_g3;
uses gnurz;
var
  GO: TGnurz;
  a: GNZTyp;
  prim: boolean;
begin
  GO := TGnurz.create;
  a := GO.StrToGNZTyp('1');
  prim := GO.GNZIstPrim(a);
  a := GO.StrToGNZTyp('2147483647');
  writeln('a="2147483647"=',GO.GNZTypToStr(a));
  writeln('a="2147483647"=',GO.GNZTypToWord(a));
end.

erhält man die fehlerhafte Ausgabe
a="2147483647"=1
a="2147483647"=1

Wenn man die Zeile prim := GO.GNZIstPrim(a) löscht, erhält man das erwartete richtige Ergebnis !? D.h. irgendwie modifiziert GNZIstPrim(a) sein Argument!

Ein weiterer Bug bei rationaler Arithmentik: "0*(-456/123) <> 0". Das liegt daran, daß die linke Seite -0 ist. Konkret liefert GRaZagleichb false:

Code: Alles auswählen

z.Nenner  := GO.WordToGNZTyp(1);
z.Zaehler := GO.WordToGNZTyp(0);
z.negativ := false;
q.Nenner  := GO.WordToGNZTyp(123);
q.Zaehler := GO.WordToGNZTyp(456);
q.negativ := true;
 
s := GO.GRaZmul(q,z);
writeln('0*(-456/123)=0 : ', GO.GRaZagleichb(s,z));

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 »

indianer-frank hat geschrieben: Das liegt daran, daß die linke Seite -0 ist. Konkret liefert GRaZagleichb false:
Ein typisches Problem von nicht auf 1-Komplement basierter Integer-Arithmetik. Nicht ohne Grund sind all Rechner-Typen, die anders arbeiten ausgestorben. (So etwas gab es tatsächlich früher 'mal in Hardware :) )

-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: Offenbar unterscheidet auch die von dir geprisene 1-Komplement-Methode zwischen 0 und -0, vgl. http://de.wikipedia.org/wiki/Integer_(Datentyp) . Das Problem ist also kein strukturelles, sondern vielmehr an einem Bug in GRaZmul, der in Kürze behoben wird.

indianer-frank hat geschrieben:Wenn man die Zeile prim := GO.GNZIstPrim(a) löscht, erhält man das erwartete richtige Ergebnis !?


hmm, das ist wirklich merkwürdig! IstPrim sollte eigentlich keinen Einfluss auf a haben. Werde dem nachgehen...

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:mschnell: Offenbar unterscheidet auch die von dir geprisene 1-Komplement-Methode zwischen 0 und -0,

Ist schon schlecht, wenn man Alzheimer hat :( . Ich meinte "Zweiterkomplement" http://de.wikipedia.org/wiki/Zweierkomplement ), also genau das Gegenteil ;). Der Bug wäre bei Verwendung von Zweierkomplement-Darstellung nicht möglich gewesen. Nur bei der Verwendung von Zweierkomplement-Darstellung ist bei 32 und 64-bit-Werten das Langzahlen-Bitfeld identisch zu den entsprechenden Hardware-Typen (Integer, Cardinal, Int64, QWord) und vermutlich nur mit Zweierkomplement-Darstellung ist eine sinnvolle Kompatibilität zwischen 32 und 64-Bit Software machbar. Es hat schon Gründe, warum andere Zahlendarstellungen bei high-Performance-Software nicht verwendet werden.

(Wenn jemand ein Projekt für ein GNURZ-ähnliches Programmier-Interface für NX aufsetzt, mache ich gerne wieder aktiv mit...)

-Michael

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

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

Beitrag von indianer-frank »

mschnell hat geschrieben:.. Es hat schon Gründe, warum andere Zahlendarstellungen bei high-Performance-Software nicht verwendet werden.

(Wenn jemand ein Projekt für ein GNURZ-ähnliches Programmier-Interface für NX aufsetzt, mache ich gerne wieder aktiv mit...)


Aber hier wird nun Langzahl-Arithmetik implementiert, und da herscht nun mal "signed magnitude" und nicht 1-er- oder 2-er-Komplement (wenn man sich nicht auf natürliche Zahlen beschränken will). Bibliotheken wie GMP, MPIR auf C-Seite und NZ,MPArith,GINT bei Pascal benutzen alle diese Darstellung. Bei der häufig anfallenden "Normalisierung" sollte eigentlich immer die "-0"-Poblematik berücksichtigt werden.

Völlig unabhängig von der Darstellung einer Integer-Langzahl hat man bei rationalen Zahlen ein weiteres "Normalisierungsproblem", wenn Zähler und Nenner vorzeichenbehaftet sein können. Häufig wird eine normalisierte Darstellung q=z/n mit n>0, ggt(z,n) = 1 und 0=0/1 verwendet.

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 »

indianer-frank hat geschrieben:Aber hier wird nun Langzahl-Arithmetik implementiert, und da herscht nun mal "signed magnitude" und nicht 1-er- oder 2-er-Komplement (wenn man sich nicht auf natürliche Zahlen beschränken will).

Verstehe ich nicht. eine Zahl in 2-Kompliment-Darstellung kann beliebig viele Bits haben. Wie die Bits in Speicher-Einheiten (Bytes oder was auch immer) verteilt werden, regeld die "Endianess" (z.B. beim PC "low Endian" die 8 niederwertigsten Bits einer vorzeichenlosen oder einer 2-Kompliment-Zahl stehen im Byte mit der niedrigsten Adresse). Wenn man sich an die vin der Hardware vorgegebenen Darstellung hält (2-Komliment und Endianess) sind von der Hardware bearbeitbare Zahlen (beim iA32-64 PC also 8, 16, 62 und 64 Bit-Werte mit und ohne Vorzeichen) im Speicher kompatibel. (die höherwertigen Bits werden mit 0 (bei vorzeichenlosen Typen) oder mit dem Vorzeichen (bei vorzeichenbehafteten Typen gefüllt um auf die Darstellung mit höherer Bitzahl zu kommen.

indianer-frank hat geschrieben: Bibliotheken wie GMP, MPIR auf C-Seite und NZ,MPArith,GINT bei Pascal benutzen alle diese Darstellung. Bei der häufig anfallenden "Normalisierung" sollte eigentlich immer die "-0"-Poblematik berücksichtigt werden.


Normalisierung gibt es nur bei Gleitpunkt-Rechnung (und vermutlich bei Rationaler Rechnung). Nicht bei ganzen Zahlen oder 2-Komplement-Zahlen. Jede Bitkombination ist eindeutig, da kann nichts normalisiert werden.

indianer-frank hat geschrieben:Völlig unabhängig von der Darstellung einer Integer-Langzahl hat man bei rationalen Zahlen ein weiteres "Normalisierungsproblem", wenn Zähler und Nenner vorzeichenbehaftet sein können. Häufig wird eine normalisierte Darstellung q=z/n mit n>0, ggt(z,n) = 1 und 0=0/1 verwendet.


Deshalb ist es vermutlich ideal eine vorzeichenbehaftete rationale Zahl als Paar eines vorzeichenbehafteten Zählers und eines Vorzeichenlosen Nenners darzustellen.

-Michael

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

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

Beitrag von indianer-frank »

mschnell hat geschrieben:
indianer-frank hat geschrieben:Aber hier wird nun Langzahl-Arithmetik implementiert, und da herscht nun mal "signed magnitude" und nicht 1-er- oder 2-er-Komplement (wenn man sich nicht auf natürliche Zahlen beschränken will).

Verstehe ich nicht. eine Zahl in 2-Kompliment-Darstellung kann beliebig viele Bits haben. Wie die Bits in Speicher-Einheiten (Bytes oder was auch immer) verteilt werden, regeld die "Endianess" (z.B. beim PC "low Endian" die 8 niederwertigsten Bits einer vorzeichenlosen oder einer 2-Kompliment-Zahl stehen im Byte mit der niedrigsten Adresse). Wenn man sich an die vin der Hardware vorgegebenen Darstellung hält (2-Komliment und Endianess) sind von der Hardware bearbeitbare Zahlen (beim iA32-64 PC also 8, 16, 62 und 64 Bit-Werte mit und ohne Vorzeichen) im Speicher kompatibel. (die höherwertigen Bits werden mit 0 (bei vorzeichenlosen Typen) oder mit dem Vorzeichen (bei vorzeichenbehafteten Typen gefüllt um auf die Darstellung mit höherer Bitzahl zu kommen.

Mag ja alles für bestimmte Situation richtig sein, was Du da erzählst. Aber noch einmal: Hier soll Langzahlarithmetik implementiert werden. Und (ob Du es nun verstehst oder nicht) in der Praxis wird da meist "signed magnitude" verwendet. Der Vorteil in praktisch 0-Zeit das Vorzeichen (=1 bit) zu ändern ist doch wohl nicht zu unterschätzen. Und erst der Huddel bei zB Multiplikation, Division!

mschnell hat geschrieben:
indianer-frank hat geschrieben: Bibliotheken wie GMP, MPIR auf C-Seite und NZ,MPArith,GINT bei Pascal benutzen alle diese Darstellung. Bei der häufig anfallenden "Normalisierung" sollte eigentlich immer die "-0"-Poblematik berücksichtigt werden.


Normalisierung gibt es nur bei Gleitpunkt-Rechnung (und vermutlich bei Rationaler Rechnung). Nicht bei ganzen Zahlen oder 2-Komplement-Zahlen. Jede Bitkombination ist eindeutig, da kann nichts normalisiert werden.


Deshalb steht da auch "Normalisierung", und dabei geht es nicht um Gleitkommanormalisierung, sondern zB darum, daß die werthöchste Einheit <> 0 ist. Stell Dir vor, Du berechnest mit a = 2^100000, b = (2^100000-1) die Differenz a := a-b. Warum solltest Du weiter mit 100000 Bits für a rechnen? Du schreibst ja wohl auch nicht 10-1 = 09 (Es sei den Du hast ne fixe Anzahl von Stellen oder Bits). Weitere Beispiele wären: Freigebenen von Speicher, Test auf 0: Manche Implementation haben für 0 keinen 'Bitspeicher', sondern Länge=0 bedeutet Wert=0 etc)

mschnell hat geschrieben:
indianer-frank hat geschrieben:Völlig unabhängig von der Darstellung einer Integer-Langzahl hat man bei rationalen Zahlen ein weiteres "Normalisierungsproblem", wenn Zähler und Nenner vorzeichenbehaftet sein können. Häufig wird eine normalisierte Darstellung q=z/n mit n>0, ggt(z,n) = 1 und 0=0/1 verwendet.


Deshalb ist es vermutlich ideal eine vorzeichenbehaftete rationale Zahl als Paar eines vorzeichenbehafteten Zählers und eines Vorzeichenlosen Nenners darzustellen.
-Michael


Unnötig kompliziert wegen zB Kehrwert. MM entweder wie in GNURZ oder beides vorzeichenbehaftet. Um die "Normalisierung" auf teilerfremd und "-0" ->"0" muß eh gemacht werden.

Frank

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 »

indianer-frank hat geschrieben: Aber noch einmal: Hier soll Langzahlarithmetik implementiert werden.

Das geht eben auf verschiedene Weisen. Wie das für welchen Zweck sinnvoll ist, kann natürlich diskutiert werden. Brüllen (also Fettschrift) ist aber auf keinen Fall eine Diskussionsgrundlage. Ich vermute jedenfalls, dass die Hardware-Hersteller sich gut überlegt haben, warum sie immer eine 2-Kompliment Zahlendarstellung implementieren. (und 32-Bit Zahlen sind schließlich auch Langzahlen auf Basis von Bytes :) ).

Mir ist jedenfalls eine eindeutige Zahldarstellung, bei der jede Bitkombination einen unterschiedlichen Wert ergibt, wesentlich sympathischer.

indianer-frank hat geschrieben:Normalisieren...

Langzahlen mit nicht fester Wort-Länge sind eine besondere Kathegorie von Langzahlen. Es gibt viele Implementierungen mit fester Wort-Länge. Das ist in vielen Anwendungen auch durchaus sinnvoll.

Wenn man variable Wort-Länge implementieren will, tut man dass M.E. am besten, indem man eine Implementierung mit fester Wortlänge verwendet und deren Funktionen in den Funktionen mit variabler Wortlänge verwendet.

-Michael

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

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

Beitrag von indianer-frank »

mschnell hat geschrieben:Brüllen (also Fettschrift) ist aber auf keinen Fall eine Diskussionsgrundlage.
War ja auch nur ein Nothelf, da Du die "" ja ignoriert hast.

mschnell hat geschrieben:
indianer-frank hat geschrieben:Normalisieren...

Langzahlen mit nicht fester Wort-Länge sind eine besondere Kathegorie von Langzahlen. Es gibt viele Implementierungen mit fester Wort-Länge. Das ist in vielen Anwendungen auch durchaus sinnvoll.

Wenn man variable Wort-Länge implementieren will, tut man dass M.E. am besten, indem man eine Implementierung mit fester Wortlänge verwendet und deren Funktionen in den Funktionen mit variabler Wortlänge verwendet.
???????

Zu wiederholten und letzen mal: Es geht nicht um Implementation mit variabler Wortlänge sondern um Implementationen mit eine variablen Anzahl von Worten (die eine fixe Länge haben) (in GNURZ also Wort=dword wegen GNZTyp = array of dword)

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 »

Da hst Du mich leider völlig missverstanden. :(.

Die Wortlänge einer Langzahl (und darum geht es ja hier) ist ja wohl die Anzahl der verwendeten Bits und entsprechend also auch die Anzahl der verwendeten Speicherstellen (sei das nun in Byte, Word, DWord oder QWord gerechnet). Welchen Datentyp die Speichereinheiten haben ist ein Implementierungs-Detail, das (bei einer "optimalen" Implementierung) von außen an den Bitfeldern, die die Lang-Zahlen-Werte darstellen, nicht zu sehen sein sollte, weil es kompatibel zur Prozessor-Hardware realisiert ist (Zahldarstellung, Endieness, etc).

-Michael

Antworten