[Bockfett]

Moin,

Ich hab auf Grundlage einer leicht optimierten Version des Siebes Eratosthenes ein Programm zum berechnen der ersten n Primzahlen geschrieben. Naturgemäß geht das mit int nur bis 2^31. Also habe ich int einfach durch long long ersetzt, aber jetzt stürzt das Programm einfach ab... Was könnte der Fehler sein?

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

using namespace std;

int main(){
    
    long long prim, i, n, m, Anzahl=0, p=1;
    clock_t start, end1, end2;
    
	cin>>prim;
    start = clock();
	vector <bool> sieb(prim, 1);
	
	while((p*p) <= sieb.size()){
	            for(i = 1; sieb[p+i] != 1; ++i){
                if( (p + i) <= sieb.size())
                break;}
                 
                 p = p + i;
                 
                 for(n = p; n*p <= prim; n++){
	             sieb[n*p] = 0;}   
                 }
end1 = clock();
     for(m = 2; m <= sieb.size(); m++){
         if(sieb[m]){
         //cout<<m<<endl;
         Anzahl = Anzahl + sieb[m];}}
         end2 = clock();
         cout<<Anzahl<<" Primzahlen "<<end1-start<<"ms "<<end2-end1<<"ms"<<endl;
cin.get();
cin.get();}

Dieser Beitrag wurde von Bockfett bearbeitet: 02. Juli 2012 - 15:01

[Witi]

Da meine Glaskugel leider nicht anzeigt, mit welchem Fehler dein Programm abstürzt, rate ich einfach mal und tippe dass es an "cin >> prim" liegt. Soweit ich weiß, existiert kein überladener Operator für long long. Stattdessen könntest du was machen (hier mit __int64):

std::stringstream sstr(mystr);
__int64 val;
sstr >> val;

Edit:
Ein normaler Cast soll angeblich auch funktionieren:

std::stringstream ss; long long ll = (long long)&ss; 

Dieser Beitrag wurde von Witi bearbeitet: 02. Juli 2012 - 22:23

[Bockfett]

Habs mal ein bisschen geändert, funktioniert aber auch nicht besser.
Der Witz ist, dass kleine Zahlen für prim funktionieren, aber schon 4e9 kackt er gnadenlos ab mit der nichts sagenden Windowsfehlermeldung "Das Programm funktioniert nicht mehr"
Kompiler ist übrigens DEV C++, alle Optimierung sind ausgeschaltet.

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

using namespace std;

int main(){
    
    long long prim, i, n, m, Anzahl=0, p=1;
    clock_t start, end1, end2;
    
	//cin>>prim;
	prim = 4000000000ULL;
    start = clock();
	vector <bool> sieb(prim, 1);
	
	while((p*p) <= sieb.size()){
	            for(i = 1; sieb[p+i] != 1; ++i){
                if( (p + i) <= sieb.size())
                break;}
                 
                 p = p + i;
                 
                 for(n = p; n*p <= prim; n++){
	             sieb[n*p] = 0;}   
                 }
end1 = clock();
     for(m = 2; m <= sieb.size(); m++){
         if(sieb[m]){
         //cout<<m<<endl;
         Anzahl = Anzahl + sieb[m];}}
         end2 = clock();
         cout<<Anzahl<<" Primzahlen "<<end1-start<<"ms "<<end2-end1<<"ms"<<endl;
cin.get();
cin.get();}

[__42__]

Der Witz an der Sache ist, dass man auf endlichem Speicher arbeitet und es wohl deshalb bei "kleinen" Zahlen funktioniert.

[Bockfett]

Das was Speicher benötigt ist der Vector. Das Programm kackt ja schon bei 4 Milliarden ab, was gerade mal 500 MB Arbeitsspeicher braucht.
Aber vielleicht ist das dennoch das Problem, dass der Compiler nur begrenzt RAM reservieren kann?!

[der dom]

Ich kenn mich mit C++ leider nicht aus aber hast du nicht die Möglichkeit die Reservierung zu erhöhen? Oder sollte das Programm nicht ohnehin den Speicher selbst reservieren, unabhängig vom Compiler?

Wenn es sowas wie try catch bei c++ gibt oder eine Möglichkeit die Fehler abzufangen, dann mach das doch mal und lass dir den Fehler der Verursacht wird, entsprechend ausgeben. Vielleicht erkennst du dann etwas besser wo es hängt. Was sagt denn der Stacktrace?

[Witi]

Ich musste deinen Quellcode jetzt doch mal bei mir ausprobieren...und es funktioniert ohne Probleme. Kompiliert mit:

g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=c:/users/witi/mingw/bin/../libexec/gcc/mingw32/4.7.0/lto-wra
pper.exe
Target: mingw32
Configured with: ../gcc-4.7.0/configure --enable-languages=c,c++,ada,fortran,objc,obj-c++ --disable-sjlj-exceptions --with-dwarf2 --enable-shared --enable-libgomp --disable-win32-registry --enable-libstdcxx-debug --disable-build-poststage1-with-cxx --enable-version-specific-runtime-libs --build=mingw32 --prefix=/mingw
Thread model: win32
gcc version 4.7.0 (GCC)

Und da ist mir bei dir etwas aufgefallen:

Zitat

Kompiler ist übrigens DEV C++, alle Optimierung sind ausgeschaltet.

Dev-C++ ist erstens kein Compiler, sondern eine IDE (kompiliert aber auch mit dem gcc) und zweitens wird das zwei etwa sieben Jahren nicht mehr weiterentwickelt!

Falls du weiter mit dem gcc arbeiten möchtest, probiere es mal mit MinGW oder falls du weiter mit einer "Klicki-Bunti"-IDE arbeiten möchtest, Code::Blocks.Schau also mal ob du es mit etwas aktuellerem zum Laufen bekommst.

[Kirill]

Nicht einen Compiler nehmen, sondern eine gescheite IDE. Dann das Programm im Debugger ausführen und schon weiss man, wo genau er abstürzt.
Wenn man sich für IDE+Debugger zu stolz ist (klingt sinnlos provokant, aber mir fällt echt kein Grund ein, nicht diese Schiene zu fahren, ausser unter DOS), tun's auch Debugmeldungen, die man immer wieder auf die Konsole ausgibt. An jeden relevanten Programmschritt eine Ausgabe des abzuarbeitenden Befehls samt Parametern dranhängen und schauen, was die letzte Ausgabe vor dem Crash ist.

Das mal an generischen Tipps, ohne auf das konkrete Problem einzugehen. Die erste Methode nehme ich für Windowsentwicklung, die zweite für DOS.

Dieser Beitrag wurde von Kirill bearbeitet: 03. Juli 2012 - 22:52

[Bockfett]

Hab das ganze jetzt noch mal mit Code::Blocks ausprobiert. Nun schafft er zwar immerhin klaglos das Berechnen bis 4*10^9, aber bei 8*10^9 bricht er nach einer knappen Minute mit folgender Fehlermeldung ab.

Process returned -1073741819 <0xC0000005>

Was zusätzlich auffällt ist, dass der Prozess "nur" ~500 MB Arbeitsspeicher in Anspruch nimmt. Zu erwarten wären doch aber 1000 MB.