Sieb des Eratosthenes; Heap reicht nicht aus ^^

[Technipion]

Hey Leute,
ich habe folgendes Problem:
Mein Programm nutzt einen Algorithmus (Sieb des Eratosthenes) um Primzahlen zu finden. Ich übergebe per Konsole das obere Limit und es filtert alle Primzahlen bis dahin raus. Hierfür benutze ich ein Array aus <unsigned long long>. Sizeof() verrät, dass sie auf meinem System 8 Byte brauchen. Hier mein Code:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if(argc < 2)
    {
        printf("Limit angeben!\n");
        return 0;
    }
    unsigned long long LIMIT = atoll(argv[1]);
    unsigned long long int i, j;
    unsigned long long *primes;
    try {
        primes = new unsigned long long[LIMIT];
    }
    catch (std::bad_alloc& ba){
        std::cerr << "bad_alloc aufgetreten: " << ba.what() << '\n';
    }
    for (i=2;i<LIMIT;i++)
        primes[i]=1;
    for (i=2;i<LIMIT;i++)
        if (primes[i])
            for (j=i;i*j<LIMIT;j++)
                primes[i*j]=0;
                    for (i=2;i<LIMIT;i++)
                        if (primes[i])
                            printf("%llu\n",i);
    return 0;
}

Mein Problem ist jetzt: Für eher "kleine" Limits wie 200.000.000 funktioniert alles prima! Dauert nur wenige Sekunden und liefert korrekte Ergebnisse. Für größere Limits kommt der Error: bad_alloc.
Ich weiß einfach nicht woran's liegt. Ich allokiere dynamisch und der Computer hat mehr als genug RAM!
Bei 210.000.000 als Limit ist Schluss. Ich compiliere es als 32-bit Programm, liegt's vielleicht daran? Sind die Pointer einfach zu klein? Oder gibt Windows 7 nicht mehr her?
Hilfe, wie kriege ich meine 4-6 GB?

Danke schonmal im Voraus
Gruß Technipion

 

[sheel]

Hi

ca. 1.6GB...

Problem 1: Wie du schon vermutest: 32bit

Problem 2 zusätzlich: So ein Array will den gesamten Speicher in einem Stück.
Es könnte sein, dass der derzeitige verbrauchte Speicher so "verteilt" ist,
dass nirgends dazwischen ein 1.6GB-Loch ohne Unterbrechungen ist.



Andere Algorithmen gehen vllt. nicht ganz so schnell, brauchen aber viel weniger Speicher.

zB. für jede Zahl, beginnend bei 1, versuchen, ob sie sich mit einer der bisher gefundenen Primzahlen teilen lasst (ohne Rest).
Wenn ja: Zu den gefundenen Primzahlen dazu
Und weiter zur nächsten Zahl.

Was nötig ist ist ein Array mit Platz für Primzahlen, nicht für alle Zahlen
(und ein int, wie voll das Array schon ist).

Es gibt rund x/ln(x) Primzahlen zw. 1 und x
Ist für 210Mio nur ca. 10Mio.
Und wenn man zB. 20 + 1.2x/ln(x) nimmt ist man auf der sicheren Seite vor Arrayüberlaufen
(weil nur ungefähr) (grad keine Ahnung, wo ich die Zahlen hernehme)
Wäre dann eben ca. 12Mio



Weiterer Punkt: Für Werte wie 210Mio. brauchts kein 8Byte-int. 4 reicht.
Mit (unsigned) 4Byte kommt man bis zu 4 Milliarden (4 294 967 295)
Damit kann man den Speicherverbrauch wieder halbieren.

Und diese 12Mio Zahlen mussen (wegen der Sache mit dem zusammenhängenden Speicher)
auch nicht alle in ein Array. In mehrere Arrays etc. aufsplitten verkompliziert die Programmierung zwar, macht die Allokation aber erfolgreicher.

 

[Technipion]

Hey super!
Hab das Array jetzt als <unsigned long> deklariert. Dadurch waren dann natürlich gleich mal Zahlen bis 400.000.000 möglich. Dann habe ich das Programm auf 64-bit umcompiliert und es lief mit 1.500.000.000 als Limit! Mehr geht jetzt leider nicht mehr, weil RAM nicht größer...
Danke für deine Antwort sheel, ich hatte es vorher auch schon mit dem trivialen Algorithmus probiert, aber der brauchte für alle Zahlen bis 1.000.000 über eine halbe Stunde...

Das Thema hat sich dann zum Glück erledigt.
Gruß Technipion

 

[deepthroat]

Hi.

Wozu verwendest du ein Array von unsigned long long?

Du mußt dir in dem Array lediglich merken, ob die Zahl an dem Index eine Primzahl ist oder nicht.

Dazu reicht ein bool!

Das führt schonmal zu einer Reduzierung des Speicherbedarfs um den Faktor 8.

Weiterhin, die Zahl 2 ist die einzige gerade natürliche Zahl die eine Primzahl ist. Alle anderen geraden Zahlen sind durch 2 teilbar...

Du brauchst also nur die ungeraden Zahlen in dem Array speichern.

Das reduziert nochmal den Speicherbedarf um die Hälfte.

Eine weitere Möglichkeit wäre es ein Bitarray zu verwenden. Das würde den Speicherbedarf nochmal um den Faktor 8 reduzieren.

Statt mehr Speicher zu fordern, sollte man erstmal überlegen ob man nicht einfach am Algorithmus etwas verbessern kann.

 

[sheel]

An sowas, dass Bits statt 8 Byte reichen, denk ich natürlich wieder mal nicht

 

[Technipion]

Maaaaan bin ich blöd!
@deepthroat: Du hast natürlich Recht! Ich werde den Code nochmal etwas umschreiben...

Wenn man sich's mal überlegt: Ich habe einfach 6GB RAM verbraucht um bis auf die 1.500.000.000 zu rechnen, dabei hätten's knappe 190MB auch getan... -.-

Danke für deinen Tipp!
Gruß Technipion

EDIT:
Jetzt isses fertig. Ich habe es so weit es auf die Schnelle geht sparsamer gemacht. Das Programm braucht jetzt nur noch LIMIT/8 Bytes. Die Laufzeit ist kaum spürbar gestiegen, aber das ist die Speicherplatzreduzierung um 64 allemal wert!
Hier das Programm:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

int main(int argc, char *argv[])
{
    if(argc < 2)
    {
        printf("Limit angeben!\n");
        return 0;
    }
    unsigned long long LIMIT = atoll(argv[1]);
    if(LIMIT < 10)
        return 0;
    unsigned long long int i, j;
    std::vector<bool> primes(LIMIT, 1);
    for (i=2;i<LIMIT;i++)
        if (primes[i])
            for (j=i;i*j<LIMIT;j++)
                primes[i*j]=0;
    for (i=2;i<LIMIT;i++)
        if (primes[i])
            printf("%llu\n",i);
    return 0;
}

Danke nochmal für die Hilfe
Gruß Technipion