laufzeitabschätzung

[andreas2505]

Hallo,

ich habe mal eine kleine frage.
Ich möchte dir Laufzeit abschätzen von einem Verfahren.
Dabei handelt es sich um einen Brute-Force-Algortihmus, der testen soll, ob es sich bei einer Zahl um eine Primzahl handelt.
Also dabei werden alle Zahlen bis zu der Wurzel der zu testenden Zahl geprüft, ob sie die zu testende Zahl teilen.
Wenn ich nun die Zahl 2^43112609 habe. Wielange würde das Verfahren ungefähr dauern und wieviel Speicherplatz würde benötigt werden. Kann mir wer erläutern, wie man darauf kommt und wie man das so grob rechnen muss.

 

[Marco13]

Wenige nanosekunden. Wenn die Zahl durch 2 teilbar ist, geht das ganze nämlich verdammt schnell.

Wenn es eine Primzahl (also eine der Form 2^irgendwas-1) ist, kann's ne Weile dauern.

Miss' die Zeit, die er braucht, um eine Pimzahl zu testen, die ungefähr 100000 ist. Teile diese Zeit dann durch 100000, und nimm sie mal sqrt(2^43112609).

Der Speicherplatz? Ist konstant... wenn man den Platz, der benötigt wird, um die Zahl an sich zu speichern, als konstant ansieht.

 

[Empire Phoenix]

warum nicht optimieren?
aka wenn 4 durch 2 teilbar ist, kann amn sich den check für 4 sparen (und auch für alle anderen geraden zahlen), das ist bei brute force schonmal fast ne 50%tige ersparniss

Speicherplatz ist in ajva sone sache, generall kansnt pro verwendeten int der nicht gelöscht werden kann, 4 byte rechenen nur kommt es halt trotzdem niemals hin, wegen garbage colector, minimum heapsize ect, hier hilft nur testen. Laufzeit ist das selbe, hängt ja von cpu speicher ect ab.

 

[javimka]

Wie lange du brauchst für 2^43112609-1? Länger als du lebst!

Speicherplatz:
Um das Resultat in Binärform abzuspeichern brauchst du 43'112'608 binäre Stellen, das sind etwa 41 MB. Ausserdem musst du noch die Wurzel dieses Resultat speichern, was die Hälfte ist. Also insgesamt etwa 62 MB. Kein Problem.

Laufzeit:
2^10 gibt ungefähr 1000. Ein Exponent von 10 sorgt also für 3 Stellen. Dein Wahnsinnsexponent wird zu einem Resultat führen, das über 12'933'782 Stellen hat. Die Wurzel davon hat 6466891 Stellen. Anstatt die Teilbarkeit für alle Zahlen zu testen, kannst du dich auf Primzahlen beschränken.
Aus der Zahlentheorie wissen wir, dass die Anzahl primzahlen kleiner n ungefähr n/ln(n) ist. Es gibt also 10^6466891 / ln( 10^6466891) Primzahlen, die kleiner als die Wurzel sind. Den Logarithmus im Divisor kann man ausrechnen: = ln(10)*6466891 = 1.4*10^7. Daraus ergibt sich als Anzahl Primzahlen, die zu testen sind 10^(6466891-7) = 10^6466884, was ne ganze Menge ist. Im Universum vermutet man 10^79 Protonen.

Die grösste bekannte Primzahl hat anscheinend 10 Mio Stellen. Wie man die gefunden hat, weiss ich auch nicht.

Hoffe, ich hab mich nirgendwo verrechnet.