Extem grosse Zahlen, über 1000 Stellen

Für allgemeine Fragen zur Programmierung, welche nicht! direkt mit Lazarus zu tun haben.
Antworten
Mathias
Beiträge: 5116
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunc)
CPU-Target: 64Bit
Wohnort: Schweiz

Extem grosse Zahlen, über 1000 Stellen

Beitrag von 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.
Mit Lazarus sehe ich gün
Mit Java und C/C++ sehe ich rot

Warf
Beiträge: 1573
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von 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

Benutzeravatar
Winni
Beiträge: 906
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.0.12, fpc 3.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von 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
Beiträge: 5116
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunc)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von Mathias »

Link ist leider Tod.
Mit Lazarus sehe ich gün
Mit Java und C/C++ sehe ich rot

TSchnuckenbock
Beiträge: 22
Registriert: Do 20. Jul 2017, 23:47
OS, Lazarus, FPC: Win7 und Win10
CPU-Target: xxBit

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von TSchnuckenbock »


TSchnuckenbock
Beiträge: 22
Registriert: Do 20. Jul 2017, 23:47
OS, Lazarus, FPC: Win7 und Win10
CPU-Target: xxBit

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von 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
Beiträge: 442
Registriert: Do 15. Nov 2007, 16:58
OS, Lazarus, FPC: Win10 (L 1.6 FPC 3.0.0)
CPU-Target: i386,x64
Wohnort: Rudolstadt

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von shokwave »

Ich glaube das ist beim FPC schon mit drin.

https://wiki.freepascal.org/gmp
mfg Ingo

Soner
Beiträge: 477
Registriert: Do 27. Sep 2012, 00:07
OS, Lazarus, FPC: Win10Pro-64Bit, Immer letzte Lazarus Release mit SVN-Fixes
CPU-Target: x86_64-win64
Wohnort: Hamburg

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von 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
Beiträge: 22
Registriert: Do 20. Jul 2017, 23:47
OS, Lazarus, FPC: Win7 und Win10
CPU-Target: xxBit

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von TSchnuckenbock »

shokwave hat geschrieben:
Mi 8. Sep 2021, 18:08
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
Beiträge: 1573
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von Warf »

TSchnuckenbock hat geschrieben:
Mi 8. Sep 2021, 17:47
@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
Beiträge: 367
Registriert: Mi 3. Jun 2020, 07:18
OS, Lazarus, FPC: L 2.0.8, FPC Trunk, OS Win/Linux
CPU-Target: Aarch64 bis Z80 ;)
Wohnort: München

Re: Extem grosse Zahlen, über 1000 Stellen

Beitrag von PascalDragon »

Winni hat geschrieben:
Mi 8. Sep 2021, 17:00
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.
FPC Compiler Entwickler

Antworten