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

redrew99

Habe ein Programm geschrieben für die Primzahlenberechnung mittels Sieb des E.,
( http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo25.php )
die Algorithmen dafür sind soweit umgesetzt, Primzahlen bis 10^6 werden in ca. 16s auf der Konsole ausgegeben. Bin mir allerdings nicht sicher, inwieweit da noch Optimierungen möglich sind. Wenn jemand Vorschläge hat....

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
  unsigned long long int n;
  unsigned long long int y;
  cout<<"Bitte geben sie die Zahl ein, "<<endl;
  cout<<"bis zu der Primzahlen berechnet werden sollen: "<<endl;
  cin>> n;
  unsigned long long int z=n-1; //Anzahl der Primzahlen.
  y=sqrt(n);    //Da Primzahlen nur bis zur Wurzel von n berechnet werden müssen

  vector<bool> vb(n); //1.alle Zahlen von 2 bis n in einer Liste.

  for(unsigned long long int i=2;i<=y;i++)
  {
    if(vb[i]==(false))   //2. für jede Zahl i: =2 bis Wurzel n IN DER LISTE führe aus
    {
     for(unsigned long long int k=(n/i);(k>=i);--k) //3.für jede Zahl k:= n/i IN DER LISTE in
                                                //absteigender Reihenfolge
     {
       if(vb[k]==(false))                       //3...IN DER LISTE
      {
        if((i*k)<n)
         {
           vb[i*k]=(true);               //i*k werden "gestrichen"
         }
         z-=1;                           //n-markierte Primzahlen=Primzahlen
      }
     }
   }
}
//Ausgabe der Primzahlen  
for(unsigned long long int j=2;j<vb.size();j++)  //j<vb.size,weil das letzte Elemente
                                                   //.size-1 ist.
  {
      if(vb[j]==(false))
      {
        cout<<" "<<j;
      }
  }
  cout<<endl<<"Primzahlen: "<<z<<endl;
  return 0;
 }

volkard

i*k muss weg!!
Du kannst auch wegpos-=k machen.

Warum eigenlich ist die Schleife rückwärts? Ich kenne 92 Gründe für Vorwärts aber nur 18 Gründe für Rückwärts.

hustbaer

man lässt glaube ich üblicherweise die geraden zahlen weg. dadurch kann man bei gleichem speicherverbrauch und ähnlicher laufzeit doppelt so viele zahlen sieben.

ichbineinnoob

Das schaut doch ganz ordentlich aus.

Ist mir so beim Überfliegen aufgefallen:

In Zeile 22 schreibst du (k>=2); , aber in Zeile 27 geht es nur weiter, wenn if(k>=i).

redrew99

volkard schrieb:

i*k muss weg!!

Stimmt, vb[i*k]=(true) ist doppelt drin, da ist ein Fehler bei Copy & Paste passiert.

volkard schrieb:

Du kannst auch wegpos-=k machen.

Das verstehe ich leider nicht, was meinst du damit?

volkard schrieb:

Warum eigenlich ist die Schleife rückwärts? Ich kenne 92 Gründe für Vorwärts aber nur 18 Gründe für Rückwärts.

Wenn die Schleife vorwärts läuft, wird z.B. bei i=2 und k=2,n=4 gestrichen. Im übernächsten Schritt wäre i=2;k=4, da n=4 aber schon gestrichen wurde, bliebe n=8 stehen.

Läuft die Schleife rückwärts, hat man diese Problematik nicht.

ichbineinnoob

Die geraden Zahlen lässt man tatsächlich aus. Aber das geht in vector<bool> wohl nicht.

Aber du kannst in Zeile 18 mit i=3 anfangen und dann immer i+=2; weiter gehen. Am Ende auf gleiche Weise einfach nicht die geraden Zahlen ausgeben.

redrew99

ichbineinnoob schrieb:

Das schaut doch ganz ordentlich aus.

Ist mir so beim Überfliegen aufgefallen:

In Zeile 22 schreibst du (k>=2); , aber in Zeile 27 geht es nur weiter, wenn if(k>=i).

Ja, stimmt, irgendwie unlogisch.
Hab Zeile 22 gleich mal auf (k>=i) korrigiert.

Nachtrag: Dementsprechend ist dann natürlich auch die if-Abfrage in Zeile 27
überflüssig, auch gleich mit korrigiert.

redrew99

Eigentlich müßte es doch auch möglich sein, die Ausgabe auf der Konsole anstelle einer separaten Schleife jeweils dann zu tätigen, wenn i zum nächsten Wert(z.B. i*i) springt bzw. gesprungen ist, da alle Zahlen dazwischen, die nicht gestrichen wurden, Primzahlen sein müssen.

ichbineinnoob

redrew99 schrieb:

Eigentlich müßte es doch auch möglich sein, die Ausgabe auf der Konsole anstelle einer separaten Schleife jeweils dann zu tätigen, wenn i zum nächsten Wert(z.B. i*i) springt bzw. gesprungen ist, da alle Zahlen dazwischen, die nicht gestrichen wurden, Primzahlen sein müssen.

Ja, ab i abwärts ist die Liste "fertig"

hustbaer

ichbineinnoob schrieb:

Die geraden Zahlen lässt man tatsächlich aus. Aber das geht in vector<bool> wohl nicht.

Wieso sollte das mit vector<bool> nicht gehen? Einfach den Index halbieren...

vector<bool> ist eine Spezialisierung von vector, um pro Bool-Wert auch tatsächlich nur ein Bit zu verwenden. Theoretisch könnte ein vector<char> schneller sein. Praktisch muss man es nachmessen.

EOutOfResources

manni66 schrieb:

Theoretisch könnte ein vector<char> schneller sein.

Wegen was? Der Bitmaske?

SeppJ

EOutOfResources schrieb:

manni66 schrieb:

Theoretisch könnte ein vector<char> schneller sein.

Wegen was? Der Bitmaske?

Weil vector<bool> eine unnötig komplizierte Spezialisierung ist, während ein vector<char> der übliche schnelle vector wäre.

SeppJ

SeppJ schrieb:

EOutOfResources schrieb:

manni66 schrieb:

Theoretisch könnte ein vector<char> schneller sein.

Wegen was? Der Bitmaske?

Weil vector<bool> eine unnötig komplizierte Spezialisierung ist, während ein vector<char> der übliche schnelle vector wäre.

Was noch wichtig ist: Solche Überlegungen müssen nicht stimmen. Man kann zum Beispiel leicht vergessen, dass ein vector<bool> viel bessere Lokalität hat. Wenn der ganze vector (oder große Teile) in den CPU-Cache passen, dann ist das ein gewaltiger Vorteil. Ich hab's mal ausprobiert:

#include <vector>
#include <iostream>
#include <cstddef>

using namespace std;

typedef vector<bool> container;  // Hier entsprechend auf char oder bool setzen

int main()
{
  const size_t max_n = 100000000;
  container numbers(max_n, 1);
  for (unsigned n=2; n<max_n; ++n)
    if (numbers[n])
      for (unsigned i=2*n; i<max_n; i+=n)
        numbers[i]=0;
  unsigned long anti_optimizer = 0;
  for (unsigned n=2; n<max_n; ++n)
    if (numbers[n])
      anti_optimizer += n;
  cout<<"Summe aller Primzahlen bis "<<max_n<<" ist "<<anti_optimizer<<".\n";
}

Die vector<char> Version rechnet bei mir (Core 2, g++, -O3 -xHOST) knapp 8 Sekunden, der vector<bool> etwas über 5 Sekunden. Also ganz klarer Sieg für den kleinen, aber komplizierten, Datentyp.

volkard

SeppJ schrieb:

Wenn der ganze vector (oder große Teile) in den CPU-Cache passen, dann ist das ein gewaltiger Vorteil.
...
Die vector<char> Version rechnet bei mir (Core 2, g++, -O3 -xHOST) knapp 8 Sekunden, der vector<bool> etwas über 5 Sekunden. Also ganz klarer Sieg für den kleinen, aber komplizierten, Datentyp.

Jup. Der vector paßt wohl gerade rein? Rein interessehalber ie steht's bei max_n=1e9?

*Rewind*

SeppJ schrieb:

Die vector<char> Version rechnet bei mir (Core 2, g++, -O3 -xHOST) knapp 8 Sekunden, der vector<bool> etwas über 5 Sekunden. Also ganz klarer Sieg für den kleinen, aber komplizierten, Datentyp.

ich weiß nicht mit welchem Code du getestet hast, aber ich hab's mal mit deinem probiert (max_n = 100000000;). Ergebnis:

vector<char> container; -> 9s
vector<bool> container; -> 19s

Edit: hab die Angaben korrigiert.

camper

Auf meinem Rechner (Atom 330) mit n=100000000:
char: 10.35s
bool: 12.75s

Die Lokalität mit bool ist nicht von besonders großem Vorteil, wenn man bedenkt, dass bool für jeden einzelnen Wert sowohl eine Lese- als auch eine Schreibvorgang impliziert. Wärend mit char nur geschrieben wird - hier könnte man ggf. auch low-level optimieren, z.B. mit unsigned arbeiten und ungeordnet schreiben.

volkard

[Rewind] schrieb:

probiert (max_n = 1000000;). Ergebnis:
vector<char> container; -> 2-3s
vector<bool> container; -> 32-33s

Naja, -O3 muß schon sein. Am besten auch -march=native.
So lahm kann Dein Rechner gar nicht sein.

Bei mir:
Bis 1e5
bool: 0.0014
char: 0.0015

Bis 1e6
bool: 0.14
char: 0.18

Bis 1e7
bool: 1.08
char: 1.84

Bis 1e8
bool: 13.77
char: 21.11

Und der Prozessor ist nicht neu. AMD Sempron 3000+ @ 1800MhZ.

SeppJ

[Rewind] schrieb:

ich weiß nicht mit welchem Code du getestet hast, aber ich hab's mal mit deinem probiert (max_n = 1000000;). Ergebnis:

vector<char> container; -> 2-3s
vector<bool> container; -> 32-33s

Das widerspricht sich ja auch nicht. Je nach Compiler und System können schon so große Unterschiede auftauchen. Anscheinend hat deine Standardbib einen sehr schlechten vector<bool>, meine einen sehr guten. Darf ich fragen, welcher Compiler?

volkard schrieb:

Jup. Der vector paßt wohl gerade rein? Rein interessehalber ie steht's bei max_n=1e9?

Eigentlich nicht, der Prozessor müsste irgendwie so um 2-4MB Cache haben. Der vector müsste aber mindestens 12.5 MB groß sein.

Abgesehen davon, dass ich gerade an einem anderen Rechner sitze, dürfte mein Core2 Rechner jedoch Probleme mit 1 Milliarde char bekommen, von der RAM-Größe her, daher unvergleichbar.

Ich sitze gerade an einem i7 mit viel mehr RAM und vergleichbar großem Cache, da probiere ich mal (gleicher Compiler wie oben) mit 1 Milliarde:
vector<bool>: gut 24 Sekunden
vector<char>: knapp 26 Sekunden

Sehr interessant. Ich lasse mal im Hintergrund mit 8 Milliarden laufen und melde mich in 10-20 Minuten mit den Ergebnissen.

edit: Ach, dazu habe ich nicht die Geduld. Dafür die Ergebnisse von dem i7 Rechner mit 100 Millionen:
bool: 1.75 Sekunden
char: 2 Sekunden

Da das auch ungefähr das gleiche ist wie bei 1 Milliarde, breche ich mal den 8 Milliarden test ab, da wird sicherlich nichts großarti anderes rauskommen.

*Rewind*

Wie bereits in der letzten Antwort dazugeschrieben, die Zeitangaben habe ich korrigiert (9s für char und 19s für bool mit n=100mil). Ich verwende momentan VS2008 PE.