Home | Registrieren | Mitgliederliste | Suchen | Hilfe | Themen des Tages | Alle Lampen aus | Login
Guten Tag, Gast

Wenn dies Dein erster Besuch hier ist, lies Dir die FAQ - Häufig gestellte Fragen durch. Du musst Dich vermutlich Registrieren, bevor Du Beiträge schreiben kannst: klicke oben auf registrieren, um den Registrierungsprozess zu starten. Um Beiträge zu lesen, suche Dir einfach das Forum aus, das Dich interessiert. Die Registrierung ist kostenlos.
Username:
Passwort:
Suchen:


Seiten: <<  1  >>
Board >>  Einfach drauf los >>  Einfach drauf los >> Wer kann es schneller?
Neues Thema    »Antworten«
Seite Drucken
red.gif Autor:
Thema: Wer kann es schneller?
Raininger (offline)
Newbie



Beiträge: 19
Geschlecht:
Mitglied seit: 17.09.2013

Deutschland
icon1   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
     PM   Buddy hinzufügen Copy Quote
Matheniete (offline)
Newbie



Beiträge: 10

Mitglied seit: 26.07.2012

Deutschland
icon1   Re: Wer kann es schneller? #2 Datum: 23.02.2014, 16:51  

zitat:
Wer kann es schneller?
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)
   PM   Buddy hinzufügen Copy Quote
Raininger (offline)
Newbie



Beiträge: 19
Geschlecht:
Mitglied seit: 17.09.2013

Deutschland
icon1   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.
     PM   Buddy hinzufügen Copy Quote
Matheniete (offline)
Newbie



Beiträge: 10

Mitglied seit: 26.07.2012

Deutschland
icon1   Re: Wer kann es schneller? #4 Datum: 25.02.2014, 16:42  


Moin,
zitat:
das verstehe ich leider nicht, was du mit den Faktoren sagen willst. Du musst ja die Faktoren erst mal finden.
Das muss ich eben nicht. Natürlich ist die Rechenvorschrift, die du in der Schule gelernt hast, hinderlich, wenn du die Struktur der Multiplikation finden willst.

Stell dir eine Frage: Warum reicht das kleine Ein mal eins aus, um beliebig lange Zahlen miteinander zu multiplizieren?

Schreib mal die Zahlen in folgender Form:

an...a5a4a3a2a1a0

wobei a für die Ziffer und der Index für den Exponenten der jeweiligen Stelle steht und multiplizier mal 2 solche Zahlen. Gibt geile Erkenntnisse...


die Matheniete...

(Bisher wurde dieser Beitrag 1 mal editiert, als letztes von Matheniete am 25.02.2014 @ 16:44)
   PM   Buddy hinzufügen Copy Quote
Raininger (offline)
Newbie



Beiträge: 19
Geschlecht:
Mitglied seit: 17.09.2013

Deutschland
icon1   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
     PM   Buddy hinzufügen Copy Quote
Board >>  Einfach drauf los >>  Einfach drauf los >> Wer kann es schneller?
Seiten: <<  1  >>
Seite Drucken
Neues Thema    »Antworten«



Forum durchsuchen:


   


Stefanos Bulletin Board, v1.3.7
© Coder-World.de, 2001-2005 (Stefanos)