Primzahlen Contest

[Bunny_Joe]

Ich frage mich gerade, um wie viel schneller das in OpenCL ablaufen würde...oder obs überhaupt sinnvoll von der GPU verarbeitet werden könnte.

edit:

Eben das hier gefunden: primesieve - Fast prime number generator
Für 10^9 braucht er gerade mal 0.03 Sekunden bei mir. Also ein ziemlich guter Algorithmus. Allerdings nur CPU.

 

[nay]

Wäre es vielleicht noch interessant den Speicherverbrauch zu messen?

 

[Crysis nerd]

Hatte übers Wochenende zu tun, aber hier noch mal meine aktuellen Ergebnisse.

Mein Programm ist immer noch single thread, nutzt aber jetzt "richtige" factorization wheel Optimierung. Die Werte für Primzahlen unter 1Mrd:

Version | Zeit | Speicher
wheel-2 | 4.1s | 67 MB
wheel-2-3 | 3.6s | 47 MB
wheel-2-3-5 | 2.7s | 39MB
wheel-2-3-5-7 | 2.35s | 35 MB

Speicher habe ich mit "/usr/bin/time -v" gemessen, die Zeit im Programm direkt.

Diese hochoptimierte C++ Version habe ich auch gefunden. Klar kann man noch jede Menge machen. Mal sehen, wie weit ich komme ohne vom idiomatischen Rust abzuweichen. Den Code für die Benchmarks gibt es übrigens hier: https://gist.github.com/LukasKalbertodt/b0dedf364263d99858cf

EDIT: Die hochoptimierte C++ Version braucht 0.7 sek bei mir. Also ca Faktor 35 besser als meine beste...

 

[nay]

Ich hab diese Version gefunden: https://github.com/kimwalisch/primecount

Braucht bei meinem i5 760 mit 4 Threads 0.01 Sekunden für Primzahlen bis 1 000 000 000. Wenn man das unterbieten will muss man sich warm anziehen