C++: Größter Ganzzahl Datentyp?

[BenNavis]

Hi.

ich habe das Sieb des Eratosthenes in C++ geschrieben. Ich frage die obere Grenze ab bis zu der Primzahlen bestimmt werden soll und lege dann ein Array dieser Größe an auf dem ich dann weiterarbeite.
Leider kriege ich ab ca. 2.000.000 einen Speicherzugriffsfehler. Ich würde allerdings auch gern größere Primzahlen berechnen.
Ich hab schon long und auch int probiert, aber das ändert nichts. Sollte long nicht größer sein als int? Gibt es noch einen Datentyp, der noch größere Werte erlaubt?

Danke euch,
Ben

[peschmae]

Bei mir ist "int" und "long" beides 4 Byte - vermutlich bei dir auch wenn es bei 2 Millionen hakt. unsigned int hilft erstmal bis 4 mio.

Es gibt noch "long long" - der ist 8 Byte. Schlauerweise verwendest du dann auch gleich "unsigned long long" - damit kommst du noch etwas weiter - nämlich entsprechend bis 1.8*10^19 - aber da ist dann dein Arbeitsspeicher voll bevor du das alles ausgeschöpft hast (wenn du nichts sparst braucht ein Array mit all dem drin irgendwas *10^49 Gigabyte Speicherplatz :D).

MfG Peschmä

[BenNavis]

Es gibt noch "long long" - der ist 8 Byte. Schlauerweise verwendest du dann auch gleich "unsigned long long" - damit kommst du noch etwas weiter - nämlich entsprechend bis 1.8*10^19 - aber da ist dann dein Arbeitsspeicher voll bevor du das alles ausgeschöpft hast (wenn du nichts sparst braucht ein Array mit all dem drin irgendwas *10^49 Gigabyte Speicherplatz :D).
Ok, danke. Dann werde ich morgen mal long long probieren.
Wie kommst Du auf so viele GB? 8 Byte bedeutet doch 2^64 bit, oder?

Wenn int und long beides 4Byte werte sind, müsste es dann nicht bis 2Mrd gehen und nicht nur bis 2Mio?

[peschmae]

Stimmt, da hatte ich ein Kilo-Faktor zuwenig :D

2^64 Bit = 1.8e19 Mögliche Zahlen, 4 Byte pro Zahl - 7.3e19 Byte Speicher. 1000^3 - ok, ist etwas weniger ;)

MfG Peschmä

[nobody0]

ANSI/ISO-C kennt integer-Datentypen bis 64 bit, also int64_t, uint64_t usw..
Es gibt auch größere wie uint128_t, die aber nicht jeder ANSI-Compiler kennen muß, d. h. die sind allgemein nicht portabel.

[BenNavis]

Leider macht es keinen Unterschied, ob ich nun long oder long long nehme, bei 2mios ist Schluß.
Muss man noch was am namespace ändern, oder was spezielles includen?

Hier mal der gekürzte Code, ab eingabe > ~2.500.000 ist Schluß.

#include <iostream>
using namespace std;

int main() {
long long eingabe;
long long i;

cout << "Geben Sie eine obere Grenze an: ";
cin >> eingabe;
long long array[eingabe];

for(i=0; i<eingabe; i++) {
array[i]=i;
}

for(i=0; i<eingabe; i++) {
if(array[i] != 0) {
cout << i << " ";
}
}

cout << "\n";
return 0;
}

[RHBaum]

Ich bezweifel, das er das kompiliert !

long long array[eingabe];

eingabe iss ne variable, aber nen statisches array aufn stack zu legen geht nur mit ner constante (die zur compilezeit bekannt ist)
Wie hasst du hier getrickst ?

die stl-streams kennen normal keine 64 bit int typen, deshalb wirst da auch nicht viel glueck mit deinem eingabeschema haben ....

lass dir deine Zahl als string geben und parse sie selber !

fuer dynamische arrays nimm nen vector !

CIao ...

[BenNavis]

Ich bezweifel, das er das kompiliert !

long long array[eingabe];

eingabe iss ne variable, aber nen statisches array aufn stack zu legen geht nur mit ner constante (die zur compilezeit bekannt ist)
Wie hasst du hier getrickst ?

die stl-streams kennen normal keine 64 bit int typen, deshalb wirst da auch nicht viel glueck mit deinem eingabeschema haben ....

lass dir deine Zahl als string geben und parse sie selber !

fuer dynamische arrays nimm nen vector !

CIao ...
"Er" kompiliert das ohne zu Murren.

Was sind stl-streams?

Was meinst Du mit "lass dir deine Zahl als string geben und parse sie selber"? Soll ich eingabe als String speichern und dann in long long casten?

Ich gucke mir mal vector an, danke.

[RHBaum]

#include <iostream>
#include <vector>

// using namespace std; // auch wenn es in vielen buechern steht, und Dir andere alles anders erzaehlen tus nich !

int main() {
unsigned long eingabe;
std::cout << "Geben Sie eine obere Grenze an: ";
std::cin >> eingabe;
std::vector<unsigned long> MyArray(eingabe);
for(unsigned long i=0; i <eingabe; i++)
{
myArray[i]=i;
}

for(std::vector<unsigned long>::const_iterator it = MyArray.begin();it != MyArray.end(); ++it )
{
if(*it)
{
cout << *it << " ";
}
}

cout << "\n";
return 0;
}

Nich getestet, irgendwo iss sichern nen fehler, soll aber nurs prinzip zeigen ....
soo sollte er bis 4 Milliarden und paar zerquetschte zaehlen ...

Ciao ...

[RHBaum]

"Er" kompiliert das ohne zu Murren.
Wer ist er ? :-) Welcher Compiler, welche Version .. meiner murrt heftig (VC 6.0, Schande ueber mich )


Was sind stl-streams?
Streams ist ein konzept. SOllen sowas wie generische Datenstroeme darstellen. Sprich du pulverst irgendwas in so nen schwarzes Loch, und irgendwo am anderen ende kommt das zeug in der selben reihenfolge wieder raus :-) Das ende koennen die console (std::cout, std::cin) ne datei (fstream) nen Stream der auf nen Netzwerk verbindung festgenagelt wurde (Transport streams unter posix, kenn namen nich mehr so genau ) ... sein.

Fuer dich als programmerier iss das easy, weil du beim zugriff nimmer unterscheiden musst, aus was du da draufrumschreibst .... oder ausliest.

In Wahrheit isses bisserl komplizierter, aber zur veranschaulichung sei es mir verzeihen, hoffentlich ...

Die STL implementiert grundlegende streams fuer dich ... also konsole, und dateien (iostream, fstream etc ... )
Fuer diese Streams sind diverse operatoren ueberladen hauptsaechlichst << und >> so das daten in den Stream einfach mit mystream << myData reinbekommst. diese operatoren sind fuer die gaengigsten datentypen schon fertig vorhanden .... nur eben fuer die 64 bittigen nicht ....



Was meinst Du mit "lass dir deine Zahl als string geben und parse sie selber"? Soll ich eingabe als String speichern und dann in long long casten?
da wie oben erklaert
long long iValue;
std::cin >> iValue funzt eben nich .... (weiss nich obs ne impl gibt die es kann ? )
deshalb :
std::string strValue;
std::cin >> strValue;

und nu strvalue in nen long long umwandeln ... viel spass :-)
btw nen einfacher cast hilft dir hier gar nich ...

und nur, wenn du mit 4,4 milliarden nich hinkommen solltest .....

Ciao ...

[bischi]

Leider kriege ich ab ca. 2.000.000 einen Speicherzugriffsfehler.

Tönt ganz danach, als ob dein Arbeitsspeicher geflutet ist...

Wie hast dus programmiert: Iterativ oder Rekursiv?

Int geht bis ca. 32000 (2 Bit) oder bis ca 2 Milliarden (4 Bit) (oder 8.4 Mio bei 3 Bit).

Dies kannst du nachrechnen (minus codierung für Spezialzeichen) mit folgender Formel: (2^(byte *8))/2

MfG Bischi

PS: Schau mal mit Tastmng oder co nach, wieviel Arbeitsspeicher noch frei ist...

[BenNavis]

OK, das mit den Streams hab ich jetzt so einigermaßen verstanden... ;)


Tönt ganz danach, als ob dein Arbeitsspeicher geflutet ist...


total used free shared buffers cached
Mem: 514064 503472 10592 0 20272 268832
-/+ buffers/cache: 214368 299696
Swap: 1044216 102732 941484

~$ ./sieb
Speicherzugriffsfehler

total used free shared buffers cached
Mem: 514064 503488 10576 0 20312 268848
-/+ buffers/cache: 214328 299736
Swap: 1044216 102732 941484
Der Speicherzugriffsfehler kommt auch sofort (zumindest für mein Wahrnehmungsvermögen) nach der Ausführung. Es macht nicht den Anschein, ob gerechnet und gerechnet wird und irgendwann kein Speicher mehr frei ist.


Wie hast dus programmiert: Iterativ oder Rekursiv?
Der Code steht oben


Int geht bis ca. 32000 (2 Bit) oder bis ca 2 Milliarden (4 Bit) (oder 8.4 Mio bei 3 Bit).
Dies kannst du nachrechnen (minus codierung für Spezialzeichen) mit folgender Formel: (2^(byte *8))/2
Ist schon klar. Um so mehr wundert mich wieso immer bei 2mios Schluß ist.

Ach ja:

~$ g++ -v
gcc-Version 3.3.5 (Debian 1:3.3.5-12)

[bischi]

OK, das mit den Streams hab ich jetzt so einigermaßen verstanden... ;)



total used free shared buffers cached
Mem: 514064 503472 10592 0 20272 268832
-/+ buffers/cache: 214368 299696
Swap: 1044216 102732 941484

~$ ./sieb
Speicherzugriffsfehler

total used free shared buffers cached
Mem: 514064 503488 10576 0 20312 268848
-/+ buffers/cache: 214328 299736
Swap: 1044216 102732 941484
Der Speicherzugriffsfehler kommt auch sofort (zumindest für mein Wahrnehmungsvermögen) nach der Ausführung. Es macht nicht den Anschein, ob gerechnet und gerechnet wird und irgendwann kein Speicher mehr frei ist.


Naja - nachher hast du auf jeden fall mehr arbeitsspeicher frei - mein Traumprogramm!



Der Code steht oben


Das ist aber nicht das Sieb des Erathostenes - oder hab ich da was falsch verstanden?

Das geht so: Boolean-Array nehmen, maximale Grösse angeben; Danach ganzes Array auf true setzen und mit 2 beginnen. Alle vielfachen von zwei auf false setzen, weiter mit drei, ... Warum du da ein Long-Array nimmst, ist mir ein Rätsel...

MfG Bischi

[BenNavis]

Das ist aber nicht das Sieb des Erathostenes - oder hab ich da was falsch verstanden?
Nee, stimmt, ist es nicht. Ich hab nur den Teil gepostet, der mit dem Anlegen und Ausgeben des Arrays zu tun hat, denn da tritt das Problem auch schon auf


Das geht so: Boolean-Array nehmen, maximale Grösse angeben; Danach ganzes Array auf true setzen und mit 2 beginnen. Alle vielfachen von zwei auf false setzen, weiter mit drei, ... Warum du da ein Long-Array nimmst, ist mir ein Rätsel...
Ok, das geht auch.
Ich habe ein long-Array genommen, weil ich dann am Ende des Durchlaufs durch das Array und nach dem Streichen aller Vielfachen der Primzahlen ein Array habe, in dem alle Zahlen != 0 Primzahlen sind.
Das hielt ich für eine schöne Methode.

Hier mal der ganze Code:


#include <iostream>
using namespace std;

int main() {
long long eingabe;
long long i;
long long anzahl = 0;

cout << "Geben Sie eine obere Grenze an: ";
cin >> eingabe;
eingabe++;
long long array[eingabe];

for(i=0; i<eingabe; i++) {
array[i]=i;
}

array[1]=0;

for(i=2; i<eingabe; i++) {
if(array[i] != 0) {
anzahl++;
for(long j=2; i*j<=eingabe; j++) {
array[i*j]=0;
}
}
}

cout << anzahl << " Primzahlen gefunden, naemlich:" << "\n";

for(i=2; i<eingabe; i++) {
if(array[i] != 0) {
cout << i << " ";
}
}

cout << "\n";
return 0;
}

[bischi]

Ok, das geht auch.
Ich habe ein long-Array genommen, weil ich dann am Ende des Durchlaufs durch das Array und nach dem Streichen aller Vielfachen der Primzahlen ein Array habe, in dem alle Zahlen != 0 Primzahlen sind.
Das hielt ich für eine schöne Methode.


Schöner vielleicht schon - aber grauenhaft Speicherverschwenderisch... Wenn du schon grosse Zahlen haben willst, da kannst du da locker den Faktor 30 oder mehr an Speicherplatz sparen...

MfG Bischi

[BenNavis]

Schöner vielleicht schon - aber grauenhaft Speicherverschwenderisch... Wenn du schon grosse Zahlen haben willst, da kannst du da locker den Faktor 30 oder mehr an Speicherplatz sparen...
Stimmt, daran hab ich gar nicht gedacht.
Ich hab mich halt möglichst eng an den Wortlaut des Algorithmus gehalten.
Ich probiere es mal mit boolean.
Ihr meint also ich soll lieber einen vector nehmen, weil bei einem Array die Größe zur Kompilierzeit feststehen muss? Wieso schluckt der gcc das dann?

Call me stupid, aber ich hab immer noch nicht verstanden, wieso long und long long keinen Unterschied machen bzw. beide einen Speicherzugriffsfehler erzeugen. :confused: ;)