Große Ganzzahlen

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
heizkoerper
Beiträge: 24
Registriert: Mo 1. Aug 2011, 14:39
OS, Lazarus, FPC: Windows XP und 7, L 0.9.31, FPC 2.4.4
CPU-Target: 32 und 64 Bit
Wohnort: Hannover
Kontaktdaten:

Große Ganzzahlen

Beitrag von heizkoerper »

Hallo Lazarusfreunde,

es wurde ja schon oft das Thema angesprochen, wie man mit sehr großen Ganzzahlen rechnen kann.

Ich habe ein Unit entwickelt, mit welchem das möglich ist.

Alle Zahlen und Ergebnisse werden in Strings abgespeichert.

Mit diesen Algorithmen ist es nun ein einfaches erweiterte Algorithmen wie z.B. für große Fakultäten, kgV, ggT zu entwickeln.

Auch Primzahlen ließen sich berechnen. Dies ist aber nur theoretisch möglich, weil sehr große Primzahlen jegliche Rechenzeit springen.

Hir nun die Unit:

Code: Alles auswählen

Unit StringMathe;
 
Interface
 
Function AdditionInteger(Zahl1,Zahl2:String):String;
Function SubtraktionInteger(Zahl1,Zahl2:String):String;
Function MultiplikationInteger(Zahl1,Zahl2:String):String;
Function DivisionInteger(Zahl1,Zahl2:String):String;
Function ModuloInteger(Zahl1,Zahl2:String):String;
 
Implementation
 
Const MaxLaenge     =500;
      ErgebnisFehler=1E2000;
 
Var   MaxInt64:Int64;
 
Function ValueInteger(s:String):Extended;
Var Fehler:Integer;
    Zahl  :Extended;
Begin
 Val(s,Zahl,Fehler);
 If Fehler<>0 Then ValueInteger:=ErgebnisFehler
              Else ValueInteger:=Int(Zahl)
End;
 
Function VorzeichenErgaenzenInteger(s:String):String;
Begin
 If s[1]='+' Then s[1]:=' ';
 If (s[1]>='0') And (s[1]<='9') Then s:=' '+s;
 VorzeichenErgaenzenInteger:=s
End;
 
Function AbsolutInteger(s:String):String;
Begin
 If (s[1]='+') Or (s[1]='-') Then s[1]:=' ';
 AbsolutInteger:=s
End;
 
Function StringVerkuerzenInteger(s:String):String;
Var i:Integer;
    h:String;
    c:Char;
Begin
 c:=s[1];i:=2;
 While s[i]='0' Do Inc(i);
 h:=c+Copy(s,i,Length(s)-i+1);
 If (h=' ') Or (h='+') Or (h='-') Then h:=' 0';
 If h='-0' Then h:=' 0';
 StringVerkuerzenInteger:=h
End;
 
Function StringVerlaengernInteger(s,Null:String):String;
Begin
 StringVerlaengernInteger:=s[1]+Copy(Null,1,Length(Null)-Length(s)+1)+
  Copy(s,2,Length(s))
End;
 
Function Replicate(s:Char;WieOft:Integer):String;
Var i:Integer;
    t:String;
Begin
 t:='';
 For i:=1 To WieOft Do t:=t+s;
 Replicate:=t
End;
 
Function GroesserInteger(s1,s2:String):Boolean;
Begin
 s1:=StringVerkuerzenInteger(s1);s2:=StringVerkuerzenInteger(s2);
 If s1=s2 Then Begin GroesserInteger:=False;Exit End;
 If (s1[1]=' ') And (s2[1]='-') Then Begin GroesserInteger:=True;Exit End;
 If (s1[1]='-') And (s2[1]=' ') Then Begin GroesserInteger:=False;Exit End;
 If (s1[1]=' ') And (s2[1]=' ') Then
  Begin
   If Length(s1)>Length(s2) Then Begin GroesserInteger:=True;Exit End;
   If Length(s1)<Length(s2) Then Begin GroesserInteger:=False;Exit End;
   If s1>s2 Then Begin GroesserInteger:=True;Exit End;
   GroesserInteger:=False;Exit
  End;
 If (s1[1]='-') And (s2[1]='-') Then
  Begin
   If Length(s1)>Length(s2) Then Begin GroesserInteger:=False;Exit End;
   If Length(s1)<Length(s2) Then Begin GroesserInteger:=True;Exit End;
   If s1>s2 Then Begin GroesserInteger:=False;Exit End;
   GroesserInteger:=True;Exit
  End;
 GroesserInteger:=False
End;
 
Function KleinerInteger(s1,s2:String):Boolean;
Begin
 s1:=StringVerkuerzenInteger(s1);s2:=StringVerkuerzenInteger(s2);
 If s1=s2 Then Begin KleinerInteger:=False;Exit End;
 If (s1[1]='-') And (s2[1]=' ') Then Begin KleinerInteger:=True;Exit End;
 If (s1[1]=' ') And (s2[1]='-') Then Begin KleinerInteger:=False;Exit End;
 If (s1[1]=' ') And (s2[1]=' ') Then
  Begin
   If Length(s1)<Length(s2) Then Begin KleinerInteger:=True;Exit End;
   If Length(s1)>Length(s2) Then Begin KleinerInteger:=False;Exit End;
   If s1<s2 Then Begin KleinerInteger:=True;Exit End;
   KleinerInteger:=False;Exit
  End;
 If (s1[1]='-') And (s2[1]='-') Then
  Begin
   If Length(s1)<Length(s2) Then Begin KleinerInteger:=False;Exit End;
   If Length(s1)>Length(s2) Then Begin KleinerInteger:=True;Exit End;
   If s1<s2 Then Begin KleinerInteger:=False;Exit End;
   KleinerInteger:=True;Exit
  End;
 KleinerInteger:=False
End;
 
Function GleichInteger(s1,s2:String):Boolean;
Begin
 s1:=StringVerkuerzenInteger(s1);s2:=StringVerkuerzenInteger(s2);
 If s1=s2 Then GleichInteger:=True Else GleichInteger:=False
End;
 
Function AdditionInteger(Zahl1,Zahl2:String):String;
Var Ergebnis,Null:String;
    i,z,CF       :Integer;
    Vz1,Vz2,Vz   :Boolean;
    z1,z2,e      :Int64;
Begin
 AdditionInteger:='?';
 If (Length(Zahl1)<1) Or (Length(Zahl2)<1) Or (Zahl1='?') Or (Zahl2='?') Then Exit;
 If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
 If Not(ValueInteger(Zahl2)<ErgebnisFehler) Then Exit;
 Zahl1:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl1));
 Zahl2:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl2));
 If ValueInteger(Zahl1)=0 Then Begin AdditionInteger:=Zahl2;Exit End;
 If ValueInteger(Zahl2)=0 Then Begin AdditionInteger:=Zahl1;Exit End;
 If (ValueInteger(AbsolutInteger(Zahl1))<MaxInt64 Div 2) And
    (ValueInteger(AbsolutInteger(Zahl2))<MaxInt64 Div 2) Then
  Begin
   z1:=Trunc(ValueInteger(Zahl1));z2:=Trunc(ValueInteger(Zahl2));e:=z1+z2;
   Str(e,Ergebnis);AdditionInteger:=VorzeichenErgaenzenInteger(Ergebnis);Exit
  End;
 If Zahl1[1]='-' Then Vz1:=True Else Vz1:=False;
 If Zahl2[1]='-' Then Vz2:=True Else Vz2:=False;
 If Length(Zahl1)>=Length(Zahl2) Then Null:=Replicate('0',Length(Zahl1))
                                 Else Null:=Replicate('0',Length(Zahl2));
 CF:=0;Ergebnis:=' '+Null;Vz:=False;
 Zahl1:=AbsolutInteger(StringVerlaengernInteger(Zahl1,Null));
 Zahl2:=AbsolutInteger(StringVerlaengernInteger(Zahl2,Null));
 If (Vz1 And Not(Vz2)) Or (Vz2 And Not(Vz1)) Then
  Begin
   Ergebnis:=SubtraktionInteger(Zahl1,Zahl2);
   If GroesserInteger(Zahl2,Zahl1) Then If Vz2 Then Vz:=True
                                               Else
                                   Else If Vz1 Then Vz:=True
  End
                                             Else
  Begin
   If Vz1 And Vz2 Then Vz:=True;
   For i:=Length(Zahl1) DownTo 2 Do
    Begin
     z:=Ord(Zahl1[i])+Ord(Zahl2[i])-2*Ord('0')+CF;
     If z>=10 Then Begin Dec(z,10);CF:=1 End Else CF:=0;
     Ergebnis[i]:=Chr(z+Ord('0'))
    End
  End;
 Ergebnis:=StringVerkuerzenInteger(Ergebnis);
 If (ValueInteger(Ergebnis)<>0) And Vz Then Ergebnis[1]:='-' Else Ergebnis[1]:=' ';
 AdditionInteger:=Ergebnis
End;
 
Function SubtraktionInteger(Zahl1,Zahl2:String):String;
Var Ergebnis,Null:String;
    i,z,BF       :Integer;
    Vz1,Vz2,Vz   :Boolean;
    z1,z2,e      :Int64;
Begin
 SubtraktionInteger:='?';
 If (Length(Zahl1)<1) Or (Length(Zahl2)<1) Or (Zahl1='?') Or (Zahl2='?') Then Exit;
 If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
 If Not(ValueInteger(Zahl2)<ErgebnisFehler) Then Exit;
 Zahl1:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl1));
 Zahl2:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl2));
 If Zahl1[1]='-' Then Vz1:=True Else Vz1:=False;
 If Zahl2[1]='-' Then Vz2:=True Else Vz2:=False;
 If ValueInteger(Zahl1)=0 Then
  Begin
   If (ValueInteger(Zahl2)=0) Or Vz2 Then Zahl2[1]:=' ' Else Zahl2[1]:='-';
   SubtraktionInteger:=Zahl2;Exit
  End;
 If ValueInteger(Zahl2)=0 Then Begin SubtraktionInteger:=Zahl1;Exit End;
 If (ValueInteger(AbsolutInteger(Zahl1))<MaxInt64 Div 2) And
    (ValueInteger(AbsolutInteger(Zahl2))<MaxInt64 Div 2) Then
  Begin
   z1:=Trunc(ValueInteger(Zahl1));z2:=Trunc(ValueInteger(Zahl2));e:=z1-z2;
   Str(e,Ergebnis);SubtraktionInteger:=VorzeichenErgaenzenInteger(Ergebnis);Exit
  End;
 If Length(Zahl1)>=Length(Zahl2) Then Null:=Replicate('0',Length(Zahl1))
                                 Else Null:=Replicate('0',Length(Zahl1));
 BF:=0;Ergebnis:=' '+Null;Vz:=False;
 Zahl1:=AbsolutInteger(StringVerlaengernInteger(Zahl1,Null));
 Zahl2:=AbsolutInteger(StringVerlaengernInteger(Zahl2,Null));
 If (Vz1 And Not(Vz2)) Or (Vz2 And Not(Vz1)) Then
  Begin
   Ergebnis:=AdditionInteger(Zahl1,Zahl2);
   If Vz1 Then Vz:=True
  End
                                             Else
  Begin
   If GroesserInteger(Zahl2,Zahl1) Then
    Begin
     Ergebnis:=Zahl1;Zahl1:=Zahl2;Zahl2:=Ergebnis;Ergebnis:=' '+Null;
     If Not(Vz1) And Not(Vz2) Then Vz:=True
    End
                                   Else If Vz1 and Vz2 Then Vz:=True;
   For i:=Length(Zahl1) DownTo 2 Do
    Begin
     z:=Ord(Zahl1[i])-Ord(Zahl2[i])-BF;
     If z<0 Then Begin Inc(z,10);BF:=1 End Else BF:=0;
     Ergebnis[i]:=Chr(z+Ord('0'))
    End
  End;
 Ergebnis:=StringVerkuerzenInteger(Ergebnis);
 If (ValueInteger(Ergebnis)<>0) And Vz Then Ergebnis[1]:='-' Else Ergebnis[1]:=' ';
 SubtraktionInteger:=Ergebnis
End;
 
Function MultiplikationInteger(Zahl1,Zahl2:String):String;
Var i,l,z,CF       :Integer;
    t,Ergebnis,Null:String;
    Vz1,Vz2        :Boolean;
    z1,z2,e        :Int64;
Begin
 MultiplikationInteger:='?';
 If (Length(Zahl1)<1) Or (Length(Zahl2)<1) Or (Zahl1='?') Or (Zahl2='?') Then Exit;
 If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
 If Not(ValueInteger(Zahl2)<ErgebnisFehler) Then Exit;
 Zahl1:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl1));
 Zahl2:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl2));
 If Length(Zahl1)+Length(Zahl2)>MaxLaenge*2 Then Exit;
 If (ValueInteger(Zahl1)=0) Or (ValueInteger(Zahl2)=0) Then
  Begin MultiplikationInteger:=' 0';Exit End;
 If (ValueInteger(AbsolutInteger(Zahl1))<MaxIntSqrt64) And
    (ValueInteger(AbsolutInteger(Zahl2))<MaxIntSqrt64) Then
  Begin
   z1:=Trunc(ValueInteger(Zahl1));z2:=Trunc(ValueInteger(Zahl2));e:=z1*z2;
   Str(e,Ergebnis);MultiplikationInteger:=VorzeichenErgaenzenInteger(Ergebnis);Exit
  End;
 If Zahl1[1]='-' Then Vz1:=True Else Vz1:=False;
 If Zahl2[1]='-' Then Vz2:=True Else Vz2:=False;
 Null:=Replicate('0',Length(Zahl1)+Length(Zahl2)-1);CF:=0;Ergebnis:=' '+Null;
 If Length(Zahl2)>Length(Zahl1) Then
  Begin Ergebnis:=Zahl1;Zahl1:=Zahl2;Zahl2:=Ergebnis;Ergebnis:=' '+Null End;
 If ValueInteger(AbsolutInteger(Zahl1))=1 Then Ergebnis:=Zahl2
                                          Else
  Begin
   If ValueInteger(AbsolutInteger(Zahl2))=1 Then Ergebnis:=Zahl1
                                            Else
   Begin
    For i:=Length(Zahl2) DownTo 2 Do
     Begin
      t:=' '+Null;
      For l:=Length(Zahl1) DownTo 2 Do
       Begin
        z:=(Ord(Zahl1[l])-Ord('0'))*(Ord(Zahl2[i])-Ord('0'))+CF;
        If z>=10 Then Begin CF:=z Div 10;z:=z Mod 10 End Else CF:=0;
        t[i+l]:=Chr(z+Ord('0'))
       End;
      t[i+1]:=Chr(CF+Ord('0'));CF:=0;Ergebnis:=AdditionInteger(Ergebnis,t)
     End
   End
  End;
 Ergebnis:=StringVerkuerzenInteger(Ergebnis);
 If (ValueInteger(Ergebnis)<>0) And
    ((Vz1 And Not(Vz2)) Or (Not(Vz1) And Vz2)) Then Ergebnis[1]:='-' Else Ergebnis[1]:=' ';
 MultiplikationInteger:=Ergebnis
End;
 
Function DivisionInteger(Zahl1,Zahl2:String):String;
Var i                :Integer;
    t,Ergebnis,Null,z:String;
    Vz1,Vz2          :Boolean;
    z1,z2,e          :Int64;
Begin
 DivisionInteger:='?';
 If (Length(Zahl1)<1) Or (Length(Zahl2)<1) Or (Zahl1='?') Or (Zahl2='?') Then Exit;
 If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
 If Not(ValueInteger(Zahl2)<ErgebnisFehler) Then Exit;
 Zahl1:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl1));
 Zahl2:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl2));
 If (Length(Zahl1)-Length(Zahl2)>MaxLaenge) Or (ValueInteger(Zahl2)=0) Then Exit;
 If GroesserInteger(AbsolutInteger(Zahl2),AbsolutInteger(Zahl1)) Or
   (ValueInteger(Zahl1)=0) Then Begin DivisionInteger:=' 0';Exit End;
 If Zahl1[1]='-' Then Vz1:=True Else Vz1:=False;
 If Zahl2[1]='-' Then Vz2:=True Else Vz2:=False;
 Null:=Replicate('0',Length(Zahl1));Ergebnis:=' ';
 Zahl1:=AbsolutInteger(StringVerlaengernInteger(Zahl1,Null));
 Zahl2:=AbsolutInteger(Zahl2);
 If Zahl1=Zahl2 Then Ergebnis:=' 1'
                Else
  If ValueInteger(Zahl2)=1 Then Ergebnis:=Zahl1
                           Else
   Begin
    If (ValueInteger(AbsolutInteger(Zahl1))<MaxInt64) And
       (ValueInteger(AbsolutInteger(Zahl2))<MaxInt64) Then
     Begin
      z1:=Trunc(ValueInteger(Zahl1));z2:=Trunc(ValueInteger(Zahl2));e:=z1 Div z2;
      Str(e,Ergebnis);DivisionInteger:=VorzeichenErgaenzenInteger(Ergebnis);Exit
     End;
    For i:=Length(Zahl2) To Length(Zahl1) Do
     Begin
      t:=Copy(Zahl1,1,i);z:=' 0';
      If GroesserInteger(t,Zahl2) Or GleichInteger(t,Zahl2) Then
       Begin
        Repeat
         t:=SubtraktionInteger(t,Zahl2);z:=AdditionInteger(z,' 1')
        Until KleinerInteger(t,Zahl2);
        t:=MultiplikationInteger(z,Zahl2);
        While KleinerInteger(t+'0',Zahl1) Or GleichInteger(t+'0',Zahl1) Do t:=t+'0';
        Zahl1:=StringVerlaengernInteger(SubtraktionInteger(Zahl1,t),Null)
       End;
      Ergebnis:=Ergebnis+z[2]
     End
   End;
 Ergebnis:=StringVerkuerzenInteger(Ergebnis);
 If (ValueInteger(Ergebnis)<>0) And
    ((Vz1 And Not(Vz2)) Or (Not(Vz1) And Vz2)) Then Ergebnis[1]:='-' Else Ergebnis[1]:=' ';
 DivisionInteger:=Ergebnis
End;
 
Function ModuloInteger(Zahl1,Zahl2:String):String;
Var Ergebnis:String;
    z1,z2,e :Int64;
Begin
 ModuloInteger:='?';
 If (Length(Zahl1)<1) Or (Length(Zahl2)<1) Or (Zahl1='?') Or (Zahl2='?') Then Exit;
 If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
 If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
 If ValueInteger(Zahl2)=0 Then Exit;
 Zahl1:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl1));
 Zahl2:=StringVerkuerzenInteger(VorzeichenErgaenzenInteger(Zahl2));
 If GleichInteger(AbsolutInteger(Zahl1),AbsolutInteger(Zahl2)) Then
  Begin ModuloInteger:=' 0';Exit End;
 If GroesserInteger(AbsolutInteger(Zahl2),AbsolutInteger(Zahl1)) Then
  Begin ModuloInteger:=Zahl1;Exit End;
 If (ValueInteger(AbsolutInteger(Zahl1))<MaxInt64) And
    (ValueInteger(AbsolutInteger(Zahl2))<MaxInt64) Then
  Begin
   z1:=Trunc(ValueInteger(Zahl1));z2:=Trunc(ValueInteger(Zahl2));e:=z1 Mod z2;
   Str(e,Ergebnis);ModuloInteger:=VorzeichenErgaenzenInteger(Ergebnis);Exit
  End;
 Ergebnis:=SubtraktionInteger(Zahl1,MultiplikationInteger(DivisionInteger(Zahl1,Zahl2),Zahl2));
 ModuloInteger:=Ergebnis
End;
 
Begin MaxInt64:=Trunc(9E18) End.


Viel Spaß beim ausprobieren.

Gruß Heizkoerper

P.S. Auf meiner sehr sporadischen Webseite (http://www.wweeke.de) ist das Programm Langzahlen mit dieser Unit entwickelt worden.
Zuletzt geändert von Lori am Do 11. Apr 2013, 15:32, insgesamt 1-mal geändert.
Grund: Bitte den Highlighter nutzen

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: Große Ganzzahlen

Beitrag von mschnell »

heizkoerper hat geschrieben:Alle Zahlen und Ergebnisse werden in Strings abgespeichert.


Werden die Werte binär in den Strings abgespeichert (als Ketten von 32 oder besser 64 Bit Integers) oder als lesbare Zahlen (als dezimaler oder hexadezimaler ASCII Text) ? ( Nach erstem Hinsehen als Text :( . )

Im zweiten Fall ist die Performance naturgemäß grauenhaft. Somit ist das als Übungs- / Demo- Projekt sicherlich eine nette Sache sollte aber praktisch nicht eingesetzt werden.

Nach meiner Erfahrung macht es für die Praxis wenig Sinn, eine Langzahlen-Arithmetik komplett neu zu schreiben. Es gibt da sehr performante und gut getestete Libraries in C, die man gut mit {$L... } oder als DLL / .so einbinden kann. Da die innersten Schleifen zudem idealer Weise in Assembler geschrieben werden sollten (und damit völlig unterschiedlich für 32 und 64 Bit Compiler und auch speziell für ARM-Architektur notwendig), sollte eine Library ausgesucht werden, die das so macht.

Ein solches Projekt (Einbinden einer C-Library und optimales nutzbar machen der Funktionalität mit FPC-Mitteln (Operator Overloading und automatisches Erzeugen der Variablen mit dynamischer Memory-Zuweisung z.B. per "interface" mit Reference-Counting) wäre ein wirklich lohnendes Projekt

-Michael

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

Re: Große Ganzzahlen

Beitrag von indianer-frank »

heizkoerper hat geschrieben:Auch Primzahlen ließen sich berechnen. Dies ist aber nur theoretisch möglich, weil sehr große Primzahlen jegliche Rechenzeit springen.
Verstehe nicht, was Du uns damit sagen willst!? Es ist doch wurscht, ob die Zahlen mit den man rechnet Primzahlen sind oder nicht! Außerdem ist doch Dein Wert MaxLaenge=500; für Langzahlen lächerlich klein, was soll denn da Rechenzeiten sprengen?

Im übrigen sind noch einige Bugs im Code, zB
- Deklaration und Wertzuweisung für MaxIntSqrt64 fehlen (Unit kann nicht übersetzt werden)
- Funktion ModuloInteger zweimal:

Code: Alles auswählen

If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit;
If Not(ValueInteger(Zahl1)<ErgebnisFehler) Then Exit

Außerdem solltest Du Deinen Beitrag editieren und Pascal-Tags setzen, damit man halbwegs eine Chance hat, den Code ohne Augenkrebsgefahr anzuschauen.

Horst_h
Beiträge: 72
Registriert: Mi 20. Mär 2013, 08:57

Re: Große Ganzzahlen

Beitrag von Horst_h »

Hallo,

Gute Güte, seit doch nett zueinander.Das hilft keinem was und schreckt nur ab.
heizkoerper ist sicher stolz auf seine Leistung und es ist auch anschaulich, wie er vorgegangen ist und auch für andere von Interesse.Das es nicht das schnellste ist, tut ja nichts zur Sache, hat er auch nicht behauptet.
Hier ist ja nicht das debian shootout Benchmark game
http://benchmarksgame.alioth.debian.org/u32/pascal.php
So super toll sieht freepascal da nicht aus, auch wenn es etwas Speicherplatz spart.Aber eben meist schnell genug.
Da sieht man bei pidigits das einbinden von GMP

Code: Alles auswählen

{ The Computer Language Benchmarks Game
  contributed by Vincent Snijders
  gmp headers by Karl-Michael Schindler
}

 
{$linklib libgmp.so}
{$mode objfpc}
 
program pidigits;


Deshalb ist dort das Programm so schnell wie anderen, die gmp nutzen.

Gruß Horst

Thomas B.
Beiträge: 90
Registriert: Fr 2. Nov 2007, 13:32
OS, Lazarus, FPC: Win (L 1.0 FPC 2.6.0)
CPU-Target: 32Bit
Wohnort: Ulm

Re: Große Ganzzahlen

Beitrag von Thomas B. »

Dem was Horst geschrieben hat, kann ich mich nur anschließen. Jeder von uns hat mit dem Programmieren mal klein angefangen.

Ich persönlich nutze die GNURZ-Bibliothek (mit ein paar Erweiterungen für Matrizen). Vielleicht wäre die als Vergleich/Anregung für Dich interessant.

Socke
Lazarusforum e. V.
Beiträge: 3158
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Große Ganzzahlen

Beitrag von Socke »

Thomas B. hat geschrieben:Dem was Horst geschrieben hat, kann ich mich nur anschließen. Jeder von uns hat mit dem Programmieren mal klein angefangen.

Vor allem ist diese Aufgabe unter Lehrern sehr beliebt. Das ganze sich so zu überlegen, dass es am Ende auch funktioniert, ist für die meisten Schüler nichts, was sie mal eben nebenbei machen. Ich selbst hab sowas nie gemacht :oops:
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

heizkoerper
Beiträge: 24
Registriert: Mo 1. Aug 2011, 14:39
OS, Lazarus, FPC: Windows XP und 7, L 0.9.31, FPC 2.4.4
CPU-Target: 32 und 64 Bit
Wohnort: Hannover
Kontaktdaten:

Re: Große Ganzzahlen

Beitrag von heizkoerper »

Hallo,

mit so einer Resonanz habe ich nicht gerechnet.

Ich möchte wie folgt Stellung nehmen:

Die Variable MaxIntSqrt64 fehlt. Meine Schuld. Wird diese deklariert und mit Trunc(3E9) belegt, ist alles in Ordnung.

Die Variablen MaxInt64 und MaxIntSrqt64 sind nur Kontrollwerte, damit es bei Int64 keinen Überlauf gibt.

Passen die Langzahlen in Int64 werden die Int64-Algorithmen benutzt. Sins die Zahlen größer kommen die String-Algorithmen zum Einsatz.

Bei der Function ModuloInteger muss es natürlich anstatt If Not(ValueInteger(Zahl1)<ErgebnisFehler) ..Zahl2.. heissen. Danke für den Hinweis.

Generell ist die Länge der Zahlen nur durch den großen Stringtypen begrenzt. Dieser ist bei 32 bit auf 2 GByte begrenzt. Auch für lange Zahlen müsste dies gerade
noch ausreichend sein.

Die Konstante MaxLaenge=500 ist nur vorhanden, um bei der Multiplikation und gerade bei der Division die maximale Rechenzeit zu begrenzen. Diese
Konstante kann natürlich vergrößert werden oder sogar ganz verschwinden. Aber Zahlen mit 500 Stellen finde ich auch nicht gerade klein.

Nun zu den geliebten Primzahlen. Es geht nicht darum mit Primzahlen zu rechnen, sondern zu testen, ob eine Zahl eine Primzahl ist oder nicht, bzw.
selbst große Primzahlen zu berechnen, wie sie z.B. bei der RSA-Verschlüsselung gebraucht werden.

Haben Zahlen eine Länge von mehreren hundert Stellen ist dieser Primzahltest praktisch aus Zeitgründen nicht mehr durchführbar.

Ich programmiere generell aus Spaß an der Freude und alles selber. Mir ist auch bekannt, dass es bessere und vor allem schnellere Algorithmen für diese Problenstellung gibt.
Selbst zu programmieren ist für mich aber allemal befriedigender als fertige Bibliotheken einzubinden.

Das war es für heute.

Gruß Heizkoerper

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: Große Ganzzahlen

Beitrag von Euklid »

heizkoerper hat geschrieben:Nun zu den geliebten Primzahlen. Es geht nicht darum mit Primzahlen zu rechnen, sondern zu testen, ob eine Zahl eine Primzahl ist oder nicht, bzw.
selbst große Primzahlen zu berechnen, wie sie z.B. bei der RSA-Verschlüsselung gebraucht werden.

Haben Zahlen eine Länge von mehreren hundert Stellen ist dieser Primzahltest praktisch aus Zeitgründen nicht mehr durchführbar.


Das klassische Berechnen von Primzahlen ist in der Tat seeehr aufwändig. Daher wurden von einigen Mathematikern Algorithmen zur Beschleunigung entwickelt. Ziemlich genial und auch für mathematisch versierte "Laien" nachzuvollziehen ist der sogenannte Miller-Rabin-Test.. Der zugehörige Wikipedia-Artikel zeigt die Funktionsweise. Auch die GNURZ verwendet den Algorithmus für besonders große Zahlen; für kleinere wird der Test klassisch durchgeführt.

Viele Grüße, Euklid

Antworten