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?

[Hador]

Also von 0 - 1.000.000 brauche ich ca. 65 Millisekunden.

EDIT: Bild angehängt.

EDIT2: Wie ermittelst du die denn? BruteForce?

[jfheins]

Zitat:

Zitat von dino

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

:shock: Was hast du für einen Rechner?

Ich habe mit JAVA für Primzahlen bis 5 Mio. 0.281 sec gebraucht ... (Die Ausgabe dauerte ungleich länger ...)

[dino]

ich hab einen normalen Rechner, bloss nen eigenen code...
der wird wahrscheinlich irre lahm sein!

(mit inttostr und strtoint und listbox raus und rein noch und nöcher)

wollte mal nen Vergleich

Hier mein Quellcode:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var i,i1:integer;
prim:boolean;
begin
listbox1.Items.add('2');
for i:=3 to 1000000 do
begin
prim:=true;
i1:=0;
while strtoint(listbox1.items[i1])<sqrt(i) do
begin
if (i/strtoint(listbox1.Items[i1]))=(i div strtoint(listbox1.Items[i1])) then prim:=false;
inc(i1);
end;
if prim=true then listbox1.items.add(inttostr(i));
gauge1.progress:=i;
gauge2.progress:=i-((i div 10000)*10000);
end;
end;

[dino]

was ist brute force?
habs einfac so emacht, wie es mir einfiel

[jfheins]

Brute Force ist das (systematische) durchprobiern aller Möglichkeiten.

Btw.: Bei dem Code kann ich gut verstehen, dass du eineinhalb Stunden brauchst ;)

[Hador]

Zitat:

Zitat von dino

was ist brute force?

http://de.wikipedia.org/wiki/Bruteforce

Du nutzt zudem noch sehr viele sehr langsame funktionen (bspw. StrToInt oder auch sqrt)

Ferner solltest du dir echt angewöhnen, deinen Quelltext zu strukturieren. Ihn zu lesen ist grausam :wink:

EDIT: Arr der rote Kasten ist mal wieder im Urlaub

[dino]

joa nun da ich mir euer code ansehe...

den 1. kann ich noch nachvollziehen

den 2. nicht

Edit: oh ja Quellcde strukturieren!!! mercks mir mal irgendwann

[Hador]

Zitat:

Zitat von dino

joa nun da ich mir euer code ansehe...
den 1. kann ich noch nachvollziehen
den 2. nicht

Ich auch noch nicht. Hab mir das Asm-Tutorial aber schon rausgekramt (Jetzt habe ich ja 2 Wochen Ferien zum lernen ^^)

Zitat:

Zitat von dino

Edit: oh ja Quellcde strukturieren!!! mercks mir mal irgendwann

Irgendwann wird sonst der Tag kommen, an dem du deine eigenen kurzzeitig nicht bearbeiteten Projekte kaum noch durchblickst.

[dino]

:oops: hab letztens mit meinem JuFo Kollegen mein Ameisenprogramm wieder angeguckt und dran rumprogrammiert(ihr kennt das alte ja) und weiss was du meinst.

Nur: (ich werds nochmal fragen müssen) hab ich jetzt das Problem, dass werte verändert werden ohne verändert zu werden(wir haben alles durchgeguckt, der wert wird nicht per := angerührt), aber das ist eine andere Geschichte


Meld dich, wenn du damit klar kommst

[Hador]

Zitat:

Zitat von dino

Meld dich, wenn du damit klar kommst

Jo mach ich. Ich habe Amateurprofi ja schon angedroht, dass ich ihn ggf. ausfragen werde ^^

[Rudirabbit]

Hi !

@Hador: Wegen des Bool Array Ram Speicher Problems, hat du schon mit PACKED ARRAY getestet ?

[Amateurprofi]

Zitat:

Zitat von dino

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

meine im Beitrag weiter oben gezeigte Version braucht für 1..1000000 ca. 9 ms und für 1..1000000000 ca. 48 s.
Und das ist nicht besonders schnell.
negaH hat m.W. eine Routine die 14 s braucht für 1..2^32 ..... (aber die hat er sicherlich nicht in 1/2 h zusammengeflickt)

[dino]

wenn man die Programmierzeit mit dazuzählt liege ich garnicht mal so schlecht in der Zeit

[negaH]

Zitat:

Und das ist nicht besonders schnell.
negaH hat m.W. eine Routine die 14 s braucht für 1..2^32

Interessenshalber habe ich meinen Code eben auf meinem Laptop getestet. Damals ergaben sich die Zeiten auf einem Pentium 4 1.5Ghz 512MB und mein neues Laptop ist ein Intel Core Duo mit 2.16Ghz 1Gb, also mit 2 CPUs a 2.16 GHz und doppelt Speicher mit viel höherem Takt.

Komischerweise ergaben sich folgende Zeiten

Code:

 1 bis    1000000 =  0.03 sec
 1 bis 1000000000 = 12.70 sec
 1 bis 2^32-1     = 56.00 sec

also langsammer als auf meinem alten P4, egal. Komischerweise sind aber meine Berechnung von der Zahl Pi mit Millionen Stellen wiederum mehr als 4 mal schneller -> 1Mio Stellen in 3.5 Sekunden statt eben 13 Sekunden auf dem P4.

Die wichtige Frage ist, wie lange brauchen zb. eure Algorithmen um alle Primzahlen zwischen zb. 1000000000 bis 2000000000 zu berechnen ?

Code:

1000000000 bis 2000000000 = 17.54 sec

bei meinem Code, allerdings sollte ich erstmal überprüfen warum das Ding auf meinem Laptop so deutlich langsammer ist als auf meinem P4.

Denn gerade die Bereichberechnung der Primzahlen ist ein Indiz für die Effizenz des Algos. Im Falle des Siebes wie hier müssen nämlich alle Vorgängerprimzahlen ermittelt werden um überhaupt den gwünschten Ausschnittsbereich berechnen zu können.

Gruß Hagen

[negaH]

Hm, ich weis ist offtopic, aber könnte es sein das eine Zeitmessung basierend auf dem Time Stamp Counter -> RDTSC und QueryPerfoamnceCounter() auf einem Mehrprozessoren System falsche Werte liefert ?

Das wäre die einzigste Erklärung so auf die Schnelle.

Gruß Hagen

[alzaimar]

Ich würde an Eurer Stelle mal nach dem "Sieve Of Atkins" googeln. Recht flott, wie man sieht. Hier der Output eines Testprogramms:

Zitat:

Zitat von Eine Delphi-Implementierung des Sieve Of Atkins

266762506 primes up to 1000359390 in 1740 tics

[negaH]

guter Tipp Alzaimar :-) dumm ist nur das mein Code nach exakt diesem Sieb arbeitet ;)

zZ. macht mich aber der enorme negative Unterschied von einem P4 1.5Ghz zu einem Dual Core 2.16Ghz Rechner stuzig.

Gruß Hagen

[edit]

Das Messtechniker Sprichwort lautet "wenn du misst dann misst du Mist" !

Meine Zeitberechnungsroutinen basieren auf RDTSC und QueryPerformanceCounter()/Frequency(). Spaßenshalber nun die gleiche Funktion mal parallel mit GetTickCount() gemessen und siehe da

12756 ms mit meiner Messroutinen
4610 ms mit GetTickCount()

Ergo: RDTSC in Kombinaton mit QueryPerformanceCounter funktioniert auf Dual Cores nicht sauber.

Ein weiteres sehr komoische Verhalten ist das die Messungen mehrmals hintereinander total verrückte Abweichungen ergeben. Es scheint das Powermanagement das die CPUs dynamisch im Takt drosselt schuld zu sein. Jetz muß ich erstmal nach ne besseren Messroutine Ausschau halten. (von wegen meine DECMath routinen wären nur 4 mal schneller als auf einem P4, so wie es aussieht ist es 12 mal schneller).

[/edit]

[Hador]

Zitat:

Zitat von Rudirabbit

@Hador: Wegen des Bool Array Ram Speicher Problems, hat du schon mit PACKED ARRAY getestet ?

Hab ich gerade. Der Speicherverbrauch bleibt gleich, dafür wird jedoch das Programm langsamer.

Zitat:

Zitat von negaH

Hm, ich weis ist offtopic, aber könnte es sein das eine Zeitmessung basierend auf dem Time Stamp Counter -> RDTSC und QueryPerfoamnceCounter() auf einem Mehrprozessoren System falsche Werte liefert ?

Das wäre die einzigste Erklärung so auf die Schnelle.

Gruß Hagen

Du könntest doch einfach mal mit GetTickCount die Zeit messen. Es ist zwar nicht ganz genau - Ich mene das habe ich mal in einem deiner Beiträge gelesen ^^ - aber immerhin müsstest du einen ungefähren Wrt bekommen. So könntest du kontrollieren, ob dieser Wert grob von dem durch RDTSC ermittelten abweicht.

EDIT: Arr irgendwie hab ich deinen letzten Beitrag übersehen :gruebel:

Zitat:

Zitat von alzaimar

Ich würde an Eurer Stelle mal nach dem "Sieve Of Atkins" googeln. Recht flott, wie man sieht. Hier der Output eines Testprogramms:

Zitat:

Zitat von Eine Delphi-Implementierung des Sieve Of Atkins

266762506 primes up to 1000359390 in 1740 tics

Ich werde erstmal versuchen meinen jetzigen Algo noch etwas zu optimieren. Dann werde ich mir das SoA. aber auf alle Fälle mal anucken. Danke für den Hinweis.

[negaH]

Ja sorry das ich deinen Thread hijacked hab, ich hab hier einen neuen Thread angelegt http://www.delphipraxis.net/internal...=618629#618629

Und defakto ist es so das meine Messroutinen mit mindestens einem Faktor von 3 mal daneben liegen, allerdings eben auch stark abhängig ob die CPUs durch das ACPI gedrosselt werden (das konnte ich schon verifizieren da ich die CPUs auch manuell drosseln kann, per Hotkey).

Aber wir sollte das alles im obigen neuen Thread fortsetzen, sorry nochmals.

Gruß Hagen

[negaH]

so zurück zum Thema. Alzaimar hat dir ja schon einen Link auf seinen Source gegeben. Wenn du mein DEC, http://www.michael-puff.de/Developer...agen_Reddmann/ , runterlädst findest du in Unit Prime.pas meine Implementation des Siebes. Als Referenz für deine Test wohl ausreichend.

Kleiner Tipp noch: wenn du mit meinen Messroutinen aus dem DEC arbeitest und du hast einen Mehrprozessorenkern dann baue doch die 2. CPU vorher aus, ansonsten misst du Mist ;)

Gruß Hagen

[Hador]

Zitat:

Zitat von negaH

so zurück zum Thema. Alzaimar hat dir ja schon einen Link auf seinen Source gegeben. Wenn du mein DEC, http://www.michael-puff.de/Developer...agen_Reddmann/ , runterlädst findest du in Unit Prime.pas meine Implementation des Siebes. Als Referenz für deine Test wohl ausreichend.

Kleiner Tipp noch: wenn du mit meinen Messroutinen aus dem DEC arbeitest und du hast einen Mehrprozessorenkern dann baue doch die 2. CPU vorher aus, ansonsten misst du Mist ;)

Gruß Hagen

Ne da kann ich ganz beruhigt sein. Bei mir schlägt 'n AMD Athlon XP 2500+ drin. Also schon etwas betagter
Aber danke schonmal für deine Referenz :lol: