Primzahlen von 0 bis n

[Hador]

Ich möchte mit einem Programm alle Primzahlen von 0 und bis zu einer eingegebenen Grenze herausfinden.
An sich klappt das auch ganz gut. Allerdings habe ich dass Problem, dass ich bei einem Durchgang von 0 bis 1.000.000.000 bspw. knapp 1 GB Arbeitsspeicher benötige. Theoretisch könnte ich ja 1/8 des benötigten Rams sparen, wenn ich für jede Boolean-Variable nur ein Bit benötigen würde. (Imho benötigt eine Boolsche Variable bei Delphi 1 Byte.) Allerdings fällt mir dazu keine schnelle Lösung ein. Lediglich:

Delphi-Quellcode:

var 
  i: Byte;
...
if i and 1 shl x
...

was aber nicht allzu schnell sein dürfte.

Zusätzlich zu diesem Arbeitsspeicher-Problem würden mich auch noch Vorschläge für Verbesserungen der Geschwindigkeit interessieren. Gern auch in Assambler (Wenn es 'ne ausführliche Erklärung dabei gibt :wink: )

Jetzt aber erstmal mein Quelltext (Ich habe ihn mal ein wenig kommentiert):

Delphi-Quellcode:

program Primzahlengenerator;

{$APPTYPE CONSOLE}

uses
  Classes, Windows;

var
  IsPrim: array of Boolean;
  j, k, Max, HalfMax: Int64;
  s: String;
  F: TMemoryStream;
  Time, Time2: Cardinal;
begin
  Writeln('Bitte geben sie eine obere Grenze ein: ');
  Readln(Max);
  Writeln('Bitte geben sie eine Datei an,' +
          ' in der die Primzahlen gespeichert werden sollen:');
  Readln(s);

  Time := GetTickCount;

  SetLength(IsPrim, Max);
    // Länge der Arrays festlegen

  j := 2;
  while j < Max do
  // Vorerst alle Zahlen als Primzahlen markieren
  begin
    IsPrim[j] := True;
    Inc(j);
  end;

  HalfMax := Max div 2;
  // Die Hälfte der Grenze speichern, so dass diese folgend nicht mehr
  // errechnet werden muss

  F := TMemoryStream.Create;

  j := 2;
  while j <= HalfMax do
  // Die halbe Liste durchgehen
  begin
    if IsPrim[j] then
    begin
      F.Write(j, 4);
      // Zahl im MemoryStream schreiben
      k := j shl 1;
      // Startwert ist das doppelte der aktuellen Zahl (j)
      while k < Max do
      begin
        IsPrim[k] := False;
        // Alle Vielfachen der Zahl (j) als Nicht-Prim markieren
        Inc(k, j);
        // k auf das nächste Vielfache setzen
      end;
    end;
    Inc(j);
  end;

  // Die restlichen Primzahlen in den Stream schreiben
  while j < Max do
  begin
    if IsPrim[j] then
      F.Write(j, 4);
    Inc(j);
  end;
  F.SaveToFile(S);
  F.Free;

  // Benötigte Zeit ausgeben
  Time2 := GetTickCount;
  Time := Time2 - Time;
  Write(Time div 60000);
  Write(' Minuten ');
  Write((Time mod 60000) div 1000);
  Write(' Sekunden ');
  Write((Time mod 60000) mod 1000);
  Writeln(' Millisekunden');
end.

PS: Es ist mir klar, dass es schon einige Beiträge zu Primzahlen in der DP gibt, mir geht es jedoch direkt um die Optimierung meines Programms.

EDIT:
Über Bewertungen meines Programmes würde ich mich im übrigen auch freuen.

[shmia]

Zitat:

Zitat von Hador

Theoretisch könnte ich ja 1/8 des benötigten Rams sparen, wenn ich für jede Boolean-Variable nur ein Bit benötigen würde. (Imho benötigt eine Boolsche Variable bei Delphi 1 Byte.) Allerdings fällt mir dazu keine schnelle Lösung ein.

Dafür gibt es die Klasse TBits. :angel2:

[3_of_8]

Bitvektoren heißen die Dinger, die du meinst. Sie sind zwar nicht so schnell wie eine "richtige" Boolean-Variable, aber trotzdem nicht soo langsam. Wenn der Speicherverbrauch es rechtfertigt, dann nimm sie.

Im Übrigen wäre es evtl. einfacher, wenn du einfach die Primzahlen in einem optimierten Array (mit optimiert meine ich bei 100 anfangen und dann immer um das Doppelte vergrößern) alle benötigten Primzahlen speicherst.

Wenn du dann wissen willst, ob eine Zahl eine Primzahl ist oder nicht, kannst du mit binärer Suche durchgehen.

[SubData]

Edit: war quark...

[Hador]

Zitat:

Zitat von shmia

Dafür gibt es die Klasse TBits. :angel2:

Die intern imho mit Integern Arbeitet. Daher hätte ich dann eine maximale obere Grenze von 2.147.483.647 was auch nicht so groß ist.

Zitat:

Zitat von 3_of_8

Bitvektoren heißen die Dinger, die du meinst. Sie sind zwar nicht so schnell wie eine "richtige" Boolean-Variable, aber trotzdem nicht soo langsam. Wenn der Speicherverbrauch es rechtfertigt, dann nimm sie.

Tja ich hatte gehofft, jemand anders wüsste noch ne andere Lösung :P

Zitat:

Zitat von 3_of_8

Im Übrigen wäre es evtl. einfacher, wenn du einfach die Primzahlen in einem optimierten Array (mit optimiert meine ich bei 100 anfangen und dann immer um das Doppelte vergrößern) alle benötigten Primzahlen speicherst.

Du meinst statt dem MemoryStream?

Zitat:

Zitat von 3_of_8

Wenn du dann wissen willst, ob eine Zahl eine Primzahl ist oder nicht, kannst du mit binärer Suche durchgehen.

Kannst du das ein wenig näher erläutern :)

EDIT:

Zitat:

Zitat von SubData

Ich frag mich immernoch, wieso er bei einer Million durchläufe nen GB Arbeitsspeicher brauch... -hm-

Nicht eine Million sonder eine Milliaden. Und rechne mal eine Milliaden Byte (Das array of Boolean) in Megabyte um ^^

[Dax]

Zitat:

Zitat von Hador

Zitat:

Zitat von shmia

Dafür gibt es die Klasse TBits. :angel2:

Die intern imho mit Integern Arbeitet. Daher hätte ich dann eine maximale obere Grenze von 2.147.483.647 was auch nicht so groß ist.

Halb richtig. TBits arbeitet mit Integern - und zwar mit einer Liste. Größe: beschränkt nur durch den Arbeitsspeicher ;)

[Hador]

Na dann werd ichs gleich mal umbauen - Gut dass es hier immer Leute gibt, die einem über die eigenen Wissenslücken hinweghelfen :thumb:

So implementiert und ausprobiert:
Verbraucht weniger Ram und is sogar noch deutlich schneller.

--

Hat sonst noch jemand irgendeine Idee, was man verbessern könnte?


EDIT2:
Hab mir grad nochmal die implementation der Klasse TBits angeschaut:

Delphi-Quellcode:

TBits = class
  private
    FSize: Integer;
    FBits: Pointer;
    procedure Error;
    procedure SetSize(Value: Integer);
    procedure SetBit(Index: Integer; Value: Boolean);
    function GetBit(Index: Integer): Boolean;
  ...

Ich denke doch, dass ich einige Probleme bekomme, wenn ich die größe über MaxInt setze.
Daher hätte ich dann dovh eine maximale obere Grenze von 2.147.483.647.

Oder übersehe ich da was?

[Amateurprofi]

@Hador,

ich habe interessehalber mal eine Assemblerversion geschrieben, die die Daten in einem Bitfeld speichert.
Das ganze kann man noch optimieren
a) im Prinzip braucht man die Daten nur für ungerade Zahlen speichern weil die einzige gerade natürliche Primzahl 2 ist,
und die kann man ja separat prüfen
b) die Geschwindigkeit kann man sicherlich noch deutlich erhöhen.

hab nicht intensiv getestet...

Delphi-Quellcode:

var sieve:array of cardinal;

PROCEDURE CreateSieve(max:integer);
var len:integer;
PROCEDURE FillSieve;
asm
               pushad
               mov   edi,sieve         // Adresse sieve[0]
               xor   [edi],3           // Bit 0 und 1 löschen
               mov   ebx,[edi-4]       // Länge in Cardinals
               shl   ebx,5             // Länge in Bits
               // ECX = P = Erste ungerade Primzahl
               mov   ecx,3
               mov   eax,9             // P^2
               // Beginnend bei P*P alle Vielfachen von P als nichtprim markieren
@ClrBitLoop:   btr   [edi],eax         // Bit löschen
               add   eax,ecx           // + P
               cmp   eax,ebx           // noch im gültigen Bereich ?
               jb    @ClrBitLoop       // ja
               // Nächsthöheres P suchen
@NxtPrimeLoop: add   ecx,2             // P:=P+2
               bt    [edi],ecx         // Ist P prim ?
               jnc   @NxtPrimeLoop     // nein, nächstes P prüfen
               mov   eax,ecx           // P=Primzahl
               mul   ecx               // P^2
               cmp   eax,ebx           // noch im gültigen Bereich
               jb    @ClrBitLoop       // ja, vielfache als nichtprim markieren
@End:          popad
end;
begin
   len:=max shr 5 + 1;
   SetLength(sieve,len);
   FillChar(sieve[0],len shl 2,$AA);
   SetLength(sieve,len);
   FillSieve;
end;

FUNCTION IsPrime(p:integer):boolean;
asm
               mov   ecx,sieve         // Adresse sieve
               mov   edx,[ecx-4]       // Länge in Cardinal
               shl   edx,5             // Länge in Bits
               cmp   eax,edx
               jb    @TestPrime
               xor   eax,eax
@TestPrime:    bt    [ecx],eax
               setc  al
end;

[Hador]

Erstmal vielen Dank. Ich werde mal versucher durch deinen Quelltext durchzublicken bzw. ihn zu verstehen.
Irgendwo hab ich hier auch noch 'n Assembler-Tutorial rumfliegen :)

Zitat:

Zitat von Amateurprofi

a) im Prinzip braucht man die Daten nur für ungerade Zahlen speichern weil die einzige gerade natürliche Primzahl 2 ist,
und die kann man ja separat prüfen

Jo daran hatte ich auch schon gedacht. Aber als ich bei mir im Quelltext Inc(j) durch Inc(j, 2) ersetzt hatte, wurde das Programm wesentlich langsamer. Aber mal gucken wies bei dir aussieht. :thumb:

Falls ich irgendwo nicht weiterkomme in deinem Asm-Code, meld ich mich mal bei dir :wink:

[dino]

ich habe mit meinem Programm innerhalb von eineinhalb stunden alle Prinzahlen von 1 bis 1Millionen gekriegt. wie lange braucht ihr?