Sieb des Eratosthenes

[Amateurprofi]

Dieser Beitrag http://www.delphipraxis.net/1213282-post18.html hat mich neugierig gemacht,
und dieser http://www.delphipraxis.net/1215236-post28.html hat mich dann dazu gebracht, mich auch mal ein wenig mit diesem Thema zu beschäftigen.

Tja, "ein wenig" ist untertrieben, ich kam vom hundertsten zum tausendsten, aber ich denke das Ergebnis ist ganz brauchbar,
auch wenn ich mit dem Zeitverhalten bei der Sieberstellung noch nicht so ganz zufrieden bin - etwas bummelig für meinen Geschmack.

Im Anhang sind eine 32 Bit Version und eine 64 Bit Version meines Programms sowie drei Help-Dateien, Help.docx, Help.pdf, Help.mht,
die über die Hilfe Funktion des Programms aufrufbar sind, solange sie sich im selben Verzeichnis befinden, wie die .exe.
Die Help Dateien sind inhaltlich identisch - aber jeder hat ja seine persönlichen Vorlieben.

Die 32 Bit Version kann Siebe bis max 2 ^ 32 - 1 erstellen, die 64 Bit Version bis 200 Giga - wenn genug Ram verfügbar ist.

Ich habe mich bemüht, alle Fehler zu finden - da ich aber weiß, wo die Juckepunkte sind, habe ich mich auf diese konzentriert und wahrscheinlich die simpelsten Ungereimtheiten übersehen.
Wer also Fehler findet, bitte Info in diesem Thread oder als PN.

Ich empfehle, die Help-Datei zumindest querzulesen.

[Horst_]

Hallo,

ich habe gerade die 32-Bit Version Primesieve32 ( Win7 ) getestet und erhalte:
Schon beim Start "External Exception C0000001D"
Bei MAX = 1e9 passiert das scheinbar mit jeder neuen Siebzahl, die beim Sieben eingeblendet wird, aber auch wenn ich das Tausender-Trennzeichen umstelle. Dubios das.
http://www.delphigroups.info/2/56/526165.html
Ohne Sourcen mußt Du es wohl selbst entdecken ;-)

Gruß Horst

[Furtbichler]

Keine Quellen? Wozu dann das Ganze?

[Amateurprofi]

Zitat:

Zitat von Horst_ (Beitrag 1217302)

Hallo,

ich habe gerade die 32-Bit Version Primesieve32 ( Win7 ) getestet und erhalte:
Schon beim Start "External Exception C0000001D"
Bei MAX = 1e9 passiert das scheinbar mit jeder neuen Siebzahl, die beim Sieben eingeblendet wird, aber auch wenn ich das Tausender-Trennzeichen umstelle. Dubios das.
http://www.delphigroups.info/2/56/526165.html
Ohne Sourcen mußt Du es wohl selbst entdecken ;-)

Gruß Horst

Hallo Horst,
Kann ich bei mir nicht nachvollziehen.
Daher ein paar Fragen:

Wenn du sagst "Schon beim Start "External Exception ..." , meinst du dann gleich wenn du das Programm startest, oder wenn du die Erstellung des Siebs startest?

Wenn du sagst "Bei MAX= 1e9 ...", meinst du dann, die Exceptions kommen bei der Erstellung des Siebs oder bei der Anzeige der Zahlen in der Liste ganz rechts?
Und: wie ist das kleineren Werten?

Läuft das bei dir als Single-Thread oder als Multi-Thread?
Anders gefragt: Welche Zahl steht in der Statusbar im dritten Panel von rechts?

Last, not least:
Welche CPU hat dein Rechner. (External Exception C0000001D heißt Illegal Instruction, es könnte also gut sein, dass ich einen Assembler Befehl nutze, den die CPU nicht "kann" - eher unwarscheinlich, aber möglich).

Wieviel Ram ist verfügbar.

Danke für Deine Mithilfe.

[Horst_]

Hallo,

AMD Phenom X4 955, Win7.
Schon zum Start kommt die Fehlermeldung.
Bei Ausführen dann extrem oft.Das II.te Bild ist bei 4E9 single Thread.
Heute morgen war es 4-fach thread.
Aus http://www.delphigroups.info/2/56/526165.html:

Zitat:

This is most probably memory corruption at work, some faulty code in your
program may have managed to overwrite a return address on the stack. When
trying to return to the mangled address the CPU ends up on some data bytes it
tries to interpret as instructions, and it fails with this error. In fact it
probably ends up in code, but in the middle of a multibyte instruction. Data
usually does not have the EXECUTE privilege, so you get an access violation,
not an invalid instruction.

It is quite easy to overwrite stack memory by incorrect usage of functions
that have untyped VAR parameters (FillChar, Move, the stream Read methods).
If you pass a pointer variable to them and forget to dereference it -> BOOM!.

Gruß Horst

[Furtbichler]

Gibt es einen Grund, uns den Quellcode vorzuenthalten?

Meinst Du, das sei ein Mehrwert für die Menschheit, den man zu Geld machen kann?

[Bjoerk]

Ich nehm mal an, daß Amateurprofi den Algo von sx2008 benutzt. Hätte mich auch mal interessiert, ob Amateurprofi diesen um Faktor 2 beschleunigt hat, denn das Sieb braucht die geraden Zahlen ja nicht. ;)

[Amateurprofi]

Zitat:

Zitat von Bjoerk (Beitrag 1217420)

Ich nehm mal an, daß Amateurprofi den Algo von sx2008 benutzt. Hätte mich auch mal interessiert, ob Amateurprofi diesen um Faktor 2 beschleunigt hat, denn das Sieb braucht die geraden Zahlen ja nicht. ;)

Hast du mal beide verglichen?
Lass mal das von sx2008 laufen.
Und dann das von mir.

[p80286]

Ich hab hier ein altes TP-Sieb ausgegraben:

Delphi-Quellcode:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  LOOPEND= $FFFFFFF;
var
  sieb : array [0..LOOPEND] of byte;
  i,j,lauf : longint;
  start,
  ende : tdatetime;
begin
  writeln (' Sieber');
  fillchar(sieb,sizeof(sieb),#0);
  start:=time;
  i:=2;
  while i < (LOOPEND shr 1) do begin
    j:=i *2;
    while j <= LOOPEND do begin;
      sieb[j] := 1;
      inc(j,i);
    end;
    repeat
      inc(i,1);
    until sieb[i]=0;
  end;
  ende:=time;
  j:=1;
  for i:=1 to loopend do if sieb[i]=0 then inc(j,1);
  writeln(' im Bereich von 0 bis ',formatfloat('0,',loopend/1),' habe ich ',j,' Primzahlen gefunden!');
 writeln('Ben”tigte Zeit:',formatdatetime('HH.MM:SS:HH:ZZZ',ende-start));
  readln;
  for i:=1 to 20 {LOOPEND} do begin
    if sieb[i]=0 then write(i:8);
  end;
  readln;
end.

Die reine Rechenzeit für ca 250 Mio liegt bei ~15-16sec

Gruß
K-H

[Amateurprofi]

Für 250 Mio braucht meins (bei mir - Intel I7) etwa 600ms, und das ist nicht nur die Rechenzeit.
Ich schrieb ja, das es etwas bummelig ist und dass ich mit dem Zeitverhalten nicht so ganz zufrieden bin.