Laufzeit Primzahlgenerator

[ssoul26]

Servus,

hat jemand von euch schon mal einen Primzahlgenerator geschrieben? Wie sehen die Laufzeiten aus?

Meine Ausgaben (Code nicht optimiert, Core 2 Duo 2GHz):

1. DEBUG
Generierte Primzahlen: 12000
Laufzeit: 2.0 s

2. DEBUG
Generierte Primzahlen: 25000
Laufzeit: 10.0 s

3. DEBUG
Generierte Primzahlen: 50000
Laufzeit: 32.0 s


Würd mich über Beiträge freuen :toll:

 

[redJava99]

Hi,
hab gerade was zusammengetippt und die Statistik sagt:

generated 11301 primes < 120000 in 0.8 seconds.
generated 25997 primes < 300000 in 6.3 seconds.
generated 49098 primes < 600000 in 10.1 seconds.

Auf einem Kern mit 4,2 GHz. Quadcore geringfügig schneller, viel zu parallelisieren gibts da nicht.

 

[JCODA]

Duration for generating 78.498 primes < 1.000.000 : 23 ms
Duration for generating 664.579 primes < 10.000.000 : 178 ms
Duration for generating 5.761.455 primes < 100.000.000 : 3.079 ms
Duration for generating 50.847.534 primes < 1.000.000.000 : 35.678 ms
Duration for generating 98.222.287 primes < 2.000.000.000 : 78.997 ms

auf einem Kern mit 3.5 GHz von einem Quadcore.

 

[ssoul26]

Ihr seit ja ziemlich schnell Überprüft ihr die Richtigkeit der generierten Primzahlen (gegenüberstellen mit schon vorhandenen Listen)? Welches Prinzip implementiert ihr?

 

[redJava99]

Ich machs nach der Hau-Drauf-Methode:
Gefundene Primzahlen = {2}
Für jede Zahl k = {3,..n} prüfe ich auf Teilbarkeit durch alle bereits gefundenen Primzahlen.
Ist keine kleinere Primzahl Teiler, ist k eine Primzahl und kommt in die Liste.
Der Test auf Korrektheit erfolgt damit implizit.

Bei JCODA interessiert mich die Methode auch brennend - die Dauer ist ja schon um einiges kürzer. Dafür findet er im angegebenen Intervall mehr Primzahlen als es eigentlich gibt. Beruhigt mich doch sehr ;-)

[Edit: JCODA hat seine Statistik korrigiert. Bleibt nur noch die Frage nach der Implementierung...]

 

[JCODA]

Ich hab vor 9 Minuten eine "bugfreie" Version reineditiert.
Ich benutze das Sieb des Eratosthenes ? Wikipedia

Und wenn ich die Optimierung vom Wiki einbaue, erhalte ich sogar:

Duration for generating 78.498 primes < 1.000.000 : 24 ms
Duration for generating 664.579 primes < 10.000.000 : 142 ms
Duration for generating 5.761.455 primes < 100.000.000 : 2.004 ms
Duration for generating 50.847.534 primes < 1.000.000.000 : 23.982 ms
Duration for generating 98.222.287 primes < 2.000.000.000 : 48.667 ms

 

[ssoul26]

Das Sieben ist wahrhaftig schwer zu toppen

Hab ein bisschen feintuning getrieben. So mal aktualisierte Zeiten (Core 2 Duo 2GHz):


1. DEBUG
Generierte Primzahlen: 100000
Laufzeit: 2.0 s

2. DEBUG
Generierte Primzahlen: 250000
Laufzeit: 7.0 s

3. DEBUG
Generierte Primzahlen: 700000
Laufzeit: 32.0 s

 

[ssoul26]

Neuer Testlauf mit einem i7.

Duration for generating 78.498 primes < 1.000.000 : 23 ms
Duration for generating 664.579 primes < 10.000.000 : 178 ms
Duration for generating 5.761.455 primes < 100.000.000 : 3.079 ms
Duration for generating 50.847.534 primes < 1.000.000.000 : 35.678 ms
Duration for generating 98.222.287 primes < 2.000.000.000 : 78.997 ms

Wie machst du das so schnell?? Über 90 Millionen Zahlen so schnell? Oder hab ich da einen Denkfehler


DEBUG
Generierte Primzahlen: 10000000
188540587
Laufzeit: 160.0 s

 

[Highchiller]

Wie wärs mit dem Sieb von Atkin?

Laut Wiki ist Erathos in O(N) operationen wobei Atkin in O(N/(log(log(N))) operationen läuft

 

[klauskarambulut]

i3-3220 @3.3 GHz

Duration for generating 4 primes < 10 : 0 ms
Duration for generating 25 primes < 100 : 0 ms
Duration for generating 168 primes < 1.000 : 1 ms
Duration for generating 1.229 primes < 10.000 : 10 ms
Duration for generating 9.592 primes < 100.000 : 8 ms
Duration for generating 78.498 primes < 1.000.000 : 11 ms
Duration for generating 664.579 primes < 10.000.000 : 67 ms
Duration for generating 5.761.455 primes < 100.000.000 : 1.313 ms
Duration for generating 50.847.534 primes < 1.000.000.000 : 15.977 ms
Duration for generating 98.222.287 primes < 2.000.000.000 : 32.846 ms
Duration for generating 105.097.564 primes < 2.147.483.647 : 35.927 ms

Wieviel speicher gibt denn JCoda seiner VM mit?

 

[DefconDev]

Auf wievielen Cores laufen diese Berechnungen? Ich denke mal nur auf einen oder?

Ich habe bisher noch nie mit Threads programmiert, wäre das nicht eine Option?

Jeweils einen Thread mit einem bestimmten Inverall durchlaufen lassen.

 

[Tobse]

Nicht super schnell... für die ersten 10 millionen 17,13 Sekunden. Auf einem Intel Core i5-4430 (3.1Ghz) und 2048MB Heap-Space.

188 primes in [1000; 999]: 67.0ms
Last prime: 997
1078 primes in [10000; 9999]: 16.0ms
Last prime: 9973
8415 primes in [100000; 99999]: 131.0ms
Last prime: 99991
69024 primes in [1000000; 999999]: 866.0ms
Last prime: 999983
586407 primes in [10000000; 9999999]: 16059.0ms
Last prime: 9999991

EDIT:
Der Zweite Anlauf lief besser (16,67 Sekunden für die ersten 10 Millionen, 7 Minuten und 21,61 Sekunden für die ersten 100 Millionen)

run:
188 primes in [1000; 999]: 1ms
Last prime: 997
1078 primes in [10000; 9999]: 4ms
Last prime: 9973
8415 primes in [100000; 99999]: 29ms
Last prime: 99991
69024 primes in [1000000; 999999]: 634ms
Last prime: 999983
586407 primes in [10000000; 9999999]: 16004ms
Last prime: 9999991
5097781 primes in [100000000; 99999999]: 424933ms
Last prime: 99999989
BUILD SUCCESSFUL (total time: 7 minutes 21 seconds)

 

[jakoberhard]

Hallo, die Berechnungen können sich sehen lassen. Bei mir rechnet er auf einem i7 mit zugewiesenen 6144MB Hash die PZ bis 1 mrd. In 62s. Nur bin ich bis jetzt noch nicht dahintergekommen, wie man das Ganze performant in eine Datei speichert (das ist der langsame Teil ;() Weiß jemand Rat?

 

[Lonsdaleit]

i3-3220 @3.3 GHz

Duration for generating 4 primes < 10 : 0 ms
Duration for generating 25 primes < 100 : 0 ms
Duration for generating 168 primes < 1.000 : 1 ms
Duration for generating 1.229 primes < 10.000 : 10 ms
Duration for generating 9.592 primes < 100.000 : 8 ms
Duration for generating 78.498 primes < 1.000.000 : 11 ms
Duration for generating 664.579 primes < 10.000.000 : 67 ms
Duration for generating 5.761.455 primes < 100.000.000 : 1.313 ms
Duration for generating 50.847.534 primes < 1.000.000.000 : 15.977 ms
Duration for generating 98.222.287 primes < 2.000.000.000 : 32.846 ms
Duration for generating 105.097.564 primes < 2.147.483.647 : 35.927 ms

Wieviel speicher gibt denn JCoda seiner VM mit?

Hi,

ich habe 2 Fragen hierzu:

1) Benutzt du das Sieb von Atkin? Und wenn ja, wie überprüfst du die Anzahl der Lösungen für die Gleichungen. Ich scheitere daran, dies performant zu implementieren.

2) Ist in den Zeiten das "herausschreiben" dieser Primzahlen in einer Liste oder der gleichen dabei, sodass man sich diese gefundenen Primzahlen auch ausgeben kann, oder zählst du nur einen counter hoch, wenn du eine Primzahl gefunden hast - kannst also nur die Anzahl der Primzahlen liefern, aber nicht welche es sind?


Gruß,
Lonsdaleit.

 

[Joose]

2) Ist in den Zeiten das "herausschreiben" dieser Primzahlen in einer Liste oder der gleichen dabei, sodass man sich diese gefundenen Primzahlen auch ausgeben kann, oder zählst du nur einen counter hoch, wenn du eine Primzahl gefunden hast - kannst also nur die Anzahl der Primzahlen liefern, aber nicht welche es sind?

Am performantesten ist es einfach nur die Anzahl der Primzahlen zu berechnen, wenn man aber noch wissen will welche Primzahlen gefunden wurden, dann sollte man diese in einer Liste abspeichern und ERST AM ENDE, diese auf der Konsole ausgeben oder in eine Datei schreiben.
Man kann natürlich noch mit Threads arbeiten und diese Aufgaben parallel laufen lassen (wobei hier mögliche locks die Performance wieder drücken könnten)

 

[Lonsdaleit]

Am performantesten ist es einfach nur die Anzahl der Primzahlen zu berechnen, wenn man aber noch wissen will welche Primzahlen gefunden wurden, dann sollte man diese in einer Liste abspeichern und ERST AM ENDE, diese auf der Konsole ausgeben oder in eine Datei schreiben.
Man kann natürlich noch mit Threads arbeiten und diese Aufgaben parallel laufen lassen (wobei hier mögliche locks die Performance wieder drücken könnten)

Dass es performanter ist sich nur die Anzahl berechnen zu lassen ist mir klar Deshalb habe ich die Frage ja gestellt ob in den Zeiten auch das ermitteln/abspeichern der expliziten Primzahlen dabei sind, oder ob in diesen Zeiten nur die Anzahl gemessen wird.

Gibt es einen nutzen dafür nur die Anzahl der Primzahlen zu kennen, aber nicht welche?

Gruß,
Lonsdaleit.

 

[Joose]

Dass es performanter ist sich nur die Anzahl berechnen zu lassen ist mir klar Deshalb habe ich die Frage ja gestellt ob in den Zeiten auch das ermitteln/abspeichern der expliziten Primzahlen dabei sind, oder ob in diesen Zeiten nur die Anzahl gemessen wird.

Da liegt das Problem bei allen Messungen in diesem Thread. Keiner schreibt wirklich dazu was ergemessen hat. Daher kann man schwer vergleichen.

Gibt es einen nutzen dafür nur die Anzahl der Primzahlen zu kennen, aber nicht welche?

Ich wüsste keinen, vielleicht gibt es einen. Kommt auf die Problemstellung an.

 

[jakoberhard]

i3-3220 @3.3 GHz

Duration for generating 4 primes < 10 : 0 ms
Duration for generating 25 primes < 100 : 0 ms
Duration for generating 168 primes < 1.000 : 1 ms
Duration for generating 1.229 primes < 10.000 : 10 ms
Duration for generating 9.592 primes < 100.000 : 8 ms
Duration for generating 78.498 primes < 1.000.000 : 11 ms
Duration for generating 664.579 primes < 10.000.000 : 67 ms
Duration for generating 5.761.455 primes < 100.000.000 : 1.313 ms
Duration for generating 50.847.534 primes < 1.000.000.000 : 15.977 ms
Duration for generating 98.222.287 primes < 2.000.000.000 : 32.846 ms
Duration for generating 105.097.564 primes < 2.147.483.647 : 35.927 ms

Wieviel speicher gibt denn JCoda seiner VM mit?

Hallo, hast Du Multiprozessing bzw. Threading aktiv? Du bist ca. 4x so schnell wie ich mit dem Sieb des E. Bei mir meckert er außerdem, wenn ich 2.147.483.647 eingebe: Heap voll, habe leider nur 8GB RAM. Du hast aber nicht das Sieb des Atkin verwendet? :bahnhof:Ich möchte versuchen, mehr Stellen zu berechnen, aber dafür benötige ich ein mehrdimensionales Array, wofür es nötig ist, mit Überträgen zu rechnen. Damit könnte man dann theoretisch (Rechenkapazität und Speicher vorausgesetzt), auch vollständige Primzahllisten mit z.B. 27 Stellen berechnen. (Was wohl etwas dauern würde )

 

[jakoberhard]

Feld mit Primzahlen bis 1000000000 fertig markiert
Primzahlen gezählt, es sind: 50847534
Primzahlen-Feld erzeugt
Benötigte Zeit: ca. 62 Sekunden
Primzahlen-Feld Ausgabe in Datei...
Ausgabe in Datei primzahlen-erastosthenes.txt fertig!
Benötigte Zeit für die Ausgabe: ca. 298 Sekunden
BUILD SUCCESSFUL (total time: 6 minutes 1 second)

... meine Ausgabe bei Primzahlen bis 1Mrd. Habe auch nur alle geraden Zahlen geprüft, schneller wirds so nicht.