Autor Beitrag
ub60
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 694
Erhaltene Danke: 92



BeitragVerfasst: So 24.01.16 10:51 
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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2601
Erhaltene Danke: 1375

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 24.01.16 11:43 
Hallo ub60,
versuche es mal mit MPArith (www.wolfgang-ehrhard...misc_de.html#mparith) von Wolfgang Ehrhardt (user profile iconGammatester).
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:

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Für diesen Beitrag haben gedankt: ub60
FinnO
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1325
Erhaltene Danke: 117

Mac OSX
TypeScript (Webstorm), Kotlin, Clojure (IDEA)
BeitragVerfasst: So 24.01.16 11:54 
Moin,

wenn du .NET verwenden kannst, wäre BigInteger die Lösung der Wahl.

Gruß

Für diesen Beitrag haben gedankt: ub60
ub60 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 694
Erhaltene Danke: 92



BeitragVerfasst: So 24.01.16 12:29 
@user profile iconMathematiker: 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.

@user profile iconFinnO: Leider nicht, aber Danke für den Tipp.

Erst einmal vielen Dank, weitere Ideen sind erwünscht.

ub60
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 515
Erhaltene Danke: 208

W7
Delphi 6 pro
BeitragVerfasst: So 24.01.16 14:16 
Moin ub60,
habe 2007 eine Unit hochgeladen, die Dir nützlich sein könnte.
www.entwickler-ecke....ight=langzahlrechnen
Gruß Fiete

_________________
Fietes Gesetz: use your brain (THINK)

Für diesen Beitrag haben gedankt: Mathematiker, ub60
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2601
Erhaltene Danke: 1375

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 24.01.16 14: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
Einloggen, um Attachments anzusehen!
_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Für diesen Beitrag haben gedankt: ub60
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1637
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: So 24.01.16 17:28 
Hallo,

ich würde GMP benutzen, dass mit freepascal und Delphi gut zu nutzen ist.
code.google.com/p/gmp-wrapper-for-delphi/
bei freepoascal ist die Unit dabei.
Beispielhaft:
www.entwickler-ecke....7&h&start=15

Bei nur 4 stelligen Faktoren liesse sich das sicher sehr schnell testen.
Man könnte www.entwickler-ecke....iewtopic.php?t=51429 DIVI modifizieren.

Gruß Horst

Für diesen Beitrag haben gedankt: ub60
ub60 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 694
Erhaltene Danke: 92



BeitragVerfasst: So 24.01.16 18:43 
@user profile iconFiete: 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.

@user profile iconMathematiker: 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!

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

ich würde GMP benutzen, dass mit freepascal und Delphi gut zu nutzen ist.
code.google.com/p/gmp-wrapper-for-delphi/
bei freepascal ist die Unit dabei.

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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1570
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: So 24.01.16 20: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.

Für diesen Beitrag haben gedankt: ub60
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1637
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mo 25.01.16 08:06 
Hallo,

ist es wirklich so?
github.com/winkelsdo...nCompendium/releases wird seit 2008 nicht weiter entwickelt.
Bei gmp vermute ich den Einsatz von SSE =?.? in diversen Varianten.Zumal durch den großen weltweiten Einsatz Fehler wohl eher aufgespürt werden.
EDIT: gmplib.org/ neueste Version 1.11.2015

Gruß Horst#
Noch ein Edit:
user profile iconLelf hat auch was passendes in der Richtung, es wäre einen Test wert, ob es bei vielen kleinen Faktoren ( 3 stellig ) auch funktioniert.
www.entwickler-ecke....ewtopic.php?t=109998

Für diesen Beitrag haben gedankt: ub60
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mo 25.01.16 09:27 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Hallo ub60,
versuche es mal mit MPArith (www.wolfgang-ehrhard...misc_de.html#mparith) von Wolfgang Ehrhardt (user profile iconGammatester).
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.

user profile iconub60 hat folgendes geschrieben Zum zitierten Posting springen:
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):
ausblenden Delphi-Quelltext
1:
2:
3:
function  mp_val(const a: mp_int; r: longint): longint;
  {-Return the valuation of a with respect to r, ie. the largest v with}
  { r^v divides a, v=0 if r=0,1,or -1, v=MaxLongint if a=0}

Hier mal ein Beispiel mit dem Beispiel-Taschenrechner
ausblenden 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

Für diesen Beitrag haben gedankt: Mathematiker, ub60
ub60 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 694
Erhaltene Danke: 92



BeitragVerfasst: Mo 25.01.16 16: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.

user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 694
Erhaltene Danke: 92



BeitragVerfasst: Di 26.01.16 18: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?

ausblenden 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;
ausblenden 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!


Zuletzt bearbeitet von ub60 am Mi 27.01.16 10:19, insgesamt 1-mal bearbeitet
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1637
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 27.01.16 08: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 user profile iconGammatester 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
ausblenden 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]

Für diesen Beitrag haben gedankt: ub60
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mi 27.01.16 09:34 
user profile iconub60 hat folgendes geschrieben Zum zitierten Posting springen:
@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
ausblenden 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.-

Für diesen Beitrag haben gedankt: ub60
ub60 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 694
Erhaltene Danke: 92



BeitragVerfasst: Mi 27.01.16 10:29 
Oh je! Ich habe die Werte falsch kopiert. :oops:
So ist es richtig;
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1637
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 27.01.16 10: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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mi 27.01.16 10:51 
user profile iconub60 hat folgendes geschrieben Zum zitierten Posting springen:
@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
ausblenden 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.
user profile iconub60 hat folgendes geschrieben Zum zitierten Posting springen:

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).

Für diesen Beitrag haben gedankt: Martok
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mi 27.01.16 11:07 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 515
Erhaltene Danke: 208

W7
Delphi 6 pro
BeitragVerfasst: Fr 05.02.16 12: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

_________________
Fietes Gesetz: use your brain (THINK)