Sieb des Eratosthenes

[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 von 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.

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.

[p80286]

Unbenommen, wenn man den Aufwand für die Oberfläche mitrechnet ist Deine Version bestimmt schneller, aber meine Intention war erst einmal eine einfache Implementierung zur Verfügung zu stellen.
Hier wäre der nächste Schritt bestimmt, die geraden Zahlen(2) aus der Berechnung zu eliminieren.

Gruß
K-H