Extem grosse Zahlen, über 1000 Stellen

[Mathias]

Angenommen, man will zB. ein Mandelbrot extrem tief berechnen. Da ist man mit einem 64Bit Float extrem schnell am Anschlag.
Was mir für eine solches Problem bekannt ist, man muss die Zahlen in eine Zeichenkette/String packen.
Und so etwas geht natürlich sehr langsam, da man Zeichen für Zeichen durcharbeiten muss, auch wen man mit Ganzzahlen rechnet.
Da ist mir der Gedanke gekommen, ob man für solche Zwecke auch die MMX/SSE Einheit der CPU nutzen könnte.

Hat einer von euch von so etwas schon gehört ?

Was ich mal gemacht hatte, die GPU für eine Mandelbrot Berechnung zu nutzen, aber da war bei 32Bit Tiefe auch Schluss. Einziger Vorteil der GPU gegenüber der CPU war, es war extrem schnell.

[Warf]

Naja, es die GMP (GNU Multi Precision Arithmetic Library) für die es auch FPC bindings gibt (mit überladenen Operatoren und allem drum und dran). Die kann verschiedene Datentypen (Ganzzahlen, Rationale Zahlen, Fixkommazahlen) und ist von vorn bis hinten durchoptimiert mit verschiedenen Assembly funktionen für verschiedene CPU typen optimiert.

Soweit ich weis gilt sie als effizienteste Bibliothek ihrer Art und ist komplett OpenSource. Wenn ich was mit großen Zahlen mache (e.g. Kryptographie) benutz ich immer einfach die GMP

[Winni]

Hi!

Es gab mal ne unit mit BCD - Binary Coded Digits.
Mit beliegiger Länge.
Das Paket hiess FMTBCD. Ich wundere mich gerade, dass ich es unter fpc 3.2 nicht finden kann.

Hier ist schonmal ein Link:

https://wiki.lazarus.freepascal.org/BcdUnit


Winni

[Mathias]

Link ist leider Tod.

[TSchnuckenbock]

Probier den Link mal so

https://wiki.lazarus.freepascal.org/BcdUnit

[TSchnuckenbock]

@Warf, welches Pascal-Binding setzt du denn für die GMP ein?

Was ich gefunden habe ist

https://gmplib.org/manual/Language-Bindings

und da scheinen mir auf den ersten Blick die Pascal-Bindings recht alt.

[shokwave]

Ich glaube das ist beim FPC schon mit drin.

https://wiki.freepascal.org/gmp

[Soner]

Diese Frage wurde schonmal im englischen Forum gestellt und Lösungen vorgeschlagen, vielleicht solltest du dort suchen.

Aber wenn du es selber machen möchtest, dann kannst du aus richtigen Zahlen-Typen, Float, Integer o.ä. Zahlenblöcke zusammenstellen und damit rechnen. Das würde viel schneller als Stringlösung sein und wahrscheinlich kaum bemerkbar langsamer sein.

Ich füge mal ein Bespiel was ich meine. Im Beispiel kann man mit zwei Byte-Variablen zahlen von 0..9999 darstellen und darstellen. Mit diesem Vorgehen kannst du dann unendlich große Zahlen darstellen und rechnen:

Code: Alles auswählen

program Project1;

{$mode objfpc}{$H+}

uses Classes, SysUtils;

type
  TZahl = record    // Darstellbare zahlen 0..9999 (z2=00..99, z1=00.99)
    z1, z2 : Byte; //das sollte man dyn. Array machen
                   //hier ist z1=0.100 un z2=
    //bloecke: Byte; //verwendete blöcke, in diesem beispiel nicht verwendet
                   //aber man könnte anzahl der verwendeten Zahlenblöcke/Arraygröße
                   //hier speichern

  end;

var a,b,c: TZahl;
     i: integer;
begin
  //a soll 999 darstellen
  a.z1:=99;
  a.z2:=9;
  //a.bloecke:=2;

  //b soll 9 darstellen
  b.z1:=9;
  b.z2:=0;
  //a.bloecke:=1;

  // c:=a+b  ==> 1008 ==> c.z1=08 und c.z2:=10
  i:=a.z1+b.z1; //108

  if i>99 then begin
    c.z1:=i-100; //8
    c.z2:=1;
  end
  else begin
    c.z1:=i;
    c.z2:=0;
  end;

  c.z2:=c.z2+a.z2+b.z2;
  writeln(c.z2,Format('%.02d',[c.z1]));
  readln;
end.

[TSchnuckenbock]

Ich glaube das ist beim FPC schon mit drin.

https://wiki.freepascal.org/gmp

Tatsache, unter

..\fpcsrc\packages\gmp\

liegt eine Datei, die auf den schnellen Blick nach Header aussieht und Examples scheinen auch dabei.

[Warf]

@Warf, welches Pascal-Binding setzt du denn für die GMP ein?

Siehe den wiki eintrag der hier schon gepostet wurde. Ist alles schon in RTL/FLC enthalten, und dank der Magie von Referenzgezählten Interfaces und Operator Overloading auch kinderleicht zu benutzen:

Code: Alles auswählen

uses gmp;

var
  A, B, C: MPInteger;
begin
  A := '1234567890123456789';
  B := 42;
  C := A**B;
  WriteLn(String(A) + '^' + String(B) + '=' String(C));
end.

Natürlich sollte gesagt werden das die interfaces und operatoren natürlich einen gewissen overhead erzeugen A + B + C erzeugt zu erst ein temporäres objekt für (A + B) und um das dann mit C zu addieren und dann das temporäre objekt wieder zu löschen. Über das standard C interface mit mpz_add oder wie die funktion heist kannst du inplace addieren.
Aber im vergleich zu der zeit die großstellige additionen brauchen sollte das irrelevant sein.

Ich weiß aber nicht ob es unter Windows funktioniert. Die GMP gibts zwar für Windows, ich glaub aber die Unit ist dafür nicht vorhanden. Allerdings sollte das ein einfaches includen und dann dll in den suchpfad legen sein

[PascalDragon]

Das Paket hiess FMTBCD. Ich wundere mich gerade, dass ich es unter fpc 3.2 nicht finden kann.

Das Paket heißt rtl-objpas und die Unit heißt FmtBCD.

[Mathias]

Ich bin gerade auf folgende lib gestossen:

https://www.mpfr.org/

Die könnte sicher auch interessant sein, wen man mit sehr grossen Zahlen rechnen will.
Ich werde es mal bei Gelegenheit ausprobieren.

[alfware17]

@Warf, welches Pascal-Binding setzt du denn für die GMP ein?

Siehe den wiki eintrag der hier schon gepostet wurde. Ist alles schon in RTL/FLC enthalten, und dank der Magie von Referenzgezählten Interfaces und Operator Overloading auch kinderleicht zu benutzen:

Code: Alles auswählen

uses gmp;

var
  A, B, C: MPInteger;
begin
  A := '1234567890123456789';
  B := 42;
  C := A**B;
  WriteLn(String(A) + '^' + String(B) + '=' String(C));
end.

Natürlich sollte gesagt werden das die interfaces und operatoren natürlich einen gewissen overhead erzeugen A + B + C erzeugt zu erst ein temporäres objekt für (A + B) und um das dann mit C zu addieren und dann das temporäre objekt wieder zu löschen. Über das standard C interface mit mpz_add oder wie die funktion heist kannst du inplace addieren.
Aber im vergleich zu der zeit die großstellige additionen brauchen sollte das irrelevant sein.

Ich weiß aber nicht ob es unter Windows funktioniert. Die GMP gibts zwar für Windows, ich glaub aber die Unit ist dafür nicht vorhanden. Allerdings sollte das ein einfaches includen und dann dll in den suchpfad legen sein

Wie erzeuge ich denn die erforderliche gmp.dll, die beim Programmaufruf verlangt wird. Compilieren konnte ich das unter Lazarus ebenso wie mit FPC batch. Während bei der Ausführung mit Lazarus nix passiert, wurde ich neugierig und habe es auf Kommandozeile gestartet - da fehlt eine gmp.dll. Die Quellen im o.g. fpc source habe ich auch gefunden, aber noch niemals eine dll erzeugt...

Danke erstmal für das Beispiel - ich bin neugierig geworden und wollte testen/messen wieviel schneller es tatsächlich wird im Vergleich mit einer String-basierten Lösung die ich vor > 20 Jahren mal geschrieben habe und gerade angeschaut.

[Mathias]

Wie erzeuge ich denn die erforderliche gmp.dll, die beim Programmaufruf verlangt wird. Compilieren konnte ich das unter Lazarus ebenso wie mit FPC batch. Während bei der Ausführung mit Lazarus nix passiert, wurde ich neugierig und habe es auf Kommandozeile gestartet - da fehlt eine gmp.dll. Die Quellen im o.g. fpc source habe ich auch gefunden, aber noch niemals eine dll erzeugt...

Da wirst du mit Lazarus nicht weit kommen. Meistens sie die Sourcen für DLLs in C geschrieben.
Entweder du hast ein MinGW auf Windows eingerichtet.
Oder versuchst die DLL in irgendeiner dubiosen Seite runter zu laden.

Oder als Linux-User einfach

Code: Alles auswählen

 sudo apt install libgmp-dev

[alfware17]

Wie erzeuge ich denn die erforderliche gmp.dll, die beim Programmaufruf verlangt wird. Compilieren konnte ich das unter Lazarus ebenso wie mit FPC batch. Während bei der Ausführung mit Lazarus nix passiert, wurde ich neugierig und habe es auf Kommandozeile gestartet - da fehlt eine gmp.dll. Die Quellen im o.g. fpc source habe ich auch gefunden, aber noch niemals eine dll erzeugt...

Da wirst du mit Lazarus nicht weit kommen. Meistens sie die Sourcen für DLLs in C geschrieben.
Entweder du hast ein MinGW auf Windows eingerichtet.
Oder versuchst die DLL in irgendeiner dubiosen Seite runter zu laden.

Oder als Linux-User einfach

Code: Alles auswählen

 sudo apt install libgmp-dev

Ich bin zwar (manchmal) Linux-Nutzer, aber ich nehme an, die .so wenn ich sie denn finde kann ich nicht einfach umbenennen und in Windows benutzen

Also ich habe kein MinGW, würde ich nicht seit 100 Jahren mal immer wieder versuchen, den "einen" C-Compiler für mich herauszufinden (angeblich ist soviel Software in der Welt in C geschrieben aber ich finden keinen Compiler, nicht mal für make wenn mal jemand Quelltexte ins git stellt - polemic off), ich nutze echt Turbo-C in einer Virtualbox für die einzige 3 C-Quellen meines Lebens.
Ich würde ja gerne - nur geht der Link http://cs.nyu.edu/exact/core/gmp/ hier auf "Zugriff verweigert".
Eine dubiose Seite habe ich gefunden https://www.dlldownloader.com/gmp-dll/ ist die seriös, habe noch nicht ausprobiert?

ICH DACHTE: das ist eine vielbenutzte seriöse Software und man kriegt das alles incl Download und Installer wie bei Microsoft.... Habe ich wohl wieder falsch gedacht.