Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Faktorisierung seeehr großer Zahlen
ub60 - So 24.01.16 11:51
Titel: Faktorisierung seeehr großer Zahlen
Hallo Leute,
für ein Krypto-Projekt suche ich eine Möglichkeit, sehr große Zahlen (>1 Million Stellen) in ihre Primfaktoren zu zerlegen.
Dabei kommt erleichternd hinzu, dass ich die Primfaktoren kenne (sie sind maximal 3-stellig). Was ich suche, sind die Exponenten.
Mein erster Versuch war die Unit BigNum2 hier aus dem Forum (mit BM_Divide(Zahl, Primfaktor)). Leider scheint sie zeitmäßig damit überfordert zu sein.
Ich suche also
- eine Langzahl-Unit, mit der man schnell (ohne Rest) dividieren kann,
- oder eine Idee, wie man die Sache beschleunigen kann.
- Eventuell gibt es ja auch professionelle Lösungen für so etwas, aber ein eigenes Programm wäre mir lieber.
ub60
Mathematiker - So 24.01.16 12:43
Hallo ub60,
versuche es mal mit MPArith (
http://www.wolfgang-ehrhardt.de/misc_de.html#mparith) von Wolfgang Ehrhardt (
Gammatester).
Allerdings vermute ich, dass bei mehr als 1 Million Stellen auch diese Lösung aussteigt.
Beste Grüße
Mathematiker
Nachtrag: Ich habe gerade nachgesehen. 32000 Ziffern sind das Maximum. Nützt dir also nichts. :cry:
ub60 - So 24.01.16 13:29
@
Mathematiker: Da war ich bei meiner Recherche auch schon drauf gestoßen, aber auf den ersten Blick scheint mit das Ganze für meine Anforderungen sehr überdimensioniert uns auch ziemlich schwierig zu sein. Wenn keine anderen Tipps kommen, werde ich mich da wohl mal einlesen.
@
FinnO: Leider nicht, aber Danke für den Tipp.
Erst einmal vielen Dank, weitere Ideen sind erwünscht.
ub60
Mathematiker - So 24.01.16 15:16
Hallo,
ich habe etwas mit Delphi probiert.
Im angehängten Programm multipliziere ich 40000 Primzahlen < 10000. Damit erhalte ich wenigstens eine rund 100000ziffrige Zahl, natürlich keine 1 Million.
Anschließend zerlege ich sie wieder mit den Primfaktoren und im Moment sieht es so aus, als ob es funktioniert.
Die Lösung ist natürlich noch zu langsam und vor allem 1 Million und mehr Ziffern ergeben eine mindestens 100fache Rechenzeit, aber vielleicht kann man ja noch etwas "basteln".
Insbesondere wird es wohl Ärger bei der Erhöhung der Feldgröße geben (Stack-Überlauf :cry: ).
Mehr fällt mir im Moment nicht ein.
Beste Grüße
Mathematiker
ub60 - So 24.01.16 19:43
@
Fiete: Vielen Dank, ich habe es gleich probiert. Funktioniert mit "kleinen Zahlen" prima. Für das, was ich machen möchte, ist es leider zu langsam.
@
Mathematiker: Das sieht auch gut aus. Den Stack habe ich auf $0100.0000 erhöht, jetzt läuft das Ganze gerade mit 200000 Faktoren. Da der Computer jetzt doch schon lange rödelt, denke ich mal, dass es auch für einige Millionen Ziffern zu langsam ist. Trotzdem vielen Dank!
Ich glaube, so was habe ich gesucht. Nächstes WE habe ich wieder Zeit, dann werde ich mich mal reinlesen. Danke sehr!
ub60
Delphi-Laie - So 24.01.16 21:35
Am besten zur Lösung dieses Problems ist die Langzahlenbibliothek "DEC" von Hagen Reddmann (negaH) geeignet, sowohl, was die Stabilität als auch - und das an erster Stelle - die Geschwindigkeit anbetrifft.
Gammatester - Mo 25.01.16 10:27
Mathematiker hat folgendes geschrieben  : |
Hallo ub60,
versuche es mal mit MPArith (http://www.wolfgang-ehrhardt.de/misc_de.html#mparith) von Wolfgang Ehrhardt (Gammatester).
Allerdings vermute ich, dass bei mehr als 1 Million Stellen auch diese Lösung aussteigt.
Beste Grüße
Mathematiker
Nachtrag: Ich habe gerade nachgesehen. 32000 Ziffern sind das Maximum. Nützt dir also nichts. :cry: |
Das ist nur ein Bruchteil der Wahrheit, dies gilt für die 16-Bit Versiion. Delphi/FPC-Standard unterstützt bis zu 520093696 (d.h. mehr als 520 Mio) oder mehr als 150 Mio Dezimalstellen. Allerdings kann man bei dieser Größenordung nur sinnvoll addieren etc., quadratische Operationen brauchen halt ihre Zeit.
| ub60 hat folgendes geschrieben : |
Hallo Leute,
für ein Krypto-Projekt suche ich eine Möglichkeit, sehr große Zahlen (>1 Million Stellen) in ihre Primfaktoren zu zerlegen.
Dabei kommt erleichternd hinzu, dass ich die Primfaktoren kenne (sie sind maximal 3-stellig). Was ich suche, sind die Exponenten.
|
Normalerweise ist die Faktorisierung von algemeinen Zahlen mit mehr als (ein paar) Hundert Dez-Stellen ein
NO GO, aber diese spezielle Struktur erklaubt sowas. (Was ist denn das für ein Krypto-Projekt?)
Für diesen Zweck gibt es in MPArith eine spezielle halbwegs optimierte Funktion (weil die manuelle oftmalige wiederholte Division sub-optimal ist):
Delphi-Quelltext
1:
2:
3:
| function mp_val(const a: mp_int; r: longint): longint;
|
Hier mal ein Beispiel mit dem Beispiel-Taschenrechner
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
| D:\Xtools\MPArith>t_calc.exe
T_CALC using MPArith V1.31.00 (31/32 bit) [mp_calc] (c) W.Ehrhardt 2006-2014
Karatsuba cutoffs: mul/sqr = 16/32, Toom-3 cutoffs: mul/sqr = 32/64
Burnikel/Ziegler div cutoff = 32, MaxBit = 520093696, MaxFact = 22623931
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.
[D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=488.987 ms]
[D]:=> val(x,3)
Result = 200001 Time = 10681.322 ms
[D]:=> val(x,7)
Result = 200000 Time = 16663.620 ms
[D]:=> val(x,2)
Result = 200000 Time = 0.308 ms
[D]:=> val(x,11)
Result = 0 Time = 1.664 ms |
ub60 - Mo 25.01.16 17:47
Vielen Dank erst mal an alle für die vielen guten Vorschläge. Ich brauche jetzt erst einmal ein paar Tage, um mir das Ganze durchzuarbeiten.
| Gammatester hat folgendes geschrieben : |
| Was ist denn das für ein Krypto-Projekt?) |
Es ist eine Art Spiel zur Verschlüsselung/Entschlüsselung von Texten. Am Ansatz der ganzen Sache kann ich nichts ändern. (Es ist auch nicht Ziel des Spiels, optimal zu sein :lol: .)
ub60
ub60 - Di 26.01.16 19:53
@Gammatester
Zuerst noch einmal vielen Dank für die ausführliche Antwort. Ich habe mir jetzt die t_calc.pas mit Delphi7 kompiliert und Deine Befehle nachvollzogen. Prinzipiell wäre der mp_val-Befehl genau das, was ich brauche. Ich muss mich nur noch etwas in die Syntax einarbeiten, und nachsehen, wie ich die große Zahl (als String) einlese.
Nun aber meine eigentliche Frage: Ich habe bei der ersten Operation (Potenzieren) eine zumindest ähnliche Zeit herausbekommen, wie Du. Bei der Zerlegung (val) beträgt der Unterschied aber etwa das 15-fache. Womit hast Du die Datei compiliert, dass die Werte ab dem zweiten Wert so schnell sind?
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
| T_CALC using MPArith V1.32.04 (31/32 bit) [mp_calc] (c) W.Ehrhardt 2006-2014
Karatsuba cutoffs: mul/sqr = 16/32, Toom-3 cutoffs: mul/sqr = 32/64
Burnikel/Ziegler div cutoff = 32, MaxBit = 520093696, MaxFact = 22623931
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.
[D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=714.290 ms]
[D]:=> val(x,3)
Result = 200001 Time = 150932.099 ms
[D]:=> val(x,2)
Result = 200000 Time = 233372.111 ms
[D]:=> val(x,11)
Result = 200000 Time = 0.152 ms
[D]:=> val(x,7)
Result = 0 Time = 35.268 ms |
Mein Rechner: Intel Core i7 860@2,80GHz, 8GB RAM
Ach so, falls noch jemand anders mittesten möchte: Die Zeit in der Ausgabe erhält man mit Punkt+Enter.
Besten Dank!
ub60
EDIT:
Oh je! Ich habe die Werte falsch kopiert. So ist es richtig;
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| [D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=714.290 ms]
[D]:=> val(x,3)
Result = 200001 Time = 150932.099 ms
[D]:=> val(x,7)
Result = 200000 Time = 233372.111 ms
[D]:=> val(x,11)
Result = 0 Time = 35.268 ms
[D]:=> val(x,2)
Result = 200000 Time = 0.152 ms |
Sorry für den Fehler!
Horst_H - Mi 27.01.16 09:12
Hallo,
| Zitat: |
[D]:=> val(x,2)
Result = 200000 Time = 233372.111 ms |
Das kann ich gar nicht glauben, dass val(x,2) länger brauchen sollte, denn dabei werden nur die 0-Bits am Ende der Zahl gezählt.
Bei
Gammatester sieht man das an der Laufzeit:
| Zitat: |
[D]:=> val(x,7)
Result = 200000 Time = 16663.620 ms
[D]:=> val(x,2)
Result = 200000 Time = 0.308 ms |
Ausserdem ist
| Zitat: |
[D]:=> val(x,7)
Result = 0 Time = 35.268 ms |
wohl nicht richtig.
210 = 2*3*5*7 -> 210^n -> 2^n*3^n*5^n*7^n also 7 kommt öfter als 0-fach vor.
Da ist etwas anderes völlig daneben.
Gruß Horst
Edit: Ich habe mal die oben genannte Version von mparith heruntergeladen und mal mit freepascal fürc 32 und 64-Bit unter Linux64 kompiliert.
Etwas zusammengerückte Ausgabe für i3-4330 ( Haswell ) 3,5 Ghz
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
| Free Pascal Compiler version 3.0.1 [2015/11/02] for x86_64
T_CALC using MPArith V1.32.04 (31/32 bit) [mp_calc] (c) W.Ehrhardt 2006-2014
[D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=299.572 ms]
[D]:=> val(x,3) Result = 200001 [D]:=> . Time = 6382.497 ms
[D]:=> val(x,7) Result = 200000 [D]:=> . Time = 9957.676 ms
[D]:=> val(x,11)Result = 0 [D]:=> . Time = 1.189 ms
[D]:=> val(x,2) Result = 200000 [D]:=> . Time = 0.057 ms
....
Free Pascal Compiler version 3.1.1 [2016/01/15] for i386
T_CALC using MPArith V1.32.04 (31/32 bit) [mp_calc] (c) W.Ehrhardt 2006-2014
[D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=580.836 ms]
[D]:=> val(x,3); Result = [>0, 18 bits, chksum=$01450053, time=7436.468 ms]
[D]:=> val(x,7); Result = [>0, 18 bits, chksum=$01410052, time=11542.324 ms]
[D]:=> val(x,11);Result = [=0, 0 bits, chksum=$00060001, time=4.589 ms]
[D]:=> val(x,2); Result = [>0, 18 bits, chksum=$01410052, time=0.082 ms] |
Gammatester - Mi 27.01.16 10:34
| ub60 hat folgendes geschrieben : |
@Gammatester
Zuerst noch einmal vielen Dank für die ausführliche Antwort. Ich habe mir jetzt die t_calc.pas mit Delphi7 kompiliert und Deine Befehle nachvollzogen. Prinzipiell wäre der mp_val-Befehl genau das, was ich brauche. Ich muss mich nur noch etwas in die Syntax einarbeiten, und nachsehen, wie ich die große Zahl (als String) einlese.
Nun aber meine eigentliche Frage: Ich habe bei der ersten Operation (Potenzieren) eine zumindest ähnliche Zeit herausbekommen, wie Du. Bei der Zerlegung (val) beträgt der Unterschied aber etwa das 15-fache. Womit hast Du die Datei compiliert, dass die Werte ab dem zweiten Wert so schnell sind?
|
Ich kann Deinen Wert für val(x,3) nachvollziehen. Für Out-of-the-Box Delphi7 erhalte ich bei mir ca 142387 ms. Bei val(x,2) und val(x,11) hast Du ev. andere Problem (Verwechslung oä), ich erhalte val(x,2)=200000 in 0.2 ms und val(x,11)=0 in 17.9 ms.
Warum ist Delphi7 so langsam für einige Operationen? Vereinfacht ausgedrückt, weill der (U)INT64-Support saumäßig ist, und erst ab D10 besser wird, keine Probleme bei FreePascal, das aber insgesamt bei mir etwas langsamer ist. Wenn Du auf D7 angewiesen bis, empfehle ich die MP16_BIT-Option, also mit {$define MP_16BIT} permanent in der mp_conf.inc oder temporär mit der Kommandozeile
<d8-dcc.exe> -dMP_16BIT t_calc.pas
Hier die Ergebnisse
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
| C:\TEST>D:\DMX\M7\DCC32 -b -q -dMP_16BIT t_calc.pas
Borland Delphi Version 15.0
Copyright (c) 1983,2002 Borland Software Corporation
38764 lines, 0.12 seconds, 112584 bytes code, 26053 bytes data.
C:\TEST>t_calc.exe
T_CALC using MPArith V1.32.04 (15/16 bit) [mp_calc] (c) W.Ehrhardt 2006-2014
Karatsuba cutoffs: mul/sqr = 64/96, Toom-3 cutoffs: mul/sqr = 128/192
Burnikel/Ziegler div cutoff = 96, MaxBit = 251658240, MaxFact = 11436685
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.
[D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C85295A4, time=638.413 ms]
[D]:=> val(x,3)
Result = 200001
[D]:=> .
Time = 20520.573 ms
[D]:=> val(x,2)
Result = 200000
[D]:=> .
Time = 0.232 ms
[D]:=> val(x,11)
Result = 0
[D]:=> .
Time = 1.516 ms
[D]:=> val(x,7)
Result = 200000
[D]:=> .
Time = 33264.165 ms |
Da die interne Darstellung jetzt anders ist, ist auch die Checksumme für x geändert. Daß jetzt 15/16-Bit-Digits benutzt werden erkennt man im Header.-
ub60 - Mi 27.01.16 11:29
Oh je! Ich habe die Werte falsch kopiert. :oops:
So ist es richtig;
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| [D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=714.290 ms]
[D]:=> val(x,3)
Result = 200001 Time = 150932.099 ms
[D]:=> val(x,7)
Result = 200000 Time = 233372.111 ms
[D]:=> val(x,11)
Result = 0 Time = 35.268 ms
[D]:=> val(x,2)
Result = 200000 Time = 0.152 ms |
Sorry für den Fehler!
Ich habe es im oberen Beitrag gleich noch einmal editiert.
@Horst_H: Danke für der Freepascal-Compiler-Test, die Daten waren sehr hilfreich. Ich hätte gedacht, dass er bei 64 Bit noch etwas schneller ist.
@Gammatester: Bei der 16-Bit-Version sind meine verwendeten Zahlen zu groß, ich brauche etwa 10 Millionen Stellen.
Für Interessenten: Erster Zwischentest mit eigenem Programm:
-Länge der Zahl: Etwas über 10 Millionen Ziffern.
-Primfaktor: 97
-Vorkommen: ca. 100 mal
-Rechenzeit: ca. 3-4 Stunden (muss noch einen Timer einbauen) mit mp_val
Ich probiere weiter ...
ub60
Horst_H - Mi 27.01.16 11:42
Hallo,
ich hoffe, Du kürzst die Zahl um die gefundenen Faktoren und rechnest damit weiter.
Bei 3 -Stelligen Zahlen bist Du bei 168 Primzahlen als Faktoren.
Du brauchst also nur 168 mal MOD mit einer kleinen Zahl berechnen.Das kann keine Stunden dauern.
Die Testzahl hat wohl 1.25 Mio Stellen.Also rechne ich mit 8-facher Laufzeit gegenüber val(x,11)
Wegen mit 80 statt 10 ms da bist Du bei 13 Sekunden um die Faktoren zu finden.
| Zitat: |
| Ich hätte gedacht, dass er bei 64 Bit noch etwas schneller ist. |
Ich auch! Abder im Program steht ja dann auch 31/32 Bit oben und nicht 63/64 BIT
Auch purepascal hat da nichts geändert.Ich kenne davon zuwenig, um das jetzt auf die Schnelle herauszufinden.
Viel Vergnügen beim Faktorisieren.
Gruß Horst
Gammatester - Mi 27.01.16 11:51
| ub60 hat folgendes geschrieben : |
@Gammatester: Bei der 16-Bit-Version sind meine verwendeten Zahlen zu groß, ich brauche etwa 10 Millionen Stellen.
|
Da verwechselst Du etwas: MP16_BIT sagt nicht, daß ein 16-Bit-Compiler benutzt wird, sondern daß die Basiseinheit MP_DIGIT ein 16-Bit-Typ ist. Wie Du an meinen Beispiel
Quelltext
1:
2:
3:
| T_CALC using MPArith V1.32.04 (15/16 bit) [mp_calc] (c) W.Ehrhardt 2006-2014
Karatsuba cutoffs: mul/sqr = 64/96, Toom-3 cutoffs: mul/sqr = 128/192
Burnikel/Ziegler div cutoff = 96, MaxBit = 251658240, MaxFact = 11436685 |
sehen kannst, kann man Zahlen bis 251658240 Bit verarbeiten. Auch meine schnelleren Delphi7-Zeiten von oben sind für den MP16_BIT-Modus.
| ub60 hat folgendes geschrieben : |
Für Interessenten: Erster Zwischentest mit eigenem Programm:
-Länge der Zahl: Etwas über 10 Millionen Ziffern.
-Primfaktor: 97
-Vorkommen: ca. 100 mal
-Rechenzeit: ca. 3-4 Stunden (muss noch einen Timer einbauen) mit mp_val
|
Test doch einfach mal MP16_BIT, wenn's bei Dir wirklich Faktor 10-15 schneller ist lohnt sich auf jeden Fall der Versuch (und 20..25 min sind gefühlt viel besser als 3-4 h).
Gammatester - Mi 27.01.16 12:07
| Horst_H hat folgendes geschrieben : |
Du brauchst also nur 168 mal MOD mit einer kleinen Zahl berechnen.Das kann keine Stunden dauern.
Die Testzahl hat wohl 1.25 Mio Stellen.Also rechne ich mit 8-facher Laufzeit gegenüber val(x,11)
Wegen mit 80 statt 10 ms da bist Du bei 13 Sekunden um die Faktoren zu finden.
|
Da kann man sich leicht irren. Selbst wenn man für Division der Testzahl 15*210^200000 durch 7 nur 0.1 ms bräuchte, wären das schon 20000 ms allein für den Faktor 7 (vereinfacht, weil die Zahlen ja immer kleiner werden). Deshalb die spezielle Funktion.
Horst: bei GMP gibt's dafür
mpz_remove -- divide out a factor and return its multiplicity.
Edit: Zumindest verstehe ich das Problem so. Es heißt ja im ersten Beitrag, daß die Primzahl-Exponenten der Zahl mit 1 Mio Stellen gesucht werden. D.h. man kann insgesamt bei 2 bis 3 stelligen Primzahlen 10^6/2.5 = 400000 Divisionen erwarten, wenn man immer naiv durch die Primzahlen teilt, bis sich ein Rest ungleich Null ergibt.
Fiete - Fr 05.02.16 13:04
Moin ub60,
da die Primfaktoren bekannt sind könnte die Eingangszahl erst mal durch das Produkt aller Faktoren geteilt werden, so ist die Zahl erst mal kleiner.
Andere Variante: teile durch Primfaktor^100, wobei 100 eine Abschätzung sei muss. Die Größe der Exponenten musst Du einschätzen, vielleicht gehts auch mit ^1000 :wink:
Das Ganze sieht nach einer Gödelisierung aus.
Gruß Fiete
Gammatester - Fr 05.02.16 13:43
| Fiete hat folgendes geschrieben : |
Moin ub60,
da die Primfaktoren bekannt sind könnte die Eingangszahl erst mal durch das Produkt aller Faktoren geteilt werden, so ist die Zahl erst mal kleiner.
Andere Variante: teile durch Primfaktor^100, wobei 100 eine Abschätzung sei muss. Die Größe der Exponenten musst Du einschätzen, vielleicht gehts auch mit ^1000 :wink:
Das Ganze sieht nach einer Gödelisierung aus.
|
Aus dem bisher gesagten, entnehme ich, daß die Exponenten der Primzahlen gesucht werden sollen, diese aber durchaus =0 sein können. Wenn dies der Fall, führt Dein erster Vorschlag i.d.R. zu nix.
Für einen schnellen Überblick, welche Primfaktoren überhaupt vorkommen, kann man mit der gegebenen Zahl N und dem euklidischen Algorithmus sehr schnell x=gcd(N, 997#) ausrechnen (wobei 997# = primorial(997) das Produkt der Primzahlen bis 997 ist) und dann sehen welche Faktoren x enthält (x hat nur maximal 416 Stellen).
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| [D]:=> x=15*210^200000;
X = [>0, 1542854 bits, chksum=$C3812EB8, time=489.822 ms]
[D]:=> y=997#;
Y = [>0, 1380 bits, chksum=$F7F94F13, time=0.093 ms]
[D]:=> gcd(x,y)
Result = 210
[D]:=> .
Time = 191.773 ms |
ub60 - Fr 05.02.16 14:23
So, mein Problem wäre gelöst und ich will nur noch für Interessenten einen kleinen "Abschlussbericht" schreiben.
1. DEC
Ich habe letztendlich das DEC (DECMath) verwendet, da es wahnsinnig schnell ist. Mit DECMath konnte ich eine Zahl mit mehr als 10 Millionen Stellen gut verarbeiten. Mit naiver Division habe ich erst einmal ermittelt, welche Primfaktoren überhaupt vorkommen. Mit naiver Division habe ich außerdem die Exponenten der Primzahlen ermittelt, die nur mit kleineren Exponenten (<100000) vorkamen. An 6 Rechnern parallel war das in einigen Stunden gelöst.
| Fiete hat folgendes geschrieben : |
Andere Variante: teile durch Primfaktor^100, wobei 100 eine Abschätzung sei muss. Die Größe der Exponenten musst Du einschätzen, vielleicht gehts auch mit ^1000 :wink:
|
Natürlich habe ich dann auch durch die gefundenen Potenzen geteilt. Das macht aber größenmäßig wirklich erst bei hohen Exponenten Sinn.
Die restlichen (großen) Exponenten habe ich so ähnlich gelöst, wie Fiete vorgeschlagen hat. Ich habe dabei allerdings so eine Art (manuelle) Intervallschachtelung durchgeführt, so dass es dann doch recht schnell ging. Beim nächsten Mal würde ich diese Intervallschachtelung sicherlich programmieren, das sollte dann höllenschnell sein.
Eine äquivalente Funktion zu mp_val habe ich in DEC leider nicht gefunden, eventuell habe ich es aber auch übersehen.
2. MPArith
MPArith funktionierte auch ganz gut, war aber aus meiner Sicht etwas langsamer als DEC.
3. GMP
Das einzige "Pascalinterface", das ich gefunden hatte, war "GMP for Delphi.zip", das mit irgendeiner höheren Delphi-Version compiliert war. Den Quelltext habe ich leider mit meinem Delphi 7 nicht zum Laufen bekommen. Im Quelltext steht:
| Zitat: |
This wrapper only supports Delphi versions with operator overloading.
For earlier versions please use header file gmp_lib.pas directly. |
Das habe ich allerdings noch nicht probiert. Wenn hier jemand einen Quelltextschnipsel hätte, der ohne Änderung mit "kleineren " Delphi-Versionen läuft, wäre ich für einen Tipp sehr dankbar. Ansonsten werde ich wohl mal alleine probieren.
| Fiete hat folgendes geschrieben : |
Das Ganze sieht nach einer Gödelisierung aus.
|
Jetzt hat das Kind einen Namen. So etwas war es. Da muss ich wohl im Mathe-Studium gerade krank gewesen sein :D .
Besten Dank noch mal an alle Ideengeber!
ub60
ub60 - Fr 05.02.16 14:32
Die Antworten haben sich gerade überschnitten, deshalb ein Doppelpost.
| Gammatester hat folgendes geschrieben : |
Für einen schnellen Überblick, welche Primfaktoren überhaupt vorkommen, kann man mit der gegebenen Zahl N und dem euklidischen Algorithmus sehr schnell x=gcd(N, 997#) ausrechnen (wobei 997# = primorial(997) das Produkt der Primzahlen bis 997 ist) und dann sehen welche Faktoren x enthält (x hat nur maximal 416 Stellen). |
Auch eine Super-Idee! Leider (oder zum Glück :lol: ) habe ich die Zahl mittlerweile faktorisiert.
Trotzdem Klasse, wie viel tolle Ideen hier im Forum gekommen sind!
ub60
Delphi-Laie - Sa 06.02.16 17:37
| ub60 hat folgendes geschrieben : |
3. GMP
Das einzige "Pascalinterface", das ich gefunden hatte, war "GMP for Delphi.zip", das mit irgendeiner höheren Delphi-Version compiliert war. Den Quelltext habe ich leider mit meinem Delphi 7 nicht zum Laufen bekommen. Im Quelltext steht:
| Zitat: | This wrapper only supports Delphi versions with operator overloading.
For earlier versions please use header file gmp_lib.pas directly. |
Das habe ich allerdings noch nicht probiert. Wenn hier jemand einen Quelltextschnipsel hätte, der ohne Änderung mit "kleineren " Delphi-Versionen läuft, wäre ich für einen Tipp sehr dankbar. Ansonsten werde ich wohl mal alleine probieren. |
Also, das ließ mir keine Ruhe, bin ich doch weiterhin auf der Suche nach Pascal-Langzahlenunits für meinen
Langzahlentaschenrechner [
http://www.entwickler-ecke.de/viewtopic.php?t=109667&highlight=langzahlentaschenrechner] (zu dem ich derzeit nicht komme, mein
Sortierkino [
http://www.entwickler-ecke.de/viewtopic.php?t=95246&highlight=sortierkino]spannt mich derzeit voll ein....).
Mein erster Fund war:
https://storage.googleapis.com/google-code-archive-downloads/v2/code.google.com/wqyfavor-downloads-host/GMP%20for%20Delphi.zip
Ist das das Archiv, was Du benutztest, oder ein anderes?
Die dort enthaltene Exe-Datei hat zunächst einmal einen Fehler: Beendet man das Programm, kommt die Fehlermeldung: "An unexpected memory leak has occured. [...]".
Diese Exe hat als Symbol das mir von Turbo-Delphi bekannte (keine Ahnung, ob das in höheren Versionen auch noch benutzt wurde, Delphi 3 und 4 erzeugten ja auch das gleiche), dennoch läßt es sich nicht mit Turbo-Delphi übersetzen. In der Datei gmp_lib.pas die beiden Typen "UInt32" durch "Cardinal" ersetzt, denn etwas anderes kann UInt32 kaum sein, in der Projektdatei die Zeile "Application.MainFormOnTaskbar := True;" entfernt bzw. auskommentiert, und schon läßt sich das auch mit Turbo-Delphi ohne Warnung und nur 5 Hinweisen bezüglich nicht benutzter Variablen (oder Variabeln?) übersetzen. Die erhaltene Exe-Datei ist deutlich kleiner als das beigelegte Original und hat diesen elenden Memory-Leak-Fehler nicht, jedenfalls nicht beim Beeenden.
Ergänzung: Delphi 7 scheitert allerdings mit dem Kompilieren....
2. Ergänzung: UInt32 ist eigentlich ein Longword, aber mit Cardinal klappt es ja auch.
3. Ergänzung: Entferne ich alles, was die Hinweise verursacht, bekomme ich auch mit dem Turbo-Delphi-Compilat diese elenden Memory-Leak-Fehlermeldungen.
4. Ergänzung: Zwei nicht verwendete private Fill-Variablen müssen bleiben, und mit diesen die Hinweise, sonst kommt die besagte elende Fehlermeldung zur Laufzeit. Angehängtes Archiv ist ansonsten für Turbo-Delphi vorbereitet, hat auch das Compilat inneliegend.
ub60 - Sa 06.02.16 19:51
Genau das war das einzig Sinnvolle, das ich gefunden habe. Ich hatte auch zuerst die UInt32 mit Cardinal ersetzt, aber dann kamen Unmengen andere Fehler ...
Bei mir funktioniert die beiliegende Exe übrigens ohne Fehlermeldung beim Abschluss. Leider wird (zumindest in der Exe) nur mit gebrochenen Zahlen gerechnet, so dass die Genauigkeit auf der Strecke bleibt (100^20=999999999999999999999999999999999997167). Außerdem wird nach ca. 40 Stellen dicht gemacht (abgeschnitten), und das ohne Hinweis oder Fehlermeldung.
ub60
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!