| |
|
 Autor: |
|
Thema: Wer kann es schneller?
|
|
|
Raininger
(offline)
Newbie
Beiträge: 19
Geschlecht: 
Mitglied seit: 17.09.2013
Deutschland
|
|
Wer kann es schneller? #1
|
Datum: 04.02.2014, 13:35 
|
Um verschiedene Programmvarianten zur Ermittlung von Primfaktoren zu testen, habe ich die Zahlenreihe 10**18 (10 hoch 18) bis 10**18+10 verwendet. Von diesen 11 Zahlen sind 2 davon Primzahlen.
Zur Verringerung der Rechenzeit sollte man versuchen, die Zahl der Rechen-operationen zu minimieren. Ein erster Schritt wäre dabei nach einem Test mit der 2 nur die ungeraden Zahlen zu verwenden. Als nächste Verbesserung könnte man für die 2 und 3 eine wiederkehrende Regel aufstellen.
Nimmt man bei der 6er Reihe (= 2*3) die Zahlen -1 und +1, so werden auch alle Primzahlen erfaßt, z. B. 6-1 / +1 = 5 und 7
12-1 / +1= 11 und 13 usw.
Damit hätte man die Zahl der Rechenoperationen von 50% (alle ungeraden) auf 33% (6er Reihe) verringert. Die nächste Verbesserung wäre eine Schrittweite von 30
(= 2*3*5) zu wählen. Damit reduzieren sich die Rechenoperationen weiter auf 26,7%.
Die nächst mögliche Schrittweite wäre dann 210 (= 2*3*5*7). Damit reduziert sich der Rechenaufwand bei der Zerlegung in Primfaktoren auf 22,4%. Die Programme werden dabei allerdings immer länger, da alle Primzahlen bis 210 außer 2, 3, 5, 7 abgefragt werden müssen.
Diese Verbesserungen sind sehr deutlich in der Rechenzeit zu erkennen. Für die Zahlenreihe 10**18 bis 10**18+10 benötigt mein alter PC
bei 6er Schrittweite ca. 195 sec,
bei 30er Schrittweite ca. 148 sec und
bei 210er Schrittweite ca. 118 sec.
Die nächst mögliche Schrittweite ist 11*210= 2310, was allerdings inakzeptabel wäre.
Die Ergebnisse lauten:
10**18 = (2*5)**18
10**18+1 = 101*9901*999999000001
10**18+2 = 2*3*17*131*1427*52445056723
10**18+3 = Primzahl
10**18+4 = 2*2*1801*246809*562425889
10**18+5 = 3*5*44087*691381*2187161
10**18+6 = 2*7*919*77724234416291
10**18+7 = 1370531*729644203597
10**18+8 = 2*2*2*3*3*97*26209*32779*166667
10**18+9 = Primzahl
10**18+10 = 2*5*11*103*4013*21993833369
|
|
|
Matheniete
(offline)
Newbie
Beiträge: 10
Mitglied seit: 26.07.2012
Deutschland
|
|
|
Re: Wer kann es schneller? #2
|
Datum: 23.02.2014, 16:51
|
zitat: ICH!
Moin erstmal.
Es ist schön zu sehen, daß nicht nur ich mich mit der Primfaktorenzerlegung beschäftige.
Aber jetzt mal zur Erklärung, warum ich die Zerlegung schneller bewerkstellige.
Die Multiplikation ist die einzige(!) Rechenoperation, die auf Grund ihrer Struktur eine Zerlegung in die Ausgangszahlen, also sprich die beiden Faktoren, zulässt.
Um die 100.-Stelle der beiden Faktoren zu berechnen, bedarf es im "worst Case", also im schlechtesten Fall 3 Rechenoperationen, im besten Fall, eine.
Alle anderen Stellen der beiden Faktoren, also von der 101.-Stelle an, bedarf es im schlechtesten Fall 8, im besten Fall 2 Rechenoperationen. Ab der 102.-Stelle kommen noch drei Rechenoperationen dazu, jede weitere Stelle die vorherigen plus 3 Rechenoperationen.
Allerdings werde ich hier, auf Grund NSA und andere Mistviechter, weder die Struktur, noch den Algorithmus posten.
die Matheniete...
(Bisher wurde dieser Beitrag 3 mal editiert, als letztes von Matheniete am 23.02.2014 @ 18:44)
|
|
|
Raininger
(offline)
Newbie
Beiträge: 19
Geschlecht:
Mitglied seit: 17.09.2013
Deutschland
|
|
|
Re: Wer kann es schneller? #3
|
Datum: 25.02.2014, 15:18
|
Hallo Matheass,
das verstehe ich leider nicht, was du mit den Faktoren sagen willst. Du musst ja die Faktoren erst mal finden.
Ich glaube aber auch nicht, dass die NSA sich für Primfaktorenzerlegung interessiert.
Natürlich war das mit dem "kann es schneller" etwas humoristisch gemeint. Das hängt sebstverständlich u. a. auch von der Geschwindigkeit des Prozessors ab.
VG, R.
|
|
|
Raininger
(offline)
Newbie
Beiträge: 19
Geschlecht:
Mitglied seit: 17.09.2013
Deutschland
|
|
|
Re: Wer kann es schneller? #5
|
Datum: 05.10.2014, 21:07
|
Hallo Matheniete,
wenn du ein so tolles Rechensystem hast, zerlege mal die 9 Zahlen
10 hoch 20 bis (10 hoch 20) +8 in Primfaktoren.
Ist eine dieser Zahlen eine Primzahl?
Bei mir dauert diese Rechnung 13 Sekunden.
Bin gespannt auf dein Ergebnis.
Tschüss, Raininger
|
|
|
CHirt
(offline)
Newbie
Beiträge: 13
Geschlecht:
Mitglied seit: 19.05.2019
Deutschland
|
|
|
Re: Wer kann es schneller? #6
|
Datum: 06.06.2019, 21:05
|
Hallo an alle,
mein "Primelchen" kann jetzt (ab V1.9) auch Primzahlzerlegung und zerlegt die 11 Zahlen
von 10^18 bis 10^18+10 in 3 Sekunden,
von 10^18 bis 10^18+100 in 11 Sekunden und findet dabei 4 Primzahlen.
Da stellt sich natürlich die Frage wie man das vergleichen soll wenn jedes Programm auf anderer Hardware lief.
Vielleicht sollte der Threadersteller mal alle verfügbaren Programme auf seinem PC testen.
10^20 geht mit Primelchen leider nicht.
Anbei die Links zum Download. Diese sind 24/7 online bis ich sie wieder lösche z.B. für Updates.
Die Updates sind in diesem Thread:
http://www.hamiel.de/cgi-bin/sbb.cgi...34&start=0#1
MfG Carsten
(Bisher wurde dieser Beitrag 1 mal editiert, als letztes von CHirt am 15.06.2019 @ 00:25)
|
|
|
|
|
|
