{(c) 2008 by Alexander Staidl}

unit gnurz; 


{$mode delphi}{$H+}

interface

uses math, strutils, dialogs, sysutils;

type
  GNZTyp = array of dword;                      // Grosse-Natuerliche-Zahlen-Typ; qword: 0..18466744073709551615
  GRaZTyp = record                              // Fuer Brueche... ...sollte klar sein.
    nenner, zaehler: GNZTyp;
  end;

  TGnurz = class
    private
      GNZ_GlobZahlenbasis:dword; //Die dem GNZTyp zugrundeliegende Zahlenbasis (Binaersystem=2, Dezimal=10, Hexadezimal=16, u.s.w.); Wird im constructor create festgelegt.

      function GNZeins:GNZTyp;             //Das Einselement des GNZ-Typs
      function GNZNull:GNZTyp;             //Das Nullelement des GNZ-Typs
      function GNZZbasiswechsel(quellbasis,zielbasis:dword;Zahl:GNZTyp):GNZTyp;  //Wechselt die Basis des Zahlensystems der Zahl, z.B. von Dezimalsystem zu Binaersystem.
      function GNZistgerade(zahl:GNZTyp):boolean; //Wird fuer GNZPotenz benoetigt

    public
      constructor create;
      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;

      //Operationen: Natuerliche Zahlen
      function GNZadd(Summand1,Summand2: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; // WICHTIG: Es muss Minuend>Subtrahend sein!; Rechnet Minuend-Subtrahend.
      function GNZmul(a,b:GNZTyp):GNZTyp;  //Gibt das Produkt a*b zurueck. Rechnet mit grossen natuerlichen Zahlen.
      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;   //Wie ggt, nur fuer grosse natuerliche Zahlen (GNZ)
      function GNZkgv(a,b:GNZTyp):GNZTyp;   //Wie kgv, nur fuer GNZ
      function GNZPotenz(Basis,Exponent:GNZTyp):GNZTyp; //Gibt Zahl^Exponent zurueck. Nach einem im Internet gefundenen Algorithmus
      function GNZFakultaet(nFak:dword):GNZTyp;  // Gibt n! zurueck
      function GNZIstPrim(zahl:GNZTyp):boolean; //Wahr, wenn zahl Primzahl
      
      //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;   //Es muss a>b sein!
      function GRaZmul(a,b:GRaZTyp):GRaZTyp;                 //Multipliziert die Brueche miteinander
      function GRaZdiv(Divident,Divisor:GRaZTyp):GRaZTyp;  //Dividiert durch Multiplikation mit dem Kehrwert
      function GRaZakleinerb(a,b:GRaZTyp):boolean;      //Gibt true zurueck, wenn a kleiner b
      function GRaZagleichb(a,b:GRaZTyp):boolean;       //Gibt true zurueck, wenn a gleich b
  end;

implementation

//private
function TGnurz.GNZeins:GNZTyp;
var ZwSp:GNZTyp;
begin
  setlength(ZwSp,1);
  ZwSp[0]:=1;
  Result:=ZwSp;
end;

function TGnurz.GNZNull:GNZTyp;
var ZwSp:GNZTyp;
begin
  setlength(ZwSp,1);
  ZwSp[0]:=0;
  Result:=ZwSp;
end;

function TGnurz.GNZZbasiswechsel(quellbasis,zielbasis:dword;Zahl:GNZTyp):GNZTyp;
var Erg, quellbasGNZT, zielbasGNZT, Faktor, Exponent, eins, ZwSpGNZ:GNZTyp;     //Alle Variablen dieser Zeile im Ziel-Zahlensystem
    n, n2, ZwSp, GlobZahlenBasis_sicherung:dword;
begin
  //Hinweis: Basiswechsel erfolgt nach eigener Methode. In Wikipedia "Zahlensystem" steht eine effektivere Methode. ggf muss die Routine also umgeschrieben werden.
  //Die folgenden beiden Zeilen sind genau genommen unsauber. GNZZbasiswechsel ist die einzige Funktion, in der ausnahmsweise so vorgegangen werden darf!
  GlobZahlenBasis_sicherung:=GNZ_GlobZahlenbasis;  // Sicherung der GNZ_GlobZahlenbasis
  GNZ_GlobZahlenbasis:=zielbasis;

  eins:=GNZeins;
  setlength(ZwSpGNZ,1);
  setlength(zielbasGNZT,2);
  zielbasGNZT[0]:=0; zielbasGNZT[1]:=1;
  setlength(quellbasGNZT,1);
  setlength(Erg,1); Erg[0]:=0;
  if quellbasis<zielbasis then quellbasGNZT[0]:=quellbasis else
  begin
    quellbasGNZT[0]:=0;
    ZwSp:=quellbasis div ZielBasis;
    ZwSpGNZ[0]:=quellbasis mod ZielBasis;
    for n2:=1 to ZwSp do quellbasGNZT:=GNZadd(quellbasGNZT,zielbasGNZT);
    quellbasGNZT:=GNZadd(quellbasGNZT,ZwSpGNZ);
  end; //  -  nun ist in QuellbasGNZT die quellbasis im Zielzahlensystem gespeichert.
  for n:=0 to length(zahl)-1 do
  begin
    setlength(Exponent,1);
    setlength(Faktor,1);
    if n<zielbasis then Exponent[0]:=n else
    begin
      Exponent[0]:=0;
      ZwSp:=n div ZielBasis;
      ZwSpGNZ[0]:=n mod ZielBasis;
      for n2:=1 to ZwSp do Exponent:=GNZadd(Exponent,zielbasGNZT);
      Exponent:=GNZadd(Exponent,ZwSpGNZ);
    end;
    if Zahl[n]<zielbasis then Faktor[0]:=Zahl[n] else
    begin
      Faktor[0]:=0;
      ZwSp:=Zahl[n] div ZielBasis;
      ZwSpGNZ[0]:=Zahl[n] mod ZielBasis;
      for n2:=1 to ZwSp do Faktor:=GNZadd(Faktor,zielbasGNZT);
      Faktor:=GNZadd(Faktor,ZwSpGNZ);
    end;
    Erg:=GNZadd(Erg,GNZmul(Faktor,GNZPotenz(quellbasGNZT,Exponent)));
  end; //for 0 to length(zahl)-1
  Result:=Erg;
  GNZ_GlobZahlenbasis:=GlobZahlenBasis_sicherung; // GNZ_GlobZahlenbasis retten.
end; //GNZZbasiswechsel


function TGnurz.GNZistgerade(zahl:GNZTyp):boolean;
var n, ugz:integer;
begin
  If GNZ_GlobZahlenbasis mod 2 = 0 then
  begin
    if zahl[0] mod 2 = 0 then Result:=true else Result:=false;
  end else
  begin
    ugz:=0;
    for n:=0 to length(zahl)-1 do
    begin
      if zahl[n] mod 2 <>0 then inc(ugz);
    end;
    if ugz mod 2 = 0 then Result:=true else Result:=false;
  end;
end; //GNZistgerade


//public
constructor TGnurz.create;
begin
  inherited;
  GNZ_GlobZahlenbasis:=10;  //10=Dezimalsystem
end;


function TGnurz.StrToGNZTyp(Eingabe:string):GNZTyp;
var n:dword;
    Erg:GNZTyp;
begin
  setlength(Erg,length(Eingabe));
  for n:= 1 to length(Eingabe) do Erg[length(Eingabe)-n]:=ord(Eingabe[n])-48;
  Result:=Erg;//GNZZbasiswechsel(10,GNZ_GlobZahlenbasis,Erg);
end;  //StrToGNZTypDez


function TGnurz.GNZTypToStr(Eingabe:GNZTyp):string;
var n:dword;
    Ausgabe:string;
begin
  Ausgabe:='';
  //Eingabe:=GNZZbasiswechsel(GNZ_GlobZahlenbasis,10,Eingabe);
  for n:=1 to length(Eingabe) do Ausgabe:=Ausgabe + chr(Eingabe[length(Eingabe)-n]+48);
  Result:=Ausgabe;
end;  //GNZTypDezToStr


// GNZ-Operationen (Rechnen mit Grosse Natuerlichen Zahlen)-------------------------------------------------------

function TGnurz.GNZadd(Summand1,Summand2:GNZTyp):GNZTyp; //Zbasis=Die Zahlenbasis. Z.B. 10 fuer Dezimalsystem, 2 fuer Dualsystem, u.s.w.
var ZwSp: dword;
    n,minn,maxn: dword;
    Erg,a,b: GNZTyp;
begin
  If length(Summand1)>=length(Summand2) then
  begin
    a:=Summand1; b:=Summand2;             //Hier ist kein copy() noetig, da a,b nicht veraendert werden.
  end else
  begin
    a:=Summand2; b:=Summand1;
  end;
  maxn:=length(a); minn:=length(b);
  setlength(Erg,maxn);
  ZwSp:=0;

  for n:=0 to minn-1 do
  begin
    ZwSp:= ZwSp + a[n] + b[n];
    If ZwSp>GNZ_GlobZahlenbasis-1 then
    begin
      Erg[n]:= ZwSp-GNZ_GlobZahlenbasis;
      ZwSp:=1;
    end else
    begin
      Erg[n]:=ZwSp;
      ZwSp:=0;
    end;
  end; //for n:=0 to minn-1;
  If maxn>minn then
  begin
    for n:=minn to maxn-1 do
    begin
      ZwSp:= ZwSp + a[n];
      If ZwSp>GNZ_GlobZahlenbasis-1 then
      begin
        Erg[n]:= ZwSp-GNZ_GlobZahlenbasis;
        ZwSp:=1;
      end else
      begin
        Erg[n]:=ZwSp;
        ZwSp:=0;
      end;
    end; //for n:=minn-1 to maxn-1;
  end; // if maxn>minn
  If ZwSp<>0 then
  begin
    setlength(Erg,maxn+1);
    Erg[maxn]:=ZwSp;
  end;
  Result:=Erg;
end; // GNZadd


function TGnurz.GNZsub(Minuent,Subtrahend:GNZTyp):GNZTyp;
var ZwSp: dword;
    n,minn,maxn: dword;
    Erg,a,b: GNZTyp;
begin
  a:=Minuent; b:=Subtrahend;            //hier ist kein copy() noetig, da a und b nicht veraendert werden.
  maxn:=length(a); minn:=length(b);
  setlength(Erg,maxn);
  ZwSp:=0;

  for n:=0 to minn-1 do
  begin
    ZwSp:=ZwSp+b[n];
    If a[n]>=ZwSp then
    begin
      Erg[n]:=a[n] -ZwSp;
      ZwSp:=0;
    end else
    begin
      Erg[n]:=GNZ_GlobZahlenbasis - ZwSp + a[n];
      ZwSp:=1;
    end;
  end; //for n:=0 to minn-1;
  If maxn>minn then
  begin
    for n:=minn to maxn-1 do
    begin
      If a[n]>=ZwSp then
      begin
        Erg[n]:=a[n]-ZwSp;
        ZwSp:=0;
      end else
      begin
        Erg[n]:=GNZ_GlobZahlenbasis - ZwSp + a[n];
        ZwSp:=1;
      end;
    end; //for n:=minn-1 to maxn-1;
  end; // if maxn>minn
  n:=maxn-1;
  while (n>=1)and(Erg[n]=0) do
  begin
    dec(n);
  end; //while
  setlength(Erg,n+1);

  Result:=Erg;
end; //GNZsub


function TGnurz.GNZmul(a,b:GNZTyp):GNZTyp;
var ZwSp,Ueberschlag: dword;
    n,na,nb,aAnz,bAnz: dword;
    Erg,ZwErg: GNZTyp;
begin
  aAnz:=length(a); bAnz:=length(b);
  setlength(Erg,1);
  Erg[0]:=0;
  ZwSp:=0;
  If NOT (((aAnz=1)and(a[0]=0))or((bAnz=1)and(b[0]=0))) then
  for na:=0 to aAnz-1 do
  begin
    setlength(ZwErg,na+bAnz+1);
    for n:=0 to na do ZwErg[n]:=0;
    for nb:=0 to bAnz-1 do
    begin
      ZwSp:=a[na]*b[nb] + ZwSp;
      If ZwSp<GNZ_GlobZahlenbasis then
      begin
        ZwErg[na+nb]:=ZwSp;
        ZwSp:=0;
      end else
      begin
        Ueberschlag:=ZwSp div GNZ_GlobZahlenbasis;
        ZwErg[na+nb]:=ZwSp mod GNZ_GlobZahlenbasis;
        ZwSp:=Ueberschlag;
      end; //if zwsp<Zbasis
    end; //for bAnz
    If ZwSp<>0 then
    begin
      ZwErg[na+bAnz]:=ZwSp;
      ZwSp:=0;
    end else setlength(ZwErg,na+bAnz);
    //showmessage('|'+GNZTypToStr(ZwErg)+'|'+GNZTypToStr(Erg)+'|');
    Erg:=GNZadd(ZwErg,Erg);
  end; //for aAnz

  Result:=Erg;
end; //GNZmul


function TGnurz.GNZakleinerb(a,b:GNZTyp):boolean;
var n:dword;
    Erg: boolean;
begin
  If length(a)<>length(b) then
  begin
    if length(a)<length(b) then Erg:=true else Erg:=false;
  end else
  begin
    n:=length(a);
    repeat
      dec(n);
    until (a[n]<>b[n])or(n=0);
    If a[n]<b[n] then Erg:=true else Erg:=false;
  end;
  Result:=Erg;
end;


function TGnurz.GNZagleichb(a,b:GNZTyp):boolean;
var n:dword;
    Erg: boolean;
begin
  If length(a)<>length(b) then Erg:=false else
  begin
    n:=length(a);
    repeat
      dec(n);
    until (a[n]<>b[n])or(n=0);
    If a[n]=b[n] then Erg:=true else Erg:=false;
  end;
  Result:=Erg;
end;


function TGnurz.GNZdiv(Divident,Divisor:GNZTyp):GNZTyp;
var ZwSp:qword;
    LaengeDivident, LaengeDivisor, LaengeErg, n:dword;
    Faktor, uGrenze:dword;
    n_dent, n_sor, n_erg:longint;
    Erg, ZwSpGNZ, ProduktGNZ, DifferenzGNZ, oGrenze, Produkt, Differenz: GNZTyp;
begin
  If GNZakleinerb(Divisor,Divident) then
  begin
    LaengeDivident:=length(Divident); LaengeDivisor:=length(Divisor);
    If LaengeDivisor=1 then
    begin
      If LaengeDivident=1 then
      begin
        SetLength(Erg,1);
        Erg[0]:=Divident[0] div Divisor[0];
      end else  // LaengeDivident=1
      begin
        //Schulmethode: Schriftliche Division mit einziffrigem Divisor, geschwindigkeitsoptimiert.
        ZwSp:=0;
        n_dent:=LaengeDivident-1;                                 //zeigt auf hoechste Ziffer

        If Divident[n_dent]<Divisor[0] then
        begin
          setlength(Erg,n_dent);                                  //da n_dent=LaengeDivident-1
          ZwSp:=Divident[n_dent]*GNZ_GlobZahlenbasis;
          dec(n_dent);                                            //im Folgenden wurde n_erg durch n_dent ersetzt, da ab hier beide gleiche Werte beinhalten
        end else setlength(Erg,LaengeDivident); //if Divident[n_dent]<Divisor[0] else

        while n_dent<>0 do
        begin
          ZwSp:=ZwSp + Divident[n_dent];
          Erg[n_dent]:=ZwSp div Divisor[0];
          ZwSp := (ZwSp mod Divisor[0])*GNZ_GlobZahlenbasis;
          dec(n_dent);
        end;//while
        ZwSp:=ZwSp + Divident[0];
        Erg[0]:=ZwSp div Divisor[0];
        //ZwSp:=ZwSp mod Divisor[0]; <--- modulo
      end; //if LaengeDivident=1 else
    end else  //LaengeDivisor=1
    begin
      //Schulmethode: Schriftliche Division mit mehrziffrigem Divisor, geschwindigkeitsoptimiert.
      n:=0;
      setlength(oGrenze,1); //In Verbindung mit oGrenze gibt es hier und im Folgenden noch Optimierungspotential
      
      repeat
        inc(n);
      until (Divident[LaengeDivident-n]<>Divisor[LaengeDivisor-n])or(n=LaengeDivisor);
      If Divident[LaengeDivident-n]<Divisor[LaengeDivisor-n] then
      begin
        LaengeErg:=LaengeDivident-LaengeDivisor;
        setlength(Erg,LaengeErg);
        setlength(ZwSpGNZ,LaengeDivisor+1);
        for n:=0 to LaengeDivisor do ZwSpGNZ[n]:=Divident[LaengeErg-1+n]; //da LaengeErg=LaengeDivident-LaengeDivisor (!)
      end else
      begin
        LaengeErg:=LaengeDivident-LaengeDivisor+1;
        setlength(Erg,LaengeErg);
        setlength(ZwSpGNZ,LaengeDivisor);
        for n:=0 to LaengeDivisor-1 do ZwSpGNZ[n]:=Divident[LaengeDivident-LaengeDivisor+n];
      end; //If Divident[LaengeDivident-n]<Divisor[LaengeDivisor-n] else
      n_erg:=LaengeErg-1; n_dent:=LaengeErg-2;  //Zeigen auf vorderste noch nicht verarbeitete Ziffer
      n_sor:=LaengeDivisor-1;                   //Zeigt auf 1. Ziffer des Divisors
      
      while n_dent<>-1 do
      begin
        If length(ZwSpGNZ)=LaengeDivisor then ZwSp:=ZwSpGNZ[n_sor]
         else ZwSp:=ZwSpGNZ[LaengeDivisor]*GNZ_GlobZahlenbasis + ZwSpGNZ[n_sor];
        //ANFANG Division des Zwischenergebnisses ZwSpGNZ
        oGrenze[0]:= (ZwSp+1) div Divisor[n_sor];                         //n_sor Zeigt auf hoechste Ziffer
        uGrenze:= ZwSp div (Divisor[n_sor]+1);
        Faktor:= ((oGrenze[0]-uGrenze)*Divisor[n_sor-1]) div GNZ_GlobZahlenbasis;
        oGrenze[0]:=oGrenze[0]-Faktor;    //Der Quotient des ZwSpGNZ ist nun entweder oGrenze oder oGrenze-1.
        if oGrenze[0]>=GNZ_GlobZahlenbasis then oGrenze[0]:=GNZ_GlobZahlenbasis-1;
        Produkt:=GNZmul(oGrenze,Divisor);
        while GNZakleinerb(ZwSpGNZ, Produkt) do
        begin
          oGrenze[0]:=oGrenze[0]-1;

          Produkt:=GNZmul(oGrenze,Divisor);
        end;
        Erg[n_erg]:=oGrenze[0];
        dec(n_erg);
        //ENDE Division des Zwischenergebnisses ZwSpGNZ
        ZwSpGNZ:= GNZsub(ZwSpGNZ,Produkt);
        If (length(ZwSpGNZ)=1)and(ZwSpGNZ[0]=0) then                        //D.h. ZwSpGNZ=GNZnull
        begin
          while (n_dent<>-1)and(Divident[n_dent]=0) do
          begin
            Erg[n_erg]:=0;
            dec(n_erg);
            dec(n_dent);
          end;
          If n_dent<>-1 then
          begin
            ZwSpGNZ[0]:=Divident[n_dent];
            dec(n_dent);
          end;
        end; // If ZwSpGNZ=GNZnull
        If n_dent <> -1 then
        begin
          setlength(ZwSpGNZ,length(ZwSpGNZ)+1);
          for n:=length(ZwSpGNZ)-2 downto 0 do ZwSpGNZ[n+1]:=ZwSpGNZ[n];     //Um 1 Stelle nach links verschieben
          ZwSpGNZ[0]:=Divident[n_dent];
          dec(n_dent);
        end; // if n_dent <> -1
        while (n_dent<>-1)and(GNZakleinerb(ZwSpGNZ,Divisor)=true) do
        begin
          Erg[n_erg]:=0;
          dec(n_erg);
          setlength(ZwSpGNZ,length(ZwSpGNZ)+1);
          for n:=length(ZwSpGNZ)-2 downto 0 do ZwSpGNZ[n+1]:=ZwSpGNZ[n];     //Um 1 Stelle nach links verschieben
          ZwSpGNZ[0]:=Divident[n_dent];
          dec(n_dent);
        end; //while (n_dent<>-1)and(GNZakleinerb(ZwSpGNZ,Divisor)=true)
      end; //while n_dent<>-1
      If length(ZwSpGNZ)=LaengeDivisor then ZwSp:=ZwSpGNZ[n_sor]
       else ZwSp:=ZwSpGNZ[LaengeDivisor]*GNZ_GlobZahlenbasis + ZwSpGNZ[n_sor];
      //ANFANG Division des Zwischenergebnisses ZwSpGNZ
      oGrenze[0]:= (ZwSp+1) div Divisor[n_sor];                         //n_sor Zeigt auf hoechste Ziffer
      uGrenze:= ZwSp div (Divisor[n_sor]+1);
      Faktor:= ((oGrenze[0]-uGrenze)*Divisor[n_sor-1]) div GNZ_GlobZahlenbasis;
      oGrenze[0]:=oGrenze[0]-Faktor;    //Der Quotient des ZwSpGNZ ist nun entweder oGrenze oder oGrenze-1.
      if oGrenze[0]>=GNZ_GlobZahlenbasis then oGrenze[0]:=GNZ_GlobZahlenbasis-1;
      Produkt:=GNZmul(oGrenze,Divisor);
      while GNZakleinerb(ZwSpGNZ, Produkt) do
      begin
        oGrenze[0]:=oGrenze[0]-1;
        Produkt:=GNZmul(oGrenze,Divisor);
      end;
      Erg[n_erg]:=oGrenze[0];
      dec(n_erg);
      //ENDE Division des Zwischenergebnisses ZwSpGNZ
      //ZwSpGNZ:= GNZsub(ZwSpGNZ,Produkt); <--- modulo
    end; //if LaengeDivisor=1 else

  end else if GNZagleichb(Divisor,Divident) then Erg:=GNZeins else Erg:=GNZnull;
  Result:=Erg;
end; // GNZDiv


function TGnurz.GNZmod(Divident, Divisor:GNZTyp):GNZTyp;
begin
  Result:= GNZsub(Divident,GNZmul(GNZdiv(Divident,Divisor),Divisor));
end;


function TGnurz.GNZggt(a,b:GNZTyp):GNZTyp;   // Nach modernen Euklidischen Algorithmus
begin
  if GNZagleichb(b,GNZNull) then Result:=copy(a) else Result:=GNZggt(b, GNZmod(a,b));
end;


function TGnurz.GNZkgv(a,b:GNZTyp):GNZTyp;   // über den ggT
begin
  GNZkgv:=GNZdiv(GNZmul(a,b),GNZggt(a,b));
end;


function TGnurz.GNZPotenz(Basis,Exponent:GNZTyp):GNZTyp; //Algorithmus im Internet gefunden.
var z,e,Erg,null,eins,zwei:GNZTyp;
begin
  z:=copy(Basis);
  e:=copy(Exponent);
  Erg:=GNZeins;
  null:=GNZnull;
  eins:=GNZeins;
  zwei:=GNZadd(eins,eins);

  while GNZagleichb(e,null)=false do
  begin
    If GNZistgerade(e) then
    begin
      e:=GNZdiv(e,zwei);
      z:=GNZmul(z,z);
    end else
    begin
      e:=GNZsub(e,eins);
      Erg:=GNZmul(Erg,z);
    end;
  end; //while
  Result:=Erg;
end; //GNZPotenz


function TGnurz.GNZFakultaet(nFak:dword):GNZTyp;
var n:dword;
    Erg,ZwSpGNZ:GNZTyp;
begin
  setlength(Erg,1); Erg[0]:=1;
  setlength(ZwSpGNZ,1);
  for n:=2 to nFak do
  begin
    ZwSpGNZ[0]:=n;
    Erg:=GNZmul(ZwSpGNZ,Erg);
  end;
  Result:=Erg;
end; //GNZFakultaet

function TGnurz.GNZIstPrim(zahl:GNZTyp):boolean;
var Wurzk, Wurzkp1,GNZzwei,GNZn: GNZTyp;
    n,nbis:word;
    prim:boolean;
begin
  GNZzwei:=GNZadd(GNZeins,GNZeins);  //ist unabh. v. Zbasis
  If GNZagleichb(GNZmod(zahl,GNZzwei),GNZnull) = true then prim:=false else
  begin
    prim:=true;
    //Zunaechst wird die Wurzel von Zahl (ueber Newton-Verfahren) fuer den klassischen Primzahltest abgeschaetzt:
    nbis:=length(zahl) div 2;
    Wurzk:=GNZdiv(zahl,GNZzwei);
    for n:=0 to nbis do
    begin
      Wurzkp1:=GNZadd(Wurzk,GNZdiv(zahl,Wurzk));
      Wurzkp1:=GNZdiv(Wurzkp1,GNZzwei);
      Wurzk:=copy(Wurzkp1);
    end;
    //Klassischer Primzahltest:
    GNZn:=GNZeins;
    repeat
      GNZn:=GNZadd(GNZn,GNZzwei);
      if GNZagleichb(GNZmod(zahl,GNZn),GNZnull) = true then prim:=false;
    until (prim=false)or(GNZakleinerb(Wurzkp1,GNZn));
  end; //if
  GNZIstPrim:=prim;
end; //GNZIstPrim


//GRaZ-Operatonen - Rechnen mit grossen Rationalen Zahlen  ---------------------------------------------------


function TGnurz.GRaZKuerzen(Bruch:GRaZTyp):GRaZTyp;
var ZwSpGNZ:GNZTyp;
begin
  //Eventuelles Kuerzen:
  ZwSpGNZ:=GNZggt(Bruch.nenner,Bruch.zaehler);
  If (length(ZwSpGNZ)=1)and(ZwSpGNZ[0]=1) then Result:=Bruch else
  begin
    Result.zaehler:=GNZdiv(Bruch.zaehler,ZwSpGNZ);
    Result.nenner:=GNZdiv(Bruch.nenner,ZwSpGNZ);
  end;
end;


function TGnurz.GRaZadd(a,b:GRaZTyp):GRaZTyp;
var ZwSpGNZ:GNZTyp;
    Erg:GRaZTyp;
begin
  ZwSpGNZ:=GNZkgv(a.nenner,b.nenner);     //Brueche auf einen Nenner bringen...
  Erg.nenner:=ZwSpGNZ;
  Erg.zaehler:=GNZadd(GNZmul(a.zaehler,GNZdiv(ZwSpGNZ,a.nenner)),GNZmul(b.zaehler,GNZdiv(ZwSpGNZ,b.nenner)));
  Result:=GRaZKuerzen(Erg);
end; //GRaZadd


function TGnurz.GRazsub(Minuent,Subtrahend:GRaZTyp):GRaZTyp;   //Es muss Minuent>Subtrahend sein!
var ZwSpGNZ:GNZTyp;
    Erg:GRaZTyp;
begin
  ZwSpGNZ:=GNZkgv(Minuent.nenner,Subtrahend.nenner);     //Brueche auf einen Nenner bringen...
  Erg.nenner:=ZwSpGNZ;
  Erg.zaehler:=GNZsub(GNZmul(Minuent.zaehler,GNZdiv(ZwSpGNZ,Minuent.nenner)),GNZmul(Subtrahend.zaehler,GNZdiv(ZwSpGNZ,Subtrahend.nenner)));
  Result:=GRaZKuerzen(Erg);
end; //GRaZsub


function TGnurz.GRaZmul(a,b:GRaZTyp):GRaZTyp;
var Erg:GRaZTyp;
begin
  Erg.zaehler:=GNZmul(a.zaehler,b.zaehler);
  Erg.nenner:=GNZmul(a.nenner,b.zaehler);
  Result:=GRaZKuerzen(Erg);
end; //GRaZmul


function TGnurz.GRaZdiv(Divident,Divisor:GRaZTyp):GRaZTyp;
var Erg:GRaZTyp;
begin
  Erg.zaehler:=GNZmul(Divident.zaehler,Divisor.nenner);
  Erg.nenner:=GNZmul(Divident.nenner,Divisor.zaehler);
  Result:=GRaZKuerzen(Erg);
end; //GRaZdiv


function TGnurz.GRaZakleinerb(a,b:GRaZTyp):boolean;
var ZwSpGNZ:GNZTyp;
begin
  ZwSpGNZ:=GNZkgv(a.nenner,b.nenner);
  Result:=GNZakleinerb(GNZmul(a.zaehler,GNZdiv(ZwSpGNZ,a.nenner)),GNZmul(b.zaehler,GNZdiv(ZwSpGNZ,b.nenner)));
end; //GRaZakleinerb


function TGnurz.GRaZagleichb(a,b:GRaZTyp):boolean;
var ZwSpGNZ:GNZTyp;
begin
  ZwSpGNZ:=GNZkgv(a.nenner,b.nenner);
  Result:=GNZagleichb(GNZmul(a.zaehler,GNZdiv(ZwSpGNZ,a.nenner)),GNZmul(b.zaehler,GNZdiv(ZwSpGNZ,b.nenner)));
end; //GRaZagleichb


end.