Optimierung C++ Primzahlen?

[Defenz0r]

Hallo,

ich habe mir ein Programm zur Berechnung von Primzahlen geschrieben, leider ist es nicht sehr Performant
und habe ca. eine Auslastung von 20% bei der Berechnung.

Hier der Code:

#include <iostream>
using namespace std;

int main()
{
    int x=0, i=0;
    int anzahl=0,zaehler=0;

    cout<<"Programm zur Berechnung von Primzahlen"<<endl;
    cout<<"Eingabe der Durchlauefe "<<endl;
    cin>>anzahl;

    for(x=2; x<=110000; x++)
    {

    for(int durchlauefe=0; durchlauefe<anzahl; durchlauefe++)

        for(i=2; i<x; i++)
        {
            if(x%i==0) break;
        }

        if(i==x)
        {
             zaehler++;
        }

        if(i==x) cout<<i<<" Ist eine Primzahl. "<<" Nr. "<<zaehler<<endl;
        }


    return 0;

}

Die Berechnungszeit steigt Linear an.

Int x ist meine momentan maximale Genauigkeit.

 

[bingo88]

Über schnellerer Algorithmen zur Primzahlsuche gibt es genügend Forschungsarbeiten. Aber ich vermute mal, du lastest nur einen Kern aus, daher die geringe Prozentzahl

 

[Defenz0r]

Keine Ahnung, wie Multithreading funktioniert.

Ich habe gerade ein Skript gefunden, kann mir mal jemand erläutern wie das genau funktionier? :

#include "iostream"

int main(int argc, char** argv)
{
   unsigned int prime_nb = 2;
   unsigned long i = 5;
   unsigned int k;
   bool found;
   for(;;)
   {
      found = true;
      for(k = 2; k < i; ++k)
         if(!(i % k))
            found = false;
      if(found)
         ++prime_nb;
      if(prime_nb >= 10001)
         break;
      i += 2; // all even numbers are not prime
   }
   std::cout << i;
   return 0;
}

int main(int argc, char** argv)

Zwei Sterne für Char?
++k? heißt das nicht k++?
Warum long?
Warum for( ; ; ) ?? muss da nicht etwas rein?

Bzw. kann jemand dieses Skript etwas kommentieren, Verständnishalber?


Danke

 

[bingo88]

Keine Ahnung, wie Multithreading funktioniert.

Das ist in so einem Fall auch nicht unbedingt trivial umzusetzen

int main(int argc, char** argv)

Zwei Sterne für Char? "Zeiger auf einen Zeiger" -> ist das gleiche wie char *argv[]
++k? heißt das nicht k++?
Warum long? Macht bei den mir bekannten x86 32-Bit Compilern keinen Unterschied zu int (bei 16 Bit war int nur 16 Bit groß, long aber 32)
Warum for(; ?? muss da nicht etwas rein? Das ist ne Endlosschleife, da muss nichts rein (ist wie ein while (true) { ... })

Ach ja, und es heißt #include <iostream>...

 

[Defenz0r]

Das Skript ist wie beschrieben nicht von mir.
Du kannst nicht sagen es heißt so oder so.
Es gibt andere Leute die Ihren eigenen Stil haben.


Das ist alles.

 

[bingo88]

Es gibt andere Leute die Ihren eigenen Stil haben.

Das hat nichts mit Stil zu tun, sondern ist im schlimmsten Fall sogar falsch (compilerabhängig):

#include "bla.h" sucht nach blah.h im AKTUELLEN Verzeichnis
#include <blah.h> sucht in den (eingestellten) Systemverzeichnissen

Es galt jetzt auch nicht dir persönlich, sondern es war einfach eine Feststellung

 

[Defenz0r]

Achso, ich fühlte mich etwas angegriffen ^^
Ich übe diese Sachen (Project Euler) , weil ich glaube das es mir etwas bringt.
Bin ja in einer Ausbildung zum FIAE, s. Profil.

lg

 

[bingo88]

Achso, ich fühlte mich etwas angegriffen ^^

Nee, war wirklich nicht so gemeint, sorry!

Ich übe diese Sachen (Project Euler) , weil ich glaube das es mir etwas bringt.
Bin ja in einer Ausbildung zum FIAE, s. Profil.

Ist ja nicht verkehrt, sich so was mal anzusehen, um daraus zu lernen. Wie gesagt, es gibt sicher genug Material dazu (Primfaktorzerlegung wird z. B. bei SSL/RSA verwendet), einfach mal danach im Netz suchen.

 

[mtheman2011]

++k? heißt das nicht k++?
...
Warum for( ; ; ) ?? muss da nicht etwas rein?



Danke

Beides wird vom Compiler in k =k+1 übersetzt, aber ++k kann unter bestimmten umständen leicht bessere performance bieten. Ist aber relativ irrelevant. Es funktioniert jedenfalls beides.

Und for( ; ; ) ist eine endlosschleife genauso wie while(true). Es gibt einfach keine abbruchbedingung aber mittels break kann die Schleife verlassen werden.

 

[DMA]

Zwei Sterne für Char? "Zeiger auf einen Zeiger" -> ist das gleiche wie char *argv[]

Nunja, also char** ist nicht das Selbe wie char*[], nur der äußere Effekt ist der Gleiche, die Logik dahinter eine andere.

Ansonsten, Primzahlen zur Laufzeit zu berechnen ist so oder so nicht sonderlich effektiv - zumindest mit den momentanigen Methoden.
Also gerade die Modulo-Operation verschlinkt verhältnismäßig viel Zeit.
Je nachdem wie du den Algorithmus gestaltest, kannst du das Teil aber etwas „effektiver“ gestalten.

Allerdings glaub eich kaum, dass du Primzahlen im großen Stile in deiner FIAE Ausbildung gebrauchen wirst und das Ganze wohl eher eine Übung sein soll(te), damit du mehr vertraut mit der Umsetzung von Problemstellungen bist.

 

[ofhouse]

Beides wird vom Compiler in k =k+1 übersetzt, aber ++k kann unter bestimmten umständen leicht bessere performance bieten. Ist aber relativ irrelevant. Es funktioniert jedenfalls beides.

Ich weiß zwar nicht, ob die Performance besser ist (das können nur Nanosekunden sein), aber k++ und ++k machen zwar augenscheinlich dasselbe, sind aber auf keinen Fall gleich.
Bei Rechenausdrücken spielt das ne große Rolle, hier 2 Beispiele:

++k zählt k hoch und rechnet dann den Ausdruck aus und speichert ihn in z.

int k = 2;
int z = ++k + 2;
// z = 5; k = 3

k++ rechnet erst den Ausdruck aus und speichert ihn in z und zählt danach k hoch.

int k = 2;
int z = k++ + 2;
// z = 4; k = 3

 

[mtheman2011]

Interessant. Is mir noch nie in der Form vorgekommen, weil ich solche Sonderausdrücke immer in Klammern schreibe. Ist aber gut zu wissen.
Ja hab ja gesagt nicht relevant aber wenn das innerhalb einer schleife passiert und auf Leistungsschwacher Hardware(langsame arm cortex prozessoren zum beispiel) ausgeführt wird kann das Auswirkungen auf das Laufzeitverhalten im Sekundenbereich haben. Kommt aber auch auf die Hardware an.

 

[DarkMo]

hab die ganze zeit des lesens scho nach nem bsp gesucht ofhouse ^^ ich wusst auch nur, dass ++k "vorher" ausgeführt wird und k++ eben "nachher". aber nen rechten anwendungsfall (vor oder nach was?) kannte ich auch noch ned *g* so sin die studenten: theoretisch profis aber praktisch nullen

 

[fadade]

so sin die studenten: theoretisch profis aber praktisch nullen

Also das sieht bei mir ja gaaanz anders aus!

-> Primzahlensuche kannst du nicht groß optimieren ... man sucht halt ... da kannst du erst bei 2903487907507 anfangen, weil die davor bestimmt schon bekannt sind, man kann Intervalle auf verschiedene Threads aufteilen, aber viel gibts da nicht mehr rauszuholen.

 

[Olstyle]

Mal eine relativ einfache Variante die mit zunehmender Menge an Zahlen schon mal deutlich schneller ist:
Sieb des Eratosthenes
Irgendwo hab ich auch noch ein entsprechendes C.Programm rumfliegen.

 

[ofhouse]

Als Motivation, die neueste Primzahl hat 17 millionen Stellen

Newly-discovered prime number is more than 17 million digits long | The Verge