GNURZ Dokumentation¶

GNURZ: Arithmetik zum Umgang mit (G)roßen (N)atürlichen (U)nd (R)ationalen (Z)ahlen

GNURZ stellt alle zum Umgang mit beliebig großen natürlichen und rationalen Zahlen notwendigen Funktionen und Grundoperationen bereit.

Der größte native FreePascal-Datentyp ist qword. Mit qword können bis zu 19-stellige Zahlen dargestellt werden. Aufgrund dieser Beschränktheit wurden für große natürliche und rationale Zahlen zwei neue Datentypen notwendig:

Datentyp für große natürliche Zahlen (GNZ):

GNZTyp = array of dword;

Eine Ziffern-Zeichenfolge in Form eines Strings lässt sich durch die Funktion StrToGNZTyp in den GNZTyp umwandeln. Umgekehrt gibt GNZTypToStr die Zahl als Ziffernfolge zurück. Für Zahlen vom Typ DWord gibt es die Funktionen WordToGNZTyp und GNZTypToWord. Die konkrete Anwendung der Funktionen kann im Demo-Projekt nachvollzogen werden: http://forge.lazarusforum.de/projects/list_files/gnurz

Datentyp für große rationale Zahlen (GRZ):

GRaZTyp = record
    nenner, zaehler: GNZTyp;
    Negativ: boolean;

Wie aus dieser Deklaration hervorgeht, werden rationale Zahlen in Form von Brüchen behandelt, bei denen jeweils Nenner und Zähler große natürliche Zahlen vom Typ GNZTyp sind. Die Zahl 3,14159 kann entsprechend durch 314159/100000 ausgedrückt werden. Dadurch werden beliebig genaue Rechnungen möglich, da wie im Beispiel 2/3=0,66666... keine Nachkommastellen abgeschnitten werden müssen und es somit zu keinen Rundungsfehlern kommt.

Die zur Zeit verfügbaren Funktionen und Operationen in Verbindung mit großen natürlichen und rationalen Zahlen sind folgende:

Operationen: Natuerliche Zahlen

      function GNZadd(a,b:GNZTyp):GNZTyp;                
              //Gibt die Summe a + b zurueck. Rechnet mit Grossen Natuerlichen Zahlen (GNZ); Zbasis=Zahlenbasis (Dezimalsystem:Zbasis=10)

      function GNZsub(Minuent,Subtrahend:GNZTyp):GNZTyp; 
              // Rechnet Minuend-Subtrahend. Aus Minuent<Subtrahend folgt Errormodus:=1

      function GNZmul(a,b:GNZTyp):GNZTyp;                
              //Gibt das Produkt a*b zurueck. Rechnet mit grossen natuerlichen Zahlen.

      function GNZmulword(a:dword;b:GNZTyp):GNZTyp;     
              // Wie GNZmul, nur ist a vom Typ dword

      function GNZakleinerb(a,b:GNZTyp):boolean;         
              // Prueft, ob a kleiner ist als b

      function GNZagleichb(a,b:GNZTyp):boolean;          
              // Prueft, ob sich a und b gleichen.

      function GNZdiv(Divident, Divisor:GNZTyp):GNZTyp;  
              //dividiert Divident durch Divisor und gibt das Ergebnis zurueck

      function GNZmod(Divident, Divisor:GNZTyp):GNZTyp;  
              //Gibt Divident mod Divisor zurueck

      function GNZggt(a,b:GNZTyp):GNZTyp;                
              //Groesster gemeinsamer Teiler fuer grosse natuerliche Zahlen (GNZ)

      function GNZkgv(a,b:GNZTyp):GNZTyp;                
              //Kleinstes gemeinsames Vielfaches fuer GNZ

      function GNZistgerade(zahl:GNZTyp):boolean; inline; 
              //Prueft, ob zahl mod 2 = 0

      function GNZPotenz(Basis,Exponent:GNZTyp):GNZTyp;  
              //Gibt Zahl^Exponent zurueck.

      function GNZPotenzMod(Basis,Exponent,Modulo:GNZTyp):GNZTyp; 
              //Rechnet Basis^Exponent mod Modulus.

      function GNZFakultaet(nFak:dword):GNZTyp;          
              // Gibt n! zurueck - experimentell

      function GNZIstPrim(zahl:GNZTyp):boolean;          
              //Wahr, wenn zahl Primzahl - experimentell

      function GNZMillerRabin(zahl:GNZTyp; it:word):boolean; 
              //Miller-Rabin Primzahltext. Wenn die Zahl den Test besteht, ist sie mit einer Wahrscheinlichkeit von (1/4)^it prim.

      function GNZMRPrimdanach(zahl:GNZTyp; it:word):GNZTyp;  
              //Bestimmt die nach zahl nächste Primzahl mit Hilfe des Miller-Rabin-Algorithmus

      function GNZZufall(Obergrenze:GNZTyp):GNZTyp;  
              // Gibt eine Zufallszahl wieder, die kleiner ist als Obergrenze.

      function GNZeins:GNZTyp;                 
              // Gibt 1 zurueck

      function GNZnull:GNZTyp;                     
              // Gibt 0 zurueck

Operationen: Rationale Zahlen

      function GRaZKuerzen(Bruch:GRaZTyp):GRaZTyp;       
              //Kuerzt den Bruch

      function GRaZadd(a,b:GRazTyp):GRaZTyp;             
              //Rechnet a+b und kuerzt die Summe anschliessend

      function GRazsub(Minuent,Subtrahend:GRaZTyp):GRaZTyp; 
              //Wenn Minuent<Subtrahend wird Errormodus:=1 gesetzt

      function GRaZmul(a,b:GRaZTyp):GRaZTyp;             
              //Multipliziert die Brueche miteinander

      function GRaZdiv(Divident,Divisor:GRaZTyp):GRaZTyp;   
              //Dividiert durch Multiplikation mit dem Kehrwert

      function GRaZakleinerbBetrag(a,b:GRaZTyp):boolean;
              //Gibt true zurueck, wenn |a| < |b|

      function GRaZakleinerb(a,b:GRaZTyp):boolean;       
              //Gibt true zurueck, wenn a < b

      function GRaZagleichbBetrag(a,b:GRaZTyp):boolean; 
              //Gibt true zurueck, wenn |a| = |b|

      function GRaZagleichb(a,b:GRaZTyp):boolean;        
              //Gibt true zurueck, wenn a = b   

Funktionen zur Typenkonvertierung und sonstige Funktionen:

      function GetErrormodus:dword;                  
              //Gibt 0 zuruecht, wenn kein Fehler aufgetreten ist.

      procedure ResetErrormodus;                     
              //Setzt Errormodus auf 0 zurueck

      function GetKarazubagrenze:dword;              
              //Gibt die Grenze zurueck, aber der der Karazuba-Algo. der Multiplikation verwendet wird

      procedure SetKazarzbagrenze(Grenze:dword);     
              //Setzt die Karazuba-Grenze neu.

      function GetGlobZahlenbasis:dword;             
              //Gibt die Zahlenbasis zurueck, mit der GNURZ intern(!) rechnet.

      procedure SetGlobZahlenbasis(basis:dword);     
              //Setzt die Zahlenbasis von GNURZ

      function StrToGNZTyp(Eingabe:string):GNZTyp;   
              //Wandelt eine natuerliche Zahl in string-Forum um in den Typ GNZTyp von Basis 10. Eingabe darf nur Zahlen enthalten.

      function GNZTypToStr(Eingabe:GNZTyp):string;   
              //"Umkehrfunktion" zu StrToGNZTypDez;

      function WordToGNZTyp(WZahl:dword):GNZTyp;     
              //Wandelt ein dWord in eine Zahl vom GNZTyp um

      function GNZTypToWord(ZahlGNZ:GNZTyp):dword;   
              //Wandelt GNZTyp in dWord um