Extem grosse Zahlen, über 1000 Stellen
-
- Beiträge: 6210
- Registriert: Do 2. Jan 2014, 17:21
- OS, Lazarus, FPC: Linux (die neusten Trunk)
- CPU-Target: 64Bit
- Wohnort: Schweiz
Extem grosse Zahlen, über 1000 Stellen
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.
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 grün
Mit Java und C/C++ sehe ich rot
Mit Java und C/C++ sehe ich rot
-
- Beiträge: 1913
- Registriert: Di 23. Sep 2014, 17:46
- OS, Lazarus, FPC: Win10 | Linux
- CPU-Target: x86_64
Re: Extem grosse Zahlen, über 1000 Stellen
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
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
- Beiträge: 1577
- Registriert: Mo 2. Mär 2009, 16:45
- OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
- CPU-Target: 64Bit
- Wohnort: Fast Dänemark
Re: Extem grosse Zahlen, über 1000 Stellen
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
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
-
- Beiträge: 6210
- Registriert: Do 2. Jan 2014, 17:21
- OS, Lazarus, FPC: Linux (die neusten Trunk)
- CPU-Target: 64Bit
- Wohnort: Schweiz
Re: Extem grosse Zahlen, über 1000 Stellen
Link ist leider Tod.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot
Mit Java und C/C++ sehe ich rot
-
- Beiträge: 72
- Registriert: Do 20. Jul 2017, 23:47
- OS, Lazarus, FPC: Win7 und Win10
- CPU-Target: xxBit
- Wohnort: Südheide (Schnuckenland)
-
- Beiträge: 72
- Registriert: Do 20. Jul 2017, 23:47
- OS, Lazarus, FPC: Win7 und Win10
- CPU-Target: xxBit
- Wohnort: Südheide (Schnuckenland)
Re: Extem grosse Zahlen, über 1000 Stellen
@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.
Was ich gefunden habe ist
https://gmplib.org/manual/Language-Bindings
und da scheinen mir auf den ersten Blick die Pascal-Bindings recht alt.
-
- Beiträge: 624
- 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
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:
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.
-
- Beiträge: 72
- Registriert: Do 20. Jul 2017, 23:47
- OS, Lazarus, FPC: Win7 und Win10
- CPU-Target: xxBit
- Wohnort: Südheide (Schnuckenland)
Re: Extem grosse Zahlen, über 1000 Stellen
Tatsache, untershokwave hat geschrieben: ↑Mi 8. Sep 2021, 18:08Ich glaube das ist beim FPC schon mit drin.
https://wiki.freepascal.org/gmp
..\fpcsrc\packages\gmp\
liegt eine Datei, die auf den schnellen Blick nach Header aussieht und Examples scheinen auch dabei.
-
- Beiträge: 1913
- Registriert: Di 23. Sep 2014, 17:46
- OS, Lazarus, FPC: Win10 | Linux
- CPU-Target: x86_64
Re: Extem grosse Zahlen, über 1000 Stellen
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:TSchnuckenbock hat geschrieben: ↑Mi 8. Sep 2021, 17:47@Warf, welches Pascal-Binding setzt du denn für die GMP ein?
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.
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
-
- Beiträge: 834
- 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
Das Paket heißt rtl-objpas und die Unit heißt FmtBCD.
FPC Compiler Entwickler