Primzahlenberechnung - Sieb des Eratosthenes - Was kann noch optimiert werden?

camper

redrew99 schrieb:

Nicht schlecht, der Code, leider habe ich die Boostbibliotheken nicht installiert (Codeblocks), um ihn testen können. werde aber mal versuchen, die genannten Optimierungsvorschläge in mein Programm mit einzubauen.

Danke soweit erstmal @all , habe viele Anregungen bekommen, was man noch besser machen kann.

@Camper:
Den Programmcode verstehe ich leider nur zu ca. 20% oder so

wo gibt es Probleme? Das Einzel-Sieben geschieht in sieve_residue_class.
Der eigentliche Streichvorgang geschieht dabeiin den Zeilen 129 und 130.

Die Schwierigkeit besteht darin, den Schleifenanfang zu finden (Zeilen 119-127).
Die kleinste Zahl, die für eine gegebene Primzahl v gestrichen werden muss ist v*v (kleinere Vielfache werden bereits durch andere Primzahlen gestrichen).
Allerdings liegt n*n im Allgemeinen nicht in der Restklasse, die gerade bearbeitet wird. Gesucht wird deshalb die kleinste Zahl k >= v für die k * v bei der Division durch p den gerade untersuchten Rest lässt.
Die Mathematik dahinter zu erklären überlasse ich anderen. Da es sich um eine bereits optimierte Variante handelt, dürfte der Algorithmus schwierig zu verstehen sein, ich verweise deshalb mal auf den zuvor von mir gezeigten Code, Zeilen 77-79, die sinngemäß das Gleiche tun.

redrew99

camper schrieb:

redrew99 schrieb:

Nicht schlecht, der Code, leider habe ich die Boostbibliotheken nicht installiert (Codeblocks), um ihn testen können. werde aber mal versuchen, die genannten Optimierungsvorschläge in mein Programm mit einzubauen.

Danke soweit erstmal @all , habe viele Anregungen bekommen, was man noch besser machen kann.

@Camper:
Den Programmcode verstehe ich leider nur zu ca. 20% oder so

wo gibt es Probleme? ...

Passt schon, als Anfänger bin ich mit so einem Programm halt restlos überfordert.
Aber wenn ich das soweit richtig verstanden habe, beruht der Großteil der Schnelligkeit der Berechnung darin, daß im Vorfeld durch Modulo-Algorithmen Zahlenbereiche ausgeschlossen werden. Ob z.B. alle möglichen Algorithmen, was das
Sieb des E. oder A. anbetrifft, umgesetzt worden sind,weiß ich nicht.
Falls nicht, könnte man das Programm eventuell noch schneller machen.....
wäre doch oder nicht ?

camper

Falls noch Interesse besteht, hier gibt es eine neue Version zum Herumspielen.
Getested mit gcc und msvc2010.
Compilieren per g++ -DNDEBUG -std=c++0x -march=native -O3 -o prime prime.cpp -DCACHE_SIZE=32768 -lboost_thread oder ähnlich
nur ca. 200 sec bis 1e11 mit 4 threads (atom 330)

redrew99

camper schrieb:

Falls noch Interesse besteht,...

jupp, tut es.

volkard

Tat es. Aber ich bin viel mehr an den Erkenntnissen interessiert, die Dich zu dem Code führten, als an dem Code selber. Warum hast Du diesen und jenen Weg beschritten? Zum Teil mathematische Tricks, zum Teil Programmiertricks, die ich übersehen hätte, zum Teil Messungen. Alles supi interessant.

Aber Du wandelst auf Abwegen, fürchte ich, und zählst nur Primzahlen.

Netter wäre vielleicht

SomeVeryCheapHash crc;
for(PrimeGenerator pg(0,1e11);!pg.isEmpty();pg.pop())
   crc.eat(pg.peek());
cout<<crc.getValue()<<'\n';

Oder sowas. Klar, wir können nicht alle Primzahlen mit cout anzeigen.

Es sollte auch single threaded bleiben, weil der Anwender deines Primzahlengenerators höchst wahrscheinlich ein Problem hat, das er selber sehr problemangemessen in Threads aufteilen kann.

Noch netter wäre oft, daß in der Tat nur ein Fenster wie [1e14;1e14+1e9[ untersucht wird. Und den Code bitte hier posten, dann ist er in 20 Jahren noch verfügbar.

Vielleicht interessant wäre auch ein Stück-Für-Stück-Aufau-Beschreibungs-Artikel im Magazin.

redrew99

Würde eine Anpassung des Codes an einen Mehrkernprozessor Geschwindigkeitsvorteile bringen?

SeppJ

redrew99 schrieb:

Würde eine Anpassung des Codes an einen Mehrkernprozessor Geschwindigkeitsvorteile bringen?

Ich werde jetzt keinen monatealten Thread mit 5 Seiten komplett durchlesen, was gerade "der Code" ist, aber ich kann dir allgemein sagen, dass das Sieb des Eratosthenes parallelisierbar ist. Und das bringt natürlich etwas.

volkard

camper schrieb:

Jede Restklasse kann separat gesiebt werden, diese Einzelsiebe sind ganz nebenbei kleiner, was das Cacheproblem reduziert. Zudem biete sich hier eine Parallelisierung an.