[C++] Priemzahlenoptimierung

Hallo!

Ich habe zu Übungszwecken das bekannte Priemzahlen-errechen-Programm geschrieben [Ich bin Anfänger:D]. Es funktioniert einwandfrei, allerdings ist mir ein Problem aufgefallen:

Der Arbeitsspeicher ist mit 600 kb für das Programm nicht sonderlich überlastet, aber wenn man beispielsweise alle Priemzahlen zwischen 1 und 10.000.000 errechnen möchte, dauert es bei mir ~10 Stunden.
(Code ist schon in meine Idee geändert, daher 10.000.000 zZt. nicht errechenbar :D)

Ich hatte als Lösungsidee mir vorgestellt, dass man einhundertK und zweihundertK gleichzeitig per && ablaufen lässt, jedoch schreit bei mir da der Compiler los!

Würde mich über etwas Hilfe freuen!

Source:

#include <iostream>
using namespace std;

int gesamt=0;
int MaxPriemzahl;
int Priemzahl, Divisor;
bool istEinePriemzahl;

void einhundertK()
{
if(MaxPriemzahl< 100000)
{
for(Priemzahl=3; Priemzahl<=MaxPriemzahl; Priemzahl++)
{
istEinePriemzahl=true;
cout << "Fortschritt: " << Priemzahl<< " ueberprueft" << endl;
for(Divisor=2; istEinePriemzahl && Divisor<Priemzahl; Divisor++)
{
if(0==Priemzahl% Divisor)
{
istEinePriemzahl=false;
}
}

if(istEinePriemzahl)
{
gesamt++;
}
}
}
}


void zweihundertK()
{
if(MaxPriemzahl<200000)
{
for(Priemzahl=100000; Priemzahl<=MaxPriemzahl; Priemzahl++)
{
istEinePriemzahl=true;
cout << "Fortschritt: " << Priemzahl<< " ueberprueft" << endl;
for(Divisor=2; istEinePriemzahl && Divisor<Priemzahl; Divisor++)
{
if(0==Priemzahl% Divisor)
{
istEinePriemzahl=false;
}
}

if(istEinePriemzahl)
{
gesamt++;
}
}
}
}

void platzhalter()
{
cout << endl;
cout << endl;
cout << endl;
cout << endl;
cout << endl;
cout << endl;
cout << endl;
}

int main()
{

cout << "PRIEMZAHLENRECHNER" << endl;
cout << endl;
cout << "Dieser Rechner kann ihnen alle Priemzahlen zwischen 1 und ihrer Wahl ausrechnen" << endl;
cout << "Ihre Wahl: " << endl;
cin >> MaxPriemzahl;

platzhalter();

einhundertK();
zweihundertK();


cout << endl;
cout << endl;
cout << "ABGESCHLOSSEN!!!" << endl;
cout << endl;
cout << endl;
cout << "+++++++++++++++++++++++++++++++++++++++++++++++++ ++++++" << endl;
cout << "-------------------------------------------------------" << endl;
cout << "---vorhandene Priemzahlen zwischen 1 und " << MaxPriemzahl << ":" << endl;
cout << "-------------- " << gesamt << " -------------------"<< endl;
cout << "-------------------------------------------------------" << endl;
cout << "+++++++++++++++++++++++++++++++++++++++++++++++++ ++++++" << endl;
cin.get();
}

Multi-Threading würde dir sicher helfen den Vorgang zu optimieren ;)

~Zer0Flag

Hi.

Eine "parallele" Ausführung wird dir nichts an Performance bringen.

Du solltest lieber einen besseren Algorithmus verwenden, z.B. folgenden:
Sieb des Eratosthenes – Wikipedia
(Ich weiß gerade gar nicht was es da sonst noch gibt. Falls Bedarf besteht kann ich nochmal in den Aufschrieben schauen, ob ich noch was habe. Ansonsten einfach mal googlen.)
Auf der Wikipedia-Seite findest du auch eine Implementierung als Pseudocode.

~noctem

Es heißt "Primzahl"!!!

Weitere regeln:

mind. 1 Primzahl zw. ihr und dem doppelten von ihr,
d.h. zw. 5 und 10 ist 7, zw. 6 und 12 ist 11

mind. 1 Primzahl zw. der Primz. zum Quadrat und der Primz.+1 zum Quadrat
z.B.: 2^2 = 4 und 3^2 = 9 --> zw. 4 und 9 ist 5 und 7

die hab ich aus irgentsoeinem buch :D

wenn dich sowas interessiert kannst du ja mal nach Riemannsche Zeta-Funktion googlen

Du hast zudem vergessen einen Wert in der main-Funktion zurückzugeben.
Desweiteren wird Multithreading keinen Performanceboost bringen, da die Leistungsfähigkeit von dem Prozessor und dem Algorithmus beeinflusst wird, nicht aber durch die Anzahl der Threads. Btw: Threads laufen nur scheinbar gleichzeitig und nicht tatsächlich.

Abgesehen von erwähnten besseren Algos könnte man auch an diesem noch etwas feilen:
1) es reicht vollkommen aus, den "divisor" bis zur Wurzel(Primzahl_kandidat) laufen zu lassen ;)
2) statt den Divisor immer um 1 zu erhöhen (und damit jedes zweite mal den "Teilbar durch 2 oder ein vielfaches davon" Test zu machen, sollte der Divisor > 2 dann gleich in 2-er Schritten erhöht werden - also [3, 5, 7, 9] usw.
3) eigentlich braucht man nur zu testen, ob eine Zahl durch eine Primzahl < dieser Zahl teilbar ist. Denn alle anderen
Zahlen sind ja eher nur aus Primzahlen zusammengetzt
4) wenn eher die größte Zahl errechnet werden soll, macht es doch keinen Sinn, mit der kleinsten zu beginnen ;)

Habs mal schnell die Punkte 1 bis 3 in Python umgesetzt (Suche nach der größten Primzahl bis X, wobei man stur von klein nach groß geht):

Code:

---

# coding=utf-8
# Wikipedia sagt: Jede positive ganze Zahl größer 1 lässt sich bis auf die
# Reihenfolge eindeutig als Produkt von Primzahlen darstellen.
# d.h wenn eine Zahl durch keine kleineren Primzahlen teilbar ist, ist sie auch Prim ;)
import math, os

prim_numbers = [2]

def is_prim(candidate):
    max_test = int(math.sqrt(candidate) + 1)
   
    for number in prim_numbers:
      if candidate % number == 0:
          return False
      elif number > max_test:
          return True
     
    return True

def prim_finder(max_num):
    for candidate in xrange(3, max_num, 2):
        if is_prim(candidate):
            prim_numbers.append(candidate)

    return prim_numbers[-1]

def main():
    try:
        print prim_finder(int(sys.argv[1])) 
        print "Primzahlen von 2 bis zur diesen:", len(prim_numbers)-1   
    except:
        print "Usage: python primmax.py [max_number]"
   
main()

---

braucht bis 1 Mio 3 Sekunden und bis 10 Mio 61 Sekunden (wobei der Rechner schon älter ist ;) )
und die "ultimative" Version ("Optimierungen" 1) 2) und 4) ), die die Test mit der größten Zahl beginnt und dann runterzählt:

Code:

---

import math

def is_prim(candidate):
    max_test = int(math.sqrt(candidate) + 1)
    # teste "Teilbar durch 2" extra:
    if candidate % 2 == 0:
        return False
   
    for num in xrange(3, max_test, 2):
      if candidate % num == 0:
          return False
     
    return True

def prim_finder(max_num):
    # wenn Zahl gerade, macht das testen keinen Sinn:
    if max_num % 2 == 0:
        max_num = max_num - 1

    for candidate in xrange(max_num, 1, -2):
        if is_prim(candidate):
            return candidate

def main():
    try:
        print prim_finder(int(sys.argv[1]))       
    except:
        print "Usage: python primmax.py [max_number]"
   
main()

---

(Zeit für 1 Mrd: 0.02s == nicht messbar ;) )

Oh da kommen Errinnerungen auf... Ich hatte auch mal einen Primzahlenrechner in C++ programmiert. Natürlich mit dem Sieb des Eratosthenes, und daran ein paar Optimierungen vorgenommen. Mit meinem C++ Programm kann man wenn man es auf einem 64 Bit Computer compiliert und ausführt und 4GB Ram oder mehr hat problemlos alle Primzahlen bis 50 Mrd. ausrechnen und das in ca. 1 Stunde (je nach Hardware).
Der Trick den ich angewendet habe um Speicher zu sparen ist, dass ich für alle Zahlen nur 1 Bit verwende (ist es eine Primzahl oder nicht) und, dass ich die geraden Zahlen von Anfang an ignoriere.
Hier mal mein Programm (Achtung, sehr komplex und nicht kommentiert):

Code:

---

#include <iostream>
#include <fstream>
#include <Windows.h>
#include <time.h>

using namespace std;

unsigned long long int i;
unsigned long long int m;
unsigned long long int count;
unsigned long long int count2;
unsigned long long int maxz;
unsigned char *prim;

DWORD WINAPI thread1(LPVOID data)
{
    for(unsigned long long int k=0; i<count; k++){
                i=k;
                if((prim[k>>3])&(0x1<<(k%8))){
                        unsigned long long int z = k*2+3;
                        for(unsigned long long int j = k+z; j<count; j+=z){
                                prim[j>>3] &= ~(unsigned char)(0x1<<(j%8));
                        }
                }
        }
        return 0;
}

DWORD WINAPI thread2(LPVOID data)
{
        char * filename = (char *) data;
        unsigned long long int buffer[512];
        unsigned int pos = 0;
        FILE * f;
       
        f = fopen(filename, "wb");
       
        buffer[pos++] = 2;

        for(m=0; m<count; m++){
                while(m>=i){
                        Sleep(10);
                }
               
                if(prim[m>>3]&(0x1<<(m%8))){
                        unsigned long long int z = m*2+3;
                        buffer[pos++] = z;
                }
                if(pos >= (sizeof(buffer)/sizeof(buffer[0]))){
                        fwrite(&buffer[0],sizeof(buffer[0]),pos,f);
                        fflush(f);       
                        pos = 0;
                }
        }

        if(pos != 0){
                fwrite(buffer,sizeof(buffer[0]),pos,f);
        }

        fclose(f);
        return 0;
}

int main(int argc, char **argv){
        HANDLE t1hwnd;
        DWORD t1id;
        HANDLE t2hwnd;
        DWORD t2id;
        clock_t start;
        clock_t end;
        float perccalc;
        float percwrite;

    start = clock() * CLK_TCK;

        cout<<"Primzahlen Rechner"<<endl;

        if(argc < 3){
                cout<<"Verwendung: "<<argv[0]<<" out.dat 10000"<<endl;
                return 1;
        }

        cout<<"Initialisiere Variablen.."<<endl;
       
        maxz = _atoi64(argv[2]);
        count = maxz/2-1;
        count2 = count/8+1;
        i=0;

        prim = new unsigned char[count2];

       

        for(unsigned long long int j = 0; j<count2; j++){
                prim[j] = 0xff;
        }

        cout<<"Starte Thread 1..."<<endl;
        t1hwnd = CreateThread( NULL, 0, thread1, NULL, 0, &t1id );

        cout<<"Starte Thread 2...\nSchreibe Ergebnis in die Datei "<<argv[1]<<"..."<<endl;
        t2hwnd = CreateThread( NULL, 0, thread2, argv[1], 0, &t2id );

        while((i<count) || (m<count)){
                Sleep(2500);
                perccalc = (float)i/count;
                perccalc =sqrt(perccalc)*100;

                percwrite = (float)i/count;
                percwrite = percwrite*100;

                cout<<"Fortschritt: "<<(float)((int)(((float)(perccalc + percwrite)/(float)(2)*100)))/100<<"%; Berechnung: "<<(float)((int)((perccalc*100)))/100<<"%; Schreiben: "<<(float)((int)((percwrite*100)))/100<<"%"<<endl;
        }

        end = clock() * CLK_TCK;
       
        delete prim;

        cout<<"Vergangene Zeit: "<<((double)((unsigned long long int)((double)(end-start)/100000))/10)<<" Sekunden"<<endl;
        cout<<"Fertig!"<<endl;

        return 0;
}

---

Zitat:

---

Zitat von The-God-of-all

dass ich die geraden Zahlen von Anfang an ignoriere.

---

Das bedeutet du lässt die Primzahl 2 einfach weg, oder schreibst sie manuell dazu...

Eine Ausgabe (cout o.ä.) dimmt auch die Geschwindigkeit.
Am besten erst berechnen, und am Ende ausgeben/loggen.

Ansonsten sind hier alle, soweit mir bekannten, Optimierungen schon genannt worden, mit dem wissen solltest du das wohl hinbekommen.

Zitat:

---

Zitat von TRX

Das bedeutet du lässt die Primzahl 2 einfach weg, oder schreibst sie manuell dazu...

---

Ich schreibe sie Manuell dazu. Das ist nur eine Zahl die hinzugefügt werden muss und dafür wird der Speicherbedarf halbiert und die Rechenzeit merklich verkürzt.

Das die Ausgabe mit cout sehr Zeitraubend ist ist mir auch aufgefallen, ich gebe die Zahlen daher in einem extra Thread aus, und nicht mit cout sondern mit fprint immer in 4096 Byte Blöcken in eine Datei (im Idealfall Clustergröße der Festplatte --> höchstmögliche Geschwindigkeit). Allerdings gibt mein gepostetes Programm die Zahlen Binär, also immer 4 Byte lang aus. Das spart nicht nur Rechenzeit sondern auch Speicherplatz.

Hier mal ein Vergleich zwischen meiner jetzigen Ausgabe und der Ausgabe mit cout bzw. einem fstream: Die Speicherrate vorher waren ein paar MB/s (ca. 4-5 MB/s), jetzt ist es wirklich die maximale Schreibgeschwindigkeit meiner Festplatte (ca. 80MB/s). Da ist also auch noch viel Spielraum zum optimieren des Algorithmus.

Noch ein Tipp: Wenn du doch cout nimmst dann benutze nicht immer std::endl als Zeilenumbruch weil das zu einem flush führt, also den Buffer leert. Es ist manchmal sinnvoll nur \n als Zeilenumbruch anzufügen weil die Daten dann in den Buffer geschrieben werden. Das geht wesentlich schneller als immer jede Zeile einzeln auszugeben.