Performance Optimierung

Ich habe Folgendes Programm zum Zählen von Primzahlen im Bereich 1 bis 1 Mrd geschrieben:

//Anzahl der Primzahlen zwischen 1 und 1 Mrd. ermitteln

#include <iostream>
#include <cmath>
#include <conio.h>
using namespace std;

double c;
unsigned int counter=1,b;
bool isprim=false;

int main()
{
    unsigned int a;
    for(a=3;a!=1000000001;a+=2)                   //Jede zweite Zahl zwischen 3 und 1 Mrd testen
    {
        isprim=true;
        for(b=2,c=sqrt(a); b<=c; ++b)     //alle zahlen zwischen 1 und der wurzel
        {                                 //der aktuellen zahl testen

            if(!(a%b))                    //wenn a durch eine zahl glatt teilbar ist,
            {                             //schleife abbrechen und nichts weiter passiert
                isprim=false;
                break;
            }
        }
        if(isprim)                        //wenn die innere schleife nicht abgebrochen wurde
            ++counter;                    //ist a eine primzahl und counter wird inkrementiert
    }

    cout<<counter;                        //ausgeben von counter
    getch();
}

Gibt es einen effektiveren Algorithmus oder irgendwelche Optimierungen bei diesem Code?
Ich denke, die meiste Rechenzeit benötigen a%b und sqrt(a). Allerding weis ich nicht, wie ich diese Ausdrücke umgehen könnte.
Jemand eine Idee?

betheman schrieb:

Gibt es einen effektiveren Algorithmus

Bei diesem "kleinen" Zahlenbereich ist das Sieb des Eratosthenes durchaus noch praktikabel.

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Hab es jetzt nicht getestet, aber dein Ansatz scheint so eine Art CPU-Burn zu sein.

Wie lange ging denn ein Durchlauf?

Dravere

Stichwort: Sieb des Eratosthenes
Wikipedia: http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Grüssli

PS: Ich hoffe du willst deinen Code nicht als C++ durchgehen lassen

Fellhuhn

b=2,c=sqrt(a); b<=c;

ist doch das gleiche wie:

b=2; b*b <= a;

Spart Zeit.

Dravere schrieb:

Stichwort: Sieb des Eratosthenes
PS: Ich hoffe du willst deinen Code nicht als C++ durchgehen lassen

Was meinst du damit? Weil ich keine Klassen/Funtkionen beutze?

hustbaer

Fellhuhn schrieb:

b=2,c=sqrt(a); b<=c;
ist doch das gleiche wie:
b=2; b*b <= a;
Spart Zeit.

Das ist jetzt ein Scherz, oder?

Nexus

betheman schrieb:

Was meinst du damit? Weil ich keine Klassen/Funtkionen beutze?

Wahrscheinlich meinte er <conio.h> und getch() , die nicht Standard-C++ entsprechen. <cmath> darf man wohl noch durchgehen lassen, auch wenn es bereits in C vorhanden war.

Zudem ist es sehr unschön, Variablen an Orten zu deklarieren, an denen man sie nicht braucht. Also keine globalen Variablen. Und die Schleifen-Zählvariablen kannst du auch gleich lokal im Schleifenkopf deklarieren.

Dravere

Nexus schrieb:

betheman schrieb:

Was meinst du damit? Weil ich keine Klassen/Funtkionen beutze?

Wahrscheinlich meinte er <conio.h> und getch() , die nicht Standard-C++ entsprechen. <cmath> darf man wohl noch durchgehen lassen, auch wenn es bereits in C vorhanden war.

Zudem ist es sehr unschön, Variablen an Orten zu deklarieren, an denen man sie nicht braucht. Also keine globalen Variablen. Und die Schleifen-Zählvariablen kannst du auch gleich lokal im Schleifenkopf deklarieren.

Genau, danke fürs übernehmen

Grüssli

Nexus

Dravere schrieb:

Genau, danke fürs übernehmen

So langsam kenn ich dich...

pumuckl

hustbaer schrieb:

Fellhuhn schrieb:
b=2,c=sqrt(a); b<=c;
ist doch das gleiche wie:
b=2; b*b <= a;
Spart Zeit.
Das ist jetzt ein Scherz, oder?

Wieso, stimmt doch. Wurzelziehn dauert länger als Multiplikation mit sich selbst
Dass man auch gleich 4 <= a hätte schreiben können ist dann wieder n anderes Thema

pumuckl schrieb:

hustbaer schrieb:
Fellhuhn schrieb:
b=2,c=sqrt(a); b<=c;
ist doch das gleiche wie:
b=2; b*b <= a;
Spart Zeit.
Das ist jetzt ein Scherz, oder?
Wieso, stimmt doch. Wurzelziehn dauert länger als Multiplikation mit sich selbst
Dass man auch gleich 4 <= a hätte schreiben können ist dann wieder n anderes Thema

Im 'Original' wird die Wurzel nur einmal bei Initialisierung der Schleife berechnet. Abbruchbedingung ist in der Folge immer ein einfacher Vergleich. Bei Deinem Verbesserungsvorschlag wird bei jedem Schleifendurchlauf die Multiplikation durchgeführt, um die Abbruchbedingung zu testen.
Und "gleich 4 <= a" zu schreiben, ist auch keine gute Idee, weil b bei jedem Schleifendurchlauf inkrementiert wird, und eben nicht immer 2 ist.

Ich hab das mal folgendermaßen gemacht:
Ich merke mir die bereits ermittelten Primzahlen und dividiere die zu testenden Zahlen nur noch durch diese und nicht mehr durch alle Zahlen. Wenn mein Quotient kleiner als der Divisor wird, ist Schluß, damit spare ich mir die Wurzel. Allerdings muß ich zweimal dividieren, einmal für den Quotienten, einmal für den Rest ... vielleicht kann man das noch vereinfachen.

#include <vector>
#include <iostream>

typedef unsigned int uint;

int main()
{
	uint maxTest = 10000000;

	std::vector<uint> pZahl;

	pZahl.reserve(1000000);

	pZahl.push_back(2);
	pZahl.push_back(3);

	uint max_ind = 1;

	for(uint zTest = 5; zTest <= maxTest; ++zTest)
	{
		uint div = 0;
		uint rest;
		uint ind = 0;
		uint quot;

		do
		{
			rest = zTest % pZahl[ind];
			quot = zTest / pZahl[ind];
			++ind;
		}while(rest != 0 && pZahl[ind] < quot && ind <= max_ind);

		if(rest)
		{
			++max_ind;
			pZahl.push_back(zTest);
		}
	}
	/*
	for(int i = 0; i < pZahl.size(); ++i)
		std::cout << pZahl[i] << std::endl; */
	std::cout << pZahl.size() << std::endl;
}

Ich habe gerade mal den Code von Belli getestet.
In einem Bereich von 1 bis 900.000 brauche ich mit meinem Programm 0.625 sek, belli's prog braucht dafür 1.218 sek.

Ich habe meinen Code jetz mal folgendermaßen umgeschrieben:

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

int main()
{
    double c;                           // Variabeln
    unsigned int counter=1,b;           // in main
    bool isprim=false;                  // deklarieren

    for(unsigned int a=3; a!=1000000001 ; a+=2)
    {
        isprim=true;
        for(b=2,c=sqrt(a) ; b<=c ; ++b)
        {

            if(!(a%b))
            {
                isprim=false;
                break;
            }
        }
        if(isprim)
            ++counter;
    }

    cout<<counter;
    cin.get();          // cin.get() statt getch()
}

Der Grund, warum ich b und c nicht in der zweiten schleife deklariere ist, dass die ja dann bei jedem Aufruf der kleinen Schleife neu deklariert würde. Das bedeutet doch, dass nach dem verlassen der inneren Schleife die Variable zerstört wird und bei einem erneuten Aufruf wieder erstellt werden muss. Ist es nicht schneller, diese Variable daher außerhalb der inneren Schleife zu deklarieren, damit b nur initialisiert und nicht nochmal deklariert werden muss?

Und zu sqrt(): Im Prinzip reicht es ja, die Wurzel nur "bis zum Komma" zu errechnen, da ja eine int variable mit der Wurzel vergleichen wird. Es istalso völlig egal ob a mit 3 oder mit 3.162... verglichen wird. Kann man das nicht nutzten um eine eigene Funktion zu schreiben, die schneller ist als sqrt() ?

Dravere

#include <ctime>
#include <vector>
#include <iostream>

int main()
{
	std::clock_t start = std::clock();

	unsigned int counter = 1;
	unsigned int const maxLimit = 900000;
	std::vector<bool> primVec(maxLimit, true);

	for(std::vector<bool>::size_type i = 2; i < primVec.size(); ++i)
	{
		if(primVec[i])
		{
			++counter;

			for(std::vector<bool>::size_type r = i + i; r < primVec.size(); r += i)
			{ primVec[r] = false; }
		}
	}

	std::cout << (std::clock() - start) << "ms" << std::endl;
	std::cout << counter << std::endl;

	/*for(std::vector<bool>::size_type i = 1; i < primVec.size(); ++i)
	{
		if(primVec[i])
		{ std::cout << i << ", "; }
	}*/

	return 0;
}

Überseh ich etwas? Wenn nicht, dann läuft der Code durch mit weniger als 50ms

Grüssli

Habs grad nochmal probiert:
Dravere's Variante: 375 ms (Allerdings zeigt die Version eine Zahl zuviel an)
Meine Variante: 718 ms
Billi's Variante: 1234ms

wtwas Abgeänderte Version von Dravere: 128ms (siehe unten)

//kein .size() mehr bei JEDEM Schleifendurchlauf
#include <ctime>
#include <vector>
#include <iostream>

int main()
{
    std::clock_t start = std::clock();

    unsigned int counter = 1;
    unsigned int const maxLimit = 900000;
    std::vector<bool> primVec(maxLimit, true);

    for(std::vector<bool>::size_type i = 2, c = primVec.size() ; i<c ; ++i)
    {
        if(primVec[i])
        {
            ++counter;

            for(std::vector<bool>::size_type r = i + i, d = primVec.size() ; r<d; r += i)
            { primVec[r] = false; }
        }
    }

    std::cout << (std::clock() - start) << "ms" << std::endl;
    std::cout << counter << std::endl;

    return 0;
}

Theoretisch würde man doch noch mehr Performance gewinnen, wenn man nicht mit dem Indexoperator sondern mit Iteratoren auf den Vector zugreift. Allerdings weis ich nicht, wie man i+i und r+=i in der inneren Schleife schreiben soll, wenn i und r Iteratoren sind.

Ich habe nochmal geändert: zTest in der äußeren Schleife immer um 2 inkrementiert (Ich habe den Algorithmus vor Jahren in Cobol geschrieben, und jetzt auf die Schnelle nach C++ übersetzt, dabei habe ich das übersehen). Das bringt nicht soooo viel.
Was aber eine Beschleunigung um mehr als 50% gebracht hat, ist, statt eines Vectors mit seiner push_back - Methode ein genügend großes POD - Array zu nehmen. Ich habe hier gerade nur einen langsamen Rechner (1GHz Athlon), deshalb erspare ich mir mal die absoluten Zahlen.

Ich denke aber, das Sieb des Eratosthenes wird nicht zu schlagen sein ...

Ich habe weitere Zeit gespart, indem ich statt Division und Modulo die Standardfunktion div benutze, die Quotient und Rest liefert.
Auf diesem lahmen Rechner hier bin ich von 3.8 Sekunden in meiner Ursprungsversion auf nun 1 Sekunde gekommen.
So sieht das jetzt aus:

#include <iostream>
#include <ctime>

typedef unsigned int uint; 

int main() 
{ 
    uint maxTest = 1000000; 

	 uint pz[100000];

	 pz[0] = 2;
	 pz[1] = 3;

    uint max_ind = 1;
	 uint ind;
	 div_t res;

	 clock_t begin = clock();

	 for(uint zTest = 5; zTest <= maxTest; zTest += 2, ind = 0) 
    { 
        do 
        { 
				res = div((int)zTest, (int)pz[ind]);
            ++ind; 
        }while(res.rem != 0 && pz[ind] < res.quot && ind <= max_ind); 

        if(res.rem) 
        { 
            ++max_ind; 
				pz[max_ind] = zTest;
        } 
    } 

	clock_t ende = clock();
	double diff = static_cast<double>((ende - begin)) / CLOCKS_PER_SEC;
	std::cout << diff << std::endl;

   std::cout << max_ind + 1 << std::endl; 
}

Dravere

@betheman,
Sag mal, welcher Compiler benutzt du? Jedenfalls sicher nicht den den MSVC. Also nehme ich mal an, dass du den GCC verwendest. Hast du dort auch die Optimierungen angestellt? Oder ist der MSVC wirklich so viel besser?

Grüssli

ich benutze CodeBlocks v1.0 GNU GCC Compiler mingw32 (alle Einstellungen auf Standard, keine Ahnung ob ich da was optimieren kann, kenn mich nicht wirklich gut aus mit Compilern ^^)

Der neue Code von Belli läuft bei mir (bei Allen Zahlen bis 900000) läuft bei mir am schnellsten

Jetzt hast Du mich auf was gebracht. An Optimierungsschalter hab ich noch gar nicht gedacht. Aber die Angabe von -O, -O1, -O2 oder -O3 führt zu einem Programmabsturz zur Laufzeit. Das macht nun ein bißchen stutzig ...
Ich benutze übrigens den gcc.